Haskell n元树遍历

我对Haskell来说还很陌生，我正在尝试找出如何遍历n元树。作为输出，我希望获取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是树的列表，并且期望它是一棵奇异的树。有没有办法做到这一点？我一直在尝试map函数，大致方法如下:

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

任何帮助将不胜感激，所以在此先感谢..!

最佳答案

遍历一棵树意味着遍历所有子树并将结果列表展平为一个。

这转化为

travTree (Branch branches) = concat $ map travTree branches

请注意，此定义的右侧还有更简洁的表示法，例如branches >>= travTree或concatMap travTree branches，但我认为上述最清晰的表示法。

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

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

关于Haskell n元树遍历，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2335629/