为自定义树创建自定义折叠函数

Question

我正在尝试创建我自己的折叠功能，然后我可以在我的自定义树上使用它。

我的树很简单：

data Stem a = Node (Stem a) (Stem a) | Leaf a

我希望能够构建一个 foldTree 函数，其工作方式与 foldr 的工作方式大致相同。

我已经设法让它在 n=1 或 leaf 时使用以下

foldTree :: (x -> u -> u) -> u -> Stem x -> u
foldTree f a (Leaf o) = f o a

但我似乎无法计算出下一行（即当有节点和叶子时），我知道我需要递归调用 foldTree 但我不确定我该怎么做。我尝试了以下但我没有太多运气。

foldTree f a (Node l r) = f a (foldTree f a l) (foldTree f a r)

这不起作用，因为我知道我的参数是 x -> u -> u，所以我的参数太多了。虽然这是我卡住的地方，但我不确定如何正确遍历这两条路径。

所以我有

foldTree :: (x -> u -> u) -> u -> Stem x -> u
foldTree f a (Leaf o) = f o a
foldTree f a (Node l r) = f a (foldTree f a l) (foldTree f a r) <-- Not working

我如何更新第二行（或者方法中的其他内容才能使其正常工作？

感谢您的帮助！

Answer 1

首先处理简单的特定案例，然后将逻辑扩展到一般案例。你有一个简单的，Leaf:

foldTree f a (Leaf o) = f o a

然后想想如果有一个 Node 只有两个 Leaf 的情况下您想发生什么：

foldTree f a (Node (Leaf x) (Leaf y)) = _

这里我们知道f要申请两次，但是顺序是什么？让我们从 Node 的第一个插槽中的 Leaf 开始：

foldTree f a (Node (Leaf x) (Leaf y)) = _ (f x a)

我在表达式中留下了空洞 (_)，因为当您尝试编译时 GHC 实际上会告诉您需要将什么类型的东西放到那里。在这种情况下，它会说您需要 u -> u 类型的东西，因为 f x a :: u。好吧，我们知道f :: x -> u -> u，所以我们可以写

foldTree f a (Node (Leaf x) (Leaf y)) = f _ (f x a)

现在唯一可以填补这个洞的是右叶的y，所以

foldTree f a (Node (Leaf x) (Leaf y)) = f y (f x a)

但我们知道 f x a 与 foldTree f a (Leaf x) 相同，因此我们可以将其替换为：

foldTree f a (Node (Leaf x) (Leaf y)) = f y (foldTree f a (Leaf x))

然后用一个变量替换Leaf x：

foldTree f a (Node left (Leaf y)) = f y (foldTree f a left)

如果你眯着眼睛仔细观察，你会再次看到同样的图案。只需快速替换

foldTree f a (Node left (Leaf y)) = f y a'
  where a' = foldTree f a left

现在您可以进行替换了

foldTree f a (Node left right) = foldTree f a' right
  where a' = foldTree f a left

而整个定义是

foldTree f a (Leaf x) = f x a
foldTree f a (Node left right) = foldTree f (foldTree f a left) right

为自定义树创建自定义折叠函数

Creating a Custom Fold Function for Custom Tree

haskell

fold