这个折叠树函数在哈斯克尔中是如何工作的

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二进制函数。因此，我们的函数总是有正确数量的参数。更一般地说，类型会匹配得很好。