Haskell N 叉树遍历

我对 Haskell 还很陌生，我正在尝试找出如何遍历 n 叉树。作为输出，我希望获得叶值列表（因为分支没有值），因此对于 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

任何帮助将不胜感激，所以提前致谢..！

你的路线是对的map，但是在遍历你想要的每个子树之后concat结果列表在一起。也没有必要用(x:xs)使用时的图案map。我会把它写成：

travTree (Branch xs) = concatMap travTree xs

（但是要注意；我还没有测试过！但是我经常发现我的“无限类型 a = [a]”问题是由map where concatMap是需要的。）