Haskell n-ary树遍历

Question

我对Haskell很新,我正在努力研究如何遍历一棵n-ary树.作为输出,我希望获得Leaf值列表(因为分支没有值),因此对于testtree,这将是:4,5

到目前为止我的定义是:

data Tree a = Leaf a | Branch [Tree a] deriving (Show)

travTree                    :: Tree a -> [a]
travTree (Leaf x)           = [x]
travTree (Branch (x:xs))    = travTree x : travTree xs

testtree = Branch [(Leaf "4"), (Leaf "5")]

但它给出了错误:

Couldn't match expected type `Tree a'
  against inferred type `[Tree a]'
In the first argument of `travTree', namely `xs'
In the second argument of `(:)', namely `travTree xs'
In the expression: travTree x : travTree xs

我假设这是因为xs是一个树列表,它期待一棵奇异的树.有没有办法做到这一点？我一直在尝试地图功能,顺序如下:

travTree (Branch (x:xs))    = travTree x : map travTree xs

但它抱怨说:

Occurs check: cannot construct the infinite type: a = [a]
When generalising the type(s) for `travTree'

我也尝试将函数签名更改为:

travTree                    :: Tree a -> [b]

这给出了错误:

Couldn't match expected type `a' against inferred type `[b]'
  `a' is a rigid type variable bound by
      the type signature for `travTree' at Main.hs:149:36
In the first argument of `(:)', namely `travTree x'
In the expression: travTree x : map travTree xs
In the definition of `travTree':
    travTree (Branch (x : xs)) = travTree x : map travTree xs

任何帮助将不胜感激,所以提前感谢..!

Answer 1

您使用的是正确的行map,但是在遍历每个子树后,您希望concat将结果列表放在一起.(x:xs)使用时,使用模式也没有必要中断列表的第一个元素map.我写这个:

travTree (Branch xs) = concatMap travTree xs

(但要注意;我没有测试过!但是我经常发现我的"无限类型a = [a]"问题是由需要的map地方引起的concatMap.)

Answer 2

遍历树意味着遍历所有子树并将生成的列表展平为一个.

这转化为

travTree (Branch branches) = concat $ map travTree branches

需要注意的是还有更简洁的符号,如branches >>= travTree或concatMap travTree branches对这个定义的右手边,但我认为上面的一个是最清晰的.

编辑:为了完整性重新引入列表理解版本:

travTree (Branch branches) = [ elem | br <- branches, elem <- travTree br ]

Answer 3

当我刚接触Haskell时,我遇到了同样的问题.我终于找到了如何通过放慢速度并查看类型来解决问题.(当我写了很多Scheme时,我反而放慢速度,看看非常简单的输入/输出对.我有时会在Haskell中这样做,但直到我查看了类型.)

travTree                    :: Tree a -> [a]
travTree (Leaf x)           = [x]
travTree (Branch (x:xs))    = travTree x : travTree xs

你的类型看起来正确:Tree a -> [a]听起来像"我所有的叶子".

travTree (Leaf x) = [x]

这种情况适当地将a转换Tree a为a [a].

travTree (Branch (x:xs)) = travTree x : travTree xs

好的,输入肯定是一个Tree a.如果输出是[a],并且第一个运算符是(:) :: a -> [a] -> [a],那么我们需要travTree x :: a和travTree xs :: [a].这有用吗？

好吧,它失败有两个原因:实际上,travTree x :: [a]你不能将列表排在另一个列表上(你需要(++) :: [a] -> [a] -> [a]它).你不能传递[Tree a]到travTree :: Tree a -> [a]--you're给它的树列表时,预计一棵树.

您可以使用map以下方法解决第二个问题:map travTree xs.这有类型[Tree a] -> [[a]].幸运的是,这现在适合travTree x :,所以

(travTree x : map travTree xs) :: [[a]]

现在你遇到了问题,[[a]]而不是[a].concat通过展平一次来解决这个问题,所以

travTree (Branch (x:xs)) = concat (travTree x : map travTree xs) :: [a]

符合预期Tree a -> [a].

其他答案是正确的说,这里的解构是没有意义的,但我希望看到拼出的类型有助于你理解如何模仿你头脑中的类型推断.这样你就可以解决其他类似问题的问题.