树上的haskell折叠操作

Question

data Tree a = Tree a [Tree a] 

请注意，我们不允许空树，并且叶子是具有空子树列表的树。

treeFold :: (a -> [b] -> b) -> Tree a -> b 
treeFold f (Tree x s) = f x (map (treeFold f) s) 

鉴于上述信息，我不明白是怎么树折叠功能 通过递归地施加折叠操作的子树，然后在根和结果应用的功能标签返回结果从子树返回。

我也不明白树折叠函数只有一个参数而不是2，当它作为参数传递给map函数，它仍然编译和正常运行。

例如，树大小函数下面，计数树的节点。

treeSize :: Tree a -> Int 
treeSize = treeFold (\x ys -> 1 + sum ys) 

所以运行的TreeSize树其中tree = Tree 4 [Tree 1 [Tree 2 [], Tree 3 []]]给出了树的大小为4

在树尺寸功能以上，树折叠功能也被传递一个参数，而不是两个。另外，传递给树折叠函数的x在任何地方都没有被使用，所以你为什么需要它。删除它会导致程序无法编译，并提供以下错误消息。

Couldn't match type `a' with `[[Int] -> Int]' 
     `a' is a rigid type variable bound by 
      the type signature for treeSize :: Tree a -> Int 
      at treeFold.hs:15:1 
    In the first argument of `sum', namely `ys' 
    In the second argument of `(+)', namely `sum ys' 
    In the expression: 1 + sum ys 

任何帮助将不胜感激。

Answer 1

第一个问题有点棘手，因为这是递归的东西......正如老师所说：“要理解递归，你必须学习，递归如何工作”。 :-P 一个小建议：尝试通过应用treeFold与一棵树或一棵树与一棵树内，并由您自己（在纸上或其他）评估它。我认为，那么你可以感觉到发生了什么......（当然，使用一个简单的函数作为treeFold的参数;就像你的treeSize使用的那样）。

treeFold仅得到一个在地图的身体参数，因为map需要从a->b功能，并treeFold有型(a -> [b] -> b) -> Tree a -> b.，所以如果你将它传递2个参数，将传递给map只有一个值，这导致失败。 （+）需要两个参数，如果你写map (+1) [1,2,3]，你会得到[2,3,4] ，因为（+1）应用于列表中的每个元素（和（+1）显然需要多一个参数，您treeFold f以上）

你的榜样的TreeSize： 这是不对的，当你说，它只得到一个参数你可以写

treeSize t = treeFold (\x ys -> 1 + sum ys) t 

，而不是你定义上面 的x不是。因为用于计数是没用的。但是，treeFoldn eeds有一个函数，它有两个参数，所以你给它的x。这是唯一的原因。您可以传递任何其他值。

Answer 2

未使用变

首先，明确标记变量为未使用的是_替换变量的方式。所以，你真的想：

treeFold (\_ ys -> 1 + sum ys) 

，因为你写你有一个编译器错误：

treeFold (\ys -> 1 + sum ys) 

...这是不一样的东西。

褶皱

其次，我会用手上的例子树评估treeSize所以你可以看到，有没有神奇的事情：

treeSize (Tree 1 [Tree 2 [], Tree 3 []]) 

-- Inline definition of 'treeSize' 
= treeFold (\_ ys -> 1 + sum ys) (Tree 1 [Tree 2 [], Tree 3 []]) 

-- Evaluate treeFold 
= (\_ ys -> 1 + sum ys) 1 (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []]) 

-- Apply the anonymous function 
= 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []]) 

-- Apply the 'map' function 
= 1 + sum [ treeFold (\_ ys -> 1 + sum ys) (Tree 2 []) 
      , treeFold (\_ ys -> 1 + sum ys) (Tree 3 []) 
      ] 

-- Apply both 'treeFold' functions 
= 1 + sum [ (\_ ys -> 1 + sum ys) 2 (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      , (\_ ys -> 1 + sum ys) 3 (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      ] 

-- Apply the anonymous functions 
= 1 + sum [ 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      , 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      ] 

-- map f [] = [] 
= 1 + sum [ 1 + sum [] 
      , 1 + sum [] 
      ] 

-- sum [] = 0 
= 1 + sum [1 + 0, 1 + 0] 
= 1 + sum [1, 1] 

-- Apply 'sum' 
= 1 + 2 
= 3 

然而，有一个简单的方法来记住如何treeFold作品。它所做的就是用您提供的函数替换每个Tree构造函数。

所以，如果您有：

Tree 1 [Tree 2 [Tree 3 [], Tree 4[]], Tree 5 [Tree 6 [], Tree 7 []]] 

...你申请treeFold f到，它会评估为：

f 1 [f 2 [f 3 [], f 4 []], f 5 [f 6 [], f 7 []]] 

treeSum只是特殊情况下f = (\_ ys -> 1 + sum ys)：

1 + sum [1 + sum [1 + sum [], 1 + sum []], 1 + sum [1 + sum [], 1 + sum []]] 

= 7 

Currying

最后一点是如何在Haskell中进行咖啡的工作。当你定义像函数：

foo x y = x + y 

...的编译器实际上是desugars两个嵌套函数：

foo = \x -> (\y -> x + y) 

这就是为什么你可以部分应用功能，在Haskell只是一个参数。当你写foo 1，将其转换为：

foo 1 

= (\x -> (\y -> x + y)) 1 

= \y -> 1 + y 

换句话说，它返回一个参数的一个新功能。

在Haskell中，所有函数只需要一个参数，我们通过返回新函数来模拟多个参数的函数。这种技术被称为“咖喱”。

如果你喜欢更传统的主流语言的多参数的方法，你可以通过让函数接受一个元组参数模拟它：

f (x, y) = x + y 

然而，这不是真正地道的Haskell，并赢得了”不会给你任何性能改善。