Haskell N 叉树遍历

Question

我对 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 是一个树列表并且它期望一个单一的树。有没有办法做到这一点？我一直在尝试 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

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

Answer 1

您使用 map 的方式是正确的，但在遍历每个子树之后，您希望将结果列表concat在一起。使用 map 时，也没有必要用 (x:xs) 模式中断列表的第一个元素。我会把它写成:

travTree (Branch xs) = concatMap travTree xs

(但要注意；我还没有测试过!但是我经常发现我的“无限类型 a = [a]”问题是由 map 引起的，其中 concatMap是需要的。)