如何使用foldTree实现符合指定规则的zipTree函数

实现思路 #

你之前的思路是对的：对第一棵树调用foldTree返回函数来操作第二棵树，只需要把foldTree的结果类型定义为Tree a -> Tree b的函数类型即可。
我们用foldTree遍历第一棵树的结构时：

• 当第一棵树是Leaf，返回的函数不管接收到什么第二棵树，都直接返回Leaf
• 当第一棵树是分支节点，返回的函数会判断第二棵树的结构：如果第二棵树是Leaf就返回Leaf，否则合并两个节点的根值，用左/右子树折叠生成的对应函数去合并两棵树的左/右子节点

完整实现代码 #

zipTree :: (a -> a -> b) -> Tree a -> Tree a -> Tree b
zipTree merger tree1 tree2 = foldTree leafHandler branchHandler tree1 tree2
  where
    -- 第一棵树为Leaf时的处理逻辑
    leafHandler = \_ -> Leaf
    -- 第一棵树为分支节点时的处理逻辑
    branchHandler rootVal leftZip rightZip = \secondTree -> case secondTree of
      Leaf -> Leaf
      Branch secondRoot left2 right2 -> Branch (merger rootVal secondRoot) (leftZip left2) (rightZip right2)

逻辑说明 #

这个实现的逻辑和你写的手动递归版本完全等价，只是把递归遍历第一棵树的逻辑交给了foldTree完成，避免了手动模式匹配树结构的重复代码。

代入你给出的测试输入验证：

zipTree (+) (Branch 1 Leaf (Branch 2 Leaf Leaf)) (Branch 3 Leaf Leaf)

1. 第一棵树的根节点值为1，对应返回的函数接收第二棵树Branch 3 Leaf Leaf
2. 合并根节点值1+3=4
3. 第一棵树的左子树是Leaf，对应leftZip函数处理第二棵树左子树Leaf返回Leaf
4. 第一棵树的右子树是分支节点，对应rightZip函数处理第二棵树右子树Leaf返回Leaf
   最终输出结果为Branch 4 Leaf Leaf，和预期一致。

内容的提问来源于stack exchange，提问作者Peter