4

我无法让我的代码对树进行预排序遍历到列表才能工作。树的定义如下：

data Tree a b = Branch b (Tree a b) (Tree a b)
          | Leaf a

我对前序遍历的定义如下：

preorder  :: (a -> c) -> (b -> c) -> Tree a b -> [c]
preorder f g (Leaf b) = [g b]
preorder f g (Branch a left right) = [f a] ++ preorder f g left ++ preorder f g right

但是我得到的错误是：

Couldn't match type `b' with `a'
  `b' is a rigid type variable bound by
      the type signature for
        preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c]
  `a' is a rigid type variable bound by
      the type signature for
        preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c]
In the first argument of `f', namely `a'
In the expression: f a
In the first argument of `(++)', namely `[f a]'

我知道我的问题是该函数的第一个参数的类型以及它需要如何成为 [c] 类型，但我一生无法弄清楚如何得到它。我已经尝试了 fa 周围的所有括号组合，没有括号，没有一个让我成功运行。

4

1 回答 1

4

你把你的类型或函数调用弄混了——可能是类型，给定你命名变量的方式。

您已经说过 that在它的第一个参数中Tree a b有 a b，但是 to 的f参数preorder需要一个a. 同样Leaf需要一个，a但你正在调用g它，它需要一个b.

这就是错误消息告诉您的内容：您传递给的第一个参数f是 type b，而它期望的是a.

如果您将数据类型更改为：

data Tree a b = Branch a (Tree a b) (Tree a b)
              | Leaf b

然后你的代码编译得很好。

或者更改preorder为

preorder  :: (a -> c) -> (b -> c) -> Tree a b -> [c]
preorder f g (Leaf a) = [f a]
preorder f g (Branch b left right) = [g b] ++ preorder f g left ++ preorder f g right
于 2014-10-07T05:07:11.460 回答