0

我正在尝试构建一棵树，其子项在列表中表示。每个孩子自己都可能是子树等。所以我走这条路——

data Children a = NoChildren | Cons a (Children a) deriving (Show, Read, Ord, Eq)
data Tree a = EmptyTree | Node a (Children a) deriving (Show, Read, Ord, Eq)

现在我尝试创建这样的树

let subtree1 = Node 67 NoChildren
let subtree2 = Node 86 NoChildren
let tree1 = Node 83 (subtree1 `Cons` (subtree2 `Cons` NoChildren))

它工作正常，直到 subtree2。未创建 tree1。抛出的错误是这样的 -

<interactive>:96:15:
    No instance for (Num (Tree Integer))
      arising from the literal `83'
    Possible fix: add an instance declaration for (Num (Tree Integer))
    In the first argument of `Node', namely `83'
    In the expression: Node 81 (subtree1 `Cons` (subtree2 `Cons` NoChildren))
    In an equation for `tree1':
      tree1 = Node 81 (subtree1 `Cons` (subtree2 `Cons` NoChildren))

我根本不明白这个错误错误。为什么抱怨 83 是文字。subtree1 和 subtree2 也有文字，它们很好......

我通过执行以下操作解决了问题

data Tree a = EmptyTree | Node a [Tree a] deriving (Show, Read, Ord, Eq)

flatten [] = []
flatten x:xs = x ++ flatten xs

preorder EmptyTree = []
preorder (Node a []) = [a]
preorder (Node a children) = [a] ++ flatten (map preorder children)
4

1 回答 1

4 
data Children a = NoChildren | Cons a (Children a)

表示您Children a与 同构[a]，因此您的

data Tree a = EmptyTree | Node a (Children a)

同构于

data List a = Empty | Nonempty a [a]

这又同构于[a].

你想要的是孩子们自己是Trees，所以你应该使用

data Children a = NoChildren | Cons (Tree a) (Children a)

或平原

data Tree a = EmptyTree | Node a [Tree a]

错误是因为某些属于（同上）的subtree1类型。然后当你写Tree aaNumsubtree2

tree1 = Node 83 (subtree1 `Cons` (subtree2 `Cons` NoChildren))

的推断类型tree1是Tree (Tree a)（对于某些a属于Num），因此

83 :: Tree a

但是没有s 的Num实例Tree。

于 2013-01-15T18:58:05.253 回答