这个折叠树函数如何在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))

它回来了

Output 1 : 12
Output 2 : 14

我在理解中遇到的问题是执行第二个函数参数操作的位置？以及它如何实际将值传递给第二个函数，显然第二个函数将两个值作为参数但第一个函数只返回一个值...从第二个值传递的位置？我能说两次第一次函数的结果，以便x和y值相同吗？因为第二个函数(\x y -> x + y)有两个参数？但结果与输出1和2中提到的结果不同。

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

第三，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一元构造函数。因此，我们总是为函数提供正确数量的参数。更一般地说，类型将匹配得很好。