Haskell n元树遍历

Question

我是一个新手Haskell程序员，正在尝试遍历一颗N叉树。输出结果应该是一个叶子值的列表（因为分支没有值），所以对于测试树来说，输出应该是：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

任何帮助都将不胜感激，提前表示感谢..！

- Matt

Answer 1

使用 map 是正确的方法，但是在遍历每个子树后，您需要将生成的列表 concat 起来。当使用 map 时，也没有必要使用 (x:xs) 模式分离出列表的第一个元素。我会这样写：

travTree (Branch xs) = concatMap travTree xs

(但要注意，我还没有测试过这个！不过我经常发现我的“无限类型 a = [a]”问题是由于使用了 map 而需要使用 concatMap 导致的。)

- Nefrubyr

---

另外：需要 a (++) 的地方使用 a (:)。 - Nathan Shively-Sanders

谢谢！我希望它是一些简单的东西，很高兴我没有太远出错 :-) - Matt

Answer 2

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

这意味着：

travTree (Branch branches) = concat $ map travTree branches

请注意，即使有更简洁的符号表示方式，例如branches >>= travTree或concatMap travTree branches，用于此定义的右侧，但我认为上面的方法最清晰明了。

编辑：为了完整起见，重新引入列表推导式版本。

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

- Dario

---

你用列表推导式的第一次回答很好，但很高兴看到你也同意我的回答！ - Nefrubyr

你也可以使用concatMap ;) - hiena

我喜欢这个解决方案，因为它将它分解了一些。我同意，它比 concatMap 函数更清晰。我也喜欢列表推导式（尽管最初可能会更复杂一些），所以再次感谢！ :-) - Matt

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]

这个案例将一个 Tree 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]--你正在给它一个树的列表，而它期望一个单一的树。

你可以通过使用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]。

其他回答已经正确指出，在这里解构是没有意义的，但我希望通过明确类型来帮助你理解如何在脑海中模拟类型推断。这样你就可以找出类似问题的错误原因。

- Nathan Shively-Sanders

---

非常感谢您，这真的解决了很多问题，我非常感激！一旦我读完这篇文章，其他解决方案就变得更加清晰易懂了。 - Matt

这很好。那些“无法构造无限类型：a = [a]”错误一开始就非常令人困惑，而你的答案清楚地解释了这个问题的根源。 - Ian Ross