Haskell новичок по типам

Question

Я совершенно не знаком с Haskell (и, в более общем плане, функциональным программированием), так что простите меня, если это действительно базовый материал. Чтобы получить больше, чем вкус, я пытаюсь реализовать в Haskell некоторые алгоритмические материалы, над которыми я работаю. У меня есть простой модуль Interval, который реализует интервалы на линии. Он содержит тип

data Interval t = Interval t t 

функции помощника

makeInterval :: (Ord t) => t -> t -> Interval t 
makeInterval l r | l <= r = Interval l r 
        | otherwise = error "bad interval" 

и некоторые вспомогательные функции относительно интервалов.

Здесь мой интерес заключается в многомерных интервалах (d-интервалах), те объекты, которые состоят из d интервалов. Я хочу отдельно рассмотреть d-интервалы, которые являются объединением d непересекающихся интервалов на линии (множественный интервал) от тех, которые являются объединением d-интервала на d отдельных линиях (интервал трека). С различными алгоритмическими процедурами в виде, я думаю, было бы неплохо иметь два различные типа (даже если оба список интервалов здесь), такие как

import qualified Interval as I 

-- Multilple interval 
newtype MInterval t = MInterval [I.Interval t] 

    -- Track interval 
newtype TInterval t = TInterval [I.Interval t]  

для обеспечения различных проверок здравомыслия, например,

makeMInterval :: (Ord t) => [I.Interval t] -> MInterval t 
makeMInterval is = if foldr (&&) True [I.precedes i i' | (i, i') <- zip is (tail is)] 
        then (MInterval is) 
        else error "bad multiple interval" 


makeTInterval :: (Ord t) => [I.Interval t] -> TInterval t 
makeTInterval = TInterval 

Теперь я добираюсь до сути, наконец! Но некоторые функции, естественно, связаны как с несколькими интервалами, так и с интервалами. Например, функция order вернет количество интервалов в несколько интервалов или интервал дорожки. Что я могу сделать? Добавление

-- Dimensional interval 
data DInterval t = MIntervalStuff (MInterval t) | TIntervalStuff (TInterval t) 

не помогает, так как, если я хорошо понимаю (поправьте меня, если я ошибаюсь), я должен был бы написать

order :: DInterval t -> Int 
order (MIntervalStuff (MInterval is)) = length is 
order (TIntervalStuff (TInterval is)) = length is 

и называют order в order (MIntervalStuff is) или order (TIntervalStuff is) когда is это MInterval или TInterval. Не так уж и здорово, это выглядит странно. Я также не хочу дублировать функцию (у меня есть много функций, которые связаны как с множественными, так и с дорожками, а также с некоторыми другими определениями d-интервалов, такими как множественные интервалы длины и длины трека).

У меня осталось ощущение, что я совершенно не прав и пропустил какой-то важный момент о типах в Haskell (и/или не могу забыть здесь достаточно о программировании OO). Итак, совершенно новый вопрос, каким было бы лучшим способом в Haskell справиться с такой ситуацией? Должен ли я забыть о введении MInterval и TInterval и идти только с одним типом?

Большое спасибо за вашу помощь,

Garulfo

Answer 1

рассмотреть использование классов типов, чтобы показать сходство между различными типами. См. Учебник по haskell [1] о классах и перегрузке для справки.

[1]: http://www.haskell.org/tutorial/classes.html Haskell учебник

Answer 2

Что вы хотите типы с той же структурой и общих операций, но которые могут быть выделены, и для которых некоторые операции имеют смысл только на том или ином типе. Идиомой для этого в Haskell является Phantom Types.

1. http://www.haskell.org/haskellwiki/Phantom_type
2. http://www.haskell.org/haskellwiki/Wrapper_types
3. http://blog.malde.org/index.php/2009/05/14/using-a-phantom-type-to-label-different-kinds-of-sequences/
4. http://neilmitchell.blogspot.com/2007/04/phantom-types-for-real-problems.html

Answer 3

Edit: это та же идея, как ответ sclv в; его ссылки предоставляют дополнительную информацию об этой технике.

Как насчет этого подхода?

data MInterval = MInterval --multiple interval 
data TInterval = TInterval --track interval 

data DInterval s t = DInterval [I.Interval t] 

makeMInterval :: (Ord t) => [I.Interval t] -> Maybe (DInterval MInterval t) 
makeMInterval is = if foldr (&&) True [I.precedes i i' | (i, i') <- zip is (tail is)] 
    then Just (DInterval is) 
    else Nothing 

order :: DInterval s t -> Int 
order (DInterval is) = length is 

equalOrder :: DInterval s1 t -> DInterval s2 t -> Bool 
equalOrder i1 i2 = order i1 == order i2 

addToMInterval :: DInterval MInterval t -> Interval t -> Maybe (DInterval MInterval t) 
addToMInterval = .. 

Здесь типа DInterval представляет интервалы несколько измерений, но требуется дополнительный параметр типа в качестве типа фантома. Эта дополнительная информация типа позволяет typechecker различать различные виды интервалов, даже если они имеют точно такое же представление.

Вы получаете тип безопасности вашего оригинального дизайна, но все ваши структуры имеют одну и ту же реализацию. Реально, когда тип интервала не имеет значения, вы можете оставить его неопределенным.

Я также изменил реализацию вашей функции makeMInterval; возвращая Maybe для такой функции, которая намного более идиоматична, чем ошибка вызова.

Более объяснение Может быть:

Давайте рассмотрим вашу функцию makeInterval. Предполагается, что эта функция принимает список интервалов, и если они удовлетворяют критериям, возвращайте несколько интервалов, в противном случае интервал трека. Это объяснение приводит к типу:

makeInterval :: (Ord t) => 
    [I.Interval t] -> 
    Either (DInterval TInterval t) (DInterval MInterval t) 

Теперь, когда у нас есть тип, как его реализовать? Мы хотели бы повторно использовать нашу функцию makeMInterval.

makeInterval is = maybe 
        (Left $ DInterval TInterval is) 
        Right 
        (makeMInterval is) 

Функция maybe принимает три аргумента: по умолчанию b использовать, если Может это Nothing, функция a -> b если Может это Just a и Maybe a. Он возвращает либо значение по умолчанию, либо результат применения функции к значению Maybe.

По умолчанию используется интервал дорожки, поэтому мы создаем интервал левого трека для первого аргумента. Если возможно, Just (DInterval MInterval t), то существует многократный интервал, поэтому все, что необходимо, - это вставить его в правую сторону. Наконец, для создания множественного интервала используется makeMInterval.

Answer 4

Что вы хотите, это классная доска. Typeclasses - это то, как перегрузка выполняется в Haskell. Класс типа - это общая структура, которая разделяется многими типами. В вашем случае, если вы хотите создать класс всех типов, которые имеют order функцию:

class Dimensional a where 
    order :: a -> Int 

Это говорит, что есть класс типов a называемых Dimensional, и для каждого типа, принадлежащего к этому классу, есть функция a -> Int называется order.Теперь вам необходимо объявить все ваши типы как принадлежащие к классу:

instance Dimensional MInterval where 
    order (MInterval is) = length is 

и так далее. Вы также можете объявлять функции, которые действуют на вещах, которые из данного класса, таким образом:

isOneDimensional :: (Dimensional a) => a -> Bool 
isOneDimensional interval = (order interval == 1) 

Типа декларация может быть прочитан «для всех типов a, принадлежащих класс типов Dimensional, эта функция принимает a и возвращает Bool ".

Мне нравится думать о классах как алгебраических структурах в математике (это не совсем то же самое, что вы не можете принуждать некоторые логические ограничения, но ...): вы указываете, какие требования относятся к типу, принадлежащему некоторый класс (по аналогии, операции должны быть определены над множеством для его принадлежности к определенной алгебраической конструкции), а затем для каждого конкретного типа вы указываете, какова конкретная реализация требуемых функций (по аналогии, что являются конкретными функциями для каждого конкретного набора).

Возьмите, например, группу. Группы должны иметь идентичность, инверсию для каждого элемента и умножения:

class Group a where: 
     identity :: a 
     inverse :: a -> a 
     (<*>)  :: a -> a -> a 

и Целые образуют группу по сложению:

instance Group Integer where: 
     identity = 0 
     inverse x = (- x) 
     x <*> y  = x + y 

Обратите внимание, что это не решит повторения, как вы должны создавать экземпляры каждого типа.