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

鉴于上述信息，我不明白树折叠功能如何
通过递归地将折叠操作应用于子树来返回结果，然后将该函数应用于根处的标签以及从子树返回的结果。

我也不明白 树折叠功能当它作为参数传递给 map 函数并且它仍然可以正确编译和运行时，只需要一个参数而不是 2。

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

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

未使用的参数

首先，将变量显式标记为未使用的方法是将变量替换为 _ .所以你真的想要:

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

curry

最后一点是在 Haskell 中柯里化(Currying)是如何工作的。当您定义如下函数时:

foo x y = x + y

...编译器实际上对两个嵌套函数进行了脱糖:

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

这就是为什么您可以在 Haskell 中仅将函数部分应用于一个参数的原因。当你写 foo 1 ，它转化为:

foo 1

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

= \y -> 1 + y

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

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

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

f (x, y) = x + y

然而，这并不是真正地道的 Haskell，它不会给你任何形式的性能改进。