此折叠树函数在 Haskell 中的工作原理

Question

在这里，我试图理解这个将一棵树折叠成一个值的函数。它表明 foldTree 将两个函数作为参数，它将第一个函数应用于 Tree a 的元素，然后将结果传递给第二个函数 (b->b->b)，后者再次执行一些操作并产生最终结果。

foldTree :: (a -> b) -> (b -> b -> b) -> Tree a -> b
foldTree f g (Leaf x) = f x
foldTree f g (Node tl tr) = g (foldTree f g tl) (foldTree f g tr)

我正在尝试按照输入来查看它是如何工作的。

Input 1:  foldTree (*2) (\x y -> x + y) (Leaf 6)
Input 2:  foldTree (*2) (\x y -> x + y) (Node (Node (Leaf 1) (Leaf 2)) (Leaf 4))

它returns

Output 1 : 12
Output 2 : 14

我在理解中遇到的问题是第二个函数参数操作在哪里执行？以及它实际上如何将值传递给第二个函数，显然第二个函数将两个值作为参数但第一个函数仅 returns 一个值......从哪里传递第二个值？我可以说第一个函数的结果两次使得 x 和 y 值相同吗？因为第二个函数 (\x y -> x + y) 需要两个个参数？但结果将与输出 1 和 2 中提到的不同。

第二次执行 return 执行第二个函数后的最终结果，或者 return 仅应用第一个函数后的结果，因为我很困惑，即使我删除了第二个函数，它也会产生相同的结果.

第三，两个大括号外的g的目的是什么？ ***g*** (foldTree f g tl) (foldTree f g tr) 它从一开始就把它当作数据构造函数还是什么？我知道数据构造函数可以构造为智能构造函数，但这里是如何处理的。

我对这个理解很困惑，可能是我在这个问题上把很多概念复杂化了？请不要犹豫，详细说明。

Answer 1

要了解 foldTree f g tree 的结果，您可以使用此技巧：

使用构造函数写下 tree 的值，例如在您的示例中，我们有 (Node (Node (Leaf 1) (Leaf 2)) (Leaf 4)).
在句法上将 Leaf 替换为 f，将 Node 替换为 g。对于前面的示例，我们得到 (g (g (f 1) (f 2)) (f 4)).
使用函数 f 和 g 的定义来计算最后一个表达式的结果。例如，我们得到 ((+) ((+) ((*2) 1) ((*2) 2)) ((*2) 4)) 这是 ((+) ((+) (1*2) (2*2)) (4*2)) 即 ((1*2) + (2*2)) + (4*2) 即 (2+4)+8 = 14.

请注意我们如何将一元构造函数 Leaf 替换为一元函数 f，将二元构造函数 Node 替换为二元函数 g。所以，我们的函数总是有正确数量的参数。更一般地说，类型会很好地匹配。

此折叠树函数在 Haskell 中的工作原理

How this Fold Tree Function works in Haskell

tree

haskell

fold