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的括号的所有组合并且没有括号，也没有给我一个成功的跑步。

Answer 1

您已经将您的类型或函数调用混合起来 - 可能是类型，因为您已命名变量。

你说Tree a b在其第一个参数b，但f参数preorder需要一个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