树的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)

它确实有效.

我看不出第一个功能和第二个功能之间的区别.我怎么得到错误？谢谢.

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)

Answer 2

请注意,这显然fmap是Functor您的Tree类型的实例.因此,您可以使用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足够的参数.定义maptree f (Node xl xr)说maptree有两个参数,一个函数和一个树.但是当你把它称之为时maptree xl,你只给它一个参数(一棵树).

在第二个版本中,您已定义maptree为只接受一个参数(树),这就是它不会产生该错误的原因.

您可以通过调用maptree f xl而不是调用来解决问题maptree xl.

Answer 4

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

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)

在第一个示例中，我使用gosort of 作为maptree f. 在第二个示例中，我利用了这样一个事实，即maptree的输入f在go函数内部的范围内，因为它go是在 的where子句中声明的maptree。