1

假设我有一个代表某种树结构的广告：

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

据我所知，没有办法对类型构造函数进行模式匹配（或者匹配函数本身没有类型？）但我仍然想使用编译时类型系统来消除返回或解析的可能性树节点的错误“类型”。例如，可能 CNode 只能是 ANode 的父节点。我可能有

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。请注意，这不是我想要执行的数据模式值或运行时检查 - 我实际上只是试图检查我为特定树模式编写的解析器的有效性。IOW，我不是要检查解析数据的模式正确性，我真正想做的是检查我的解析器的模式正确性——我只是想确保有一天我不会搞砸 parseANode返回 ANode 值以外的值。

我希望也许如果我匹配绑定变量中的值构造函数，类型推断会弄清楚我的意思：

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 只能作为 ANodes 的父节点。所以我想我可以这样做： 

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 的模式匹配变得更加困难 - 事实上这是不可能的，因为它们只是完全不同的类型。我想我可以在任何我想进行模式匹配的地方创建一个类型类

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

无论如何，这似乎有点混乱。谁能想到一个更简洁的方法来做到这一点？

4

3 回答 3

4

我仍然想使用编译时类型系统来消除返回或解析树节点的错误“类型”的可能性

这听起来像是 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时使用。

于 2010-10-08T22:42:26.490 回答
4

我不明白你反对你的最终解决方案。您仍然可以对AnyNodes 进行模式匹配，如下所示： 

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

它有点冗长，但我认为它具有您想要的工程属性。

于 2010-10-09T00:22:05.730 回答
1

基根回答的扩展：编码红/黑树的正确性属性是一个典型的例子。该线程的代码显示了 GADT 和嵌套数据类型解决方案：http ://www.reddit.com/r/programming/comments/w1oz/how_are_gadts_useful_in_practical_programming/cw3i9

于 2010-12-20T14:42:32.300 回答