Haskell先序遍历树并转换为列表

Question

我有些困难，无法让我的代码将树的先序遍历转换为列表。树的定义如下：

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]，但我无论如何都想不出该如何获取它。我已经尝试了f、a周围所有可行的括号组合，但没有一种可以成功运行。

- user3369628

Answer 1

您将类型或函数调用混淆了 - 可能是类型，鉴于您命名变量的方式。

您说 Tree a b 在其第一个参数中具有 b，但 preorder 的 f 参数需要一个 a。同样，Leaf 接受一个 a，但您正在对其调用 g，而该函数需要一个 b。

这就是错误消息告诉您的内容：您传递给 f 的第一个参数是类型为 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

- GS - Apologise to Monica

---

非常感谢，我没有意识到我已经翻转了它们。我对Haskell还比较新。 - user3369628