Как я могу использовать систему типов Haskell для обеспечения корректности, все еще имея возможность сопоставления с образцом? - PullRequest
Новая
       26

Как я могу использовать систему типов Haskell для обеспечения корректности, все еще имея возможность сопоставления с образцом?

1 голос
/ 09 октября 2010

Допустим, у меня есть adt, представляющий какую-то древовидную структуру: 

data Tree = ANode (Maybe Tree) (Maybe Tree) AValType
          | BNode (Maybe Tree) (Maybe Tree) BValType
          | CNode (Maybe Tree) (Maybe Tree) CValType

Насколько я знаю, нет способа сопоставления с шаблоном с помощью конструкторов типов (иначе сами функции сопоставления не имели бытип?), но я все же хотел бы использовать систему типов времени компиляции, чтобы исключить возможность возврата или анализа неправильного «типа» узла дерева.Например, возможно, что CNode могут быть только родителями для ANodes.Я мог бы иметь 

parseANode :: Parser (Maybe Tree)

в качестве функции синтаксического анализа Parsec, которая используется как часть моего синтаксического анализатора CNode: 

parseCNode :: Parser (Maybe Tree)
parseCNode = try (
                  string "<CNode>" >>
                  parseANode >>= \maybeanodel ->
                  parseANode >>= \maybeanoder ->
                  parseCValType >>= \cval ->
                  string "</CNode>"
                  return (Just (CNode maybeanodel maybeanoder cval))
             ) <|> return Nothing

В соответствии с системой типов parseANode может в конечном итоге вернуть Maybe CNode, Maybe BNode или Maybe ANode, но я действительно хочу убедиться, что он возвращает только Maybe ANode.Обратите внимание, что я не хочу проверять значение схемы или данные во время выполнения - я просто пытаюсь проверить достоверность синтаксического анализатора, который я написал для конкретной схемы дерева.Я не пытаюсь проверить проанализированные данные на правильность схемы, я действительно пытаюсь проверить мой синтаксический анализатор на правильность схемы - я просто хочу убедиться, что я неКогда-нибудь я попытаюсь разобрать parseANode, чтобы получить что-то, отличное от значения ANode.

Я надеялся, что, если я сопоставлю конструктор значений в переменной bind, вывод типа определит, что я имел в виду:

parseCNode :: Parser (Maybe Tree)
parseCNode = try (
                  string "<CNode>" >>
                  parseANode >>= \(Maybe (ANode left right avall)) ->
                  parseANode >>= \(Maybe (ANode left right avalr)) ->
                  parseCValType >>= \cval ->
                  string "</CNode>"
                  return (Just (CNode (Maybe (ANode left right avall)) (Maybe (ANode left right avalr)) cval))
             ) <|> return Nothing

Но это имеет много проблем, не последнюю из которых тот parseANode больше не может возвращать Nothing.И все равно это не работает - похоже, что переменная связывания обрабатывается как сопоставление с шаблоном, и среда выполнения жалуется на неисчерпывающее сопоставление с шаблоном, когда parseANode либо возвращает Nothing, либо Maybe BNode, либо что-то в этом роде.

Я мог бычто-то вроде этого: 

data ANode = ANode (Maybe BNode) (Maybe BNode) AValType
data BNode = BNode (Maybe CNode) (Maybe CNode) BValType
data CNode = CNode (Maybe ANode) (Maybe ANode) CValType

но такой отстой, потому что он предполагает, что ограничение применяется ко всем узлам - мне это может быть не интересно - на самом деле это могут быть только CNodes, которые могут быть толькоАноды воспитания.Так что, думаю, я мог бы сделать это: 

data AnyNode = AnyANode ANode | AnyBNode BNode | AnyCNode CNode

data ANode = ANode (Maybe AnyNode) (Maybe AnyNode) AValType
data BNode = BNode (Maybe AnyNode) (Maybe AnyNode) BValType
data CNode = CNode (Maybe ANode) (Maybe ANode) CValType

, но тогда это значительно затруднит сопоставление с образцом с * Node's - на самом деле это невозможно, потому что это просто совершенно разные типы.Я мог бы создать класс типов, где бы я ни хотел сопоставить с образцом, я думаю 

class Node t where
    matchingFunc :: t -> Bool

instance Node ANode where
    matchingFunc (ANode left right val) = testA val

instance Node BNode where
    matchingFunc (BNode left right val) = val == refBVal

instance Node CNode where
    matchingFunc (CNode left right val) = doSomethingWithACValAndReturnABool val

В любом случае, это просто кажется немного грязным.Кто-нибудь может придумать более краткий способ сделать это?

Ответы [ 3 ]

4 голосов
/ 09 октября 2010

Я не понимаю вашего возражения против вашего окончательного решения. Вы все еще можете сопоставить паттерн с AnyNode s, например: 

f (AnyANode (ANode x y z)) = ...

Это немного более многословно, но я думаю, что у него есть нужные вам технические характеристики.

4 голосов
/ 09 октября 2010

Я все еще хотел бы использовать систему типов времени компиляции, чтобы исключить возможность возврата или анализа неправильного «типа» узла дерева

Это похоже на случай использованиядля GADT. 

{-# LANGUAGE GADTs, EmptyDataDecls #-}
data ATag
data BTag
data CTag

data Tree t where
  ANode :: Maybe (Tree t) -> Maybe (Tree t) -> AValType -> Tree ATag
  BNode :: Maybe (Tree t) -> Maybe (Tree t) -> BValType -> Tree BTag
  CNode :: Maybe (Tree t) -> Maybe (Tree t) -> CValType -> Tree CTag

Теперь вы можете использовать Tree t, когда вас не интересует тип узла, или Tree ATag, когда вы делаете.

1 голос
/ 20 декабря 2010

Расширение ответа Кигана: кодирование свойств корректности красных / черных деревьев является своего рода каноническим примером. Этот поток имеет код, показывающий как GADT, так и решение с вложенным типом данных: http://www.reddit.com/r/programming/comments/w1oz/how_are_gadts_useful_in_practical_programming/cw3i9

...