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。更具体地说，f x = 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)

它确实有效。

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

- DB Tsai

---

现在我搞定了，我太傻了...>< - DB Tsai

应该使用maptree f (Node xl xr) = Node (maptree f xl) (maptree f xr)代替maptree f (Node xl xr) = Node (maptree xl) (maptree xr)。 - DB Tsai

Answer 1

你在递归调用maptree时缺失了函数:

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)

- KQ.

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)

- hammar

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子句中声明的。

- Dan Burton

Answer 4

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

在你的第二个版本中，你已经定义 maptree 只接受一个参数(一棵树)，这就是为什么它不会产生那个错误的原因。

你可以通过例如这样调用 maptree f xl 而不是 maptree xl 来解决你的问题。

- Judah Jacobson