Haskell 树木地图

Question

我的树是由

data Tree a = Leaf a | Node (Tree a) (Tree a) 
        deriving (Show)

我还声明一个测试树定义的。

myTree = Node (Node (Leaf 1) (Leaf 2)) (Leaf 3)

我想要做的是创建一个函数 maptree f 它将作用于 Leaf。更具体地说，fx = x +1，

那么maptree f myTree将返回

Node (Node (Leaf 2) (Leaf 3)) (Leaf 4)

我的解决方案是，

maptree f (Leaf a)= Leaf (f a)
maptree f (Node xl xr ) = Node (maptree xl) (maptree xr)

但它会返回以下错误

Couldn't match expected type `Tree a'
       against inferred type `Tree t -> Tree t'
Probable cause: `maptree' is applied to too few arguments
In the first argument of `Node', namely `(maptree xl)'
In the expression: Node (maptree xl) (maptree xr)

失败，模块已加载：无。

然而，如果我这样做的话，

maptree (Leaf a)= Leaf ( a + 1)
maptree (Node xl xr ) = Node (maptree xl) (maptree xr)

它确实有效。

我看不出第一个功能和第二个功能之间的区别。我如何得到错误？谢谢。

Answer 1

您缺少递归映射树调用上的函数：

maptree f (Leaf a)= Leaf (f a) 
maptree f (Node xl xr ) = Node (maptree xl) (maptree xr)

应该是

maptree f (Leaf a)= Leaf (f a) 
maptree f (Node xl xr ) = Node (maptree f xl) (maptree f xr)

Answer 2

请注意，这是 Tree 类型的 Functor 实例的明显 fmap。因此，您可以使用 DeriveFunctor 扩展让 GHC 为您生成它。

{-# LANGUAGE DeriveFunctor #-}
data Tree a = Leaf a | Node (Tree a) (Tree a) 
    deriving (Functor, Show)

我们来试试吧。

*Main> fmap (+1) (Node (Node (Leaf 1) (Leaf 2)) (Leaf 3))
Node (Node (Leaf 2) (Leaf 3)) (Leaf 4)

Answer 3

当您更深地递归时（对于这种高阶函数），不忘记传递函数的一种愚蠢方法是使用助手：

maptree f (Leaf a)     = Leaf (f a)
maptree f (Node xl xr) = Node (go xl) (go xr)
    where go = maptree f

或者，或者（也许更常见）：

maptree f tree = go tree                      -- or eta reduce:   maptree f = go
    where go (Leaf a)     = Leaf (f a)
          go (Node xl xr) = Node (go xl) (go xr)

在第一个示例中，我使用 go 有点像 maptree f 的宏。在第二个示例中，我利用了 maptree 的输入 f 位于 go 函数内部的事实，因为 go 在 maptree 的 where 子句中声明。

Answer 4

错误消息基本上告诉您出了什么问题：您没有传递 maptree 足够的参数。定义maptree f (Node xl xr) 表示maptree 接受两个参数：一个函数和一棵树。但是，当您像 maptree xl 那样调用它时，您只给它一个参数（一棵树）。

在第二个版本中，您将 maptree 定义为仅接受一个参数（一棵树），这就是它不会产生该错误的原因。

例如，您可以通过调用 maptree f xl 而不是 maptree xl 来解决问题。