OCaml中的fold_tree

Question

正如你可能知道的，OCaml中有更高阶的函数，如fold_left，fold_right，filter等。

在我的函数式编程课程中，我介绍了一个名为fold_tree的函数，它类似于fold_left/right，不是在列表上，而是在(二进制)树上。它看起来是这样的：

 let rec fold_tree f a t = 
  match t with
    Leaf -> a |
    Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);;

其中，树定义为：

type 'a tree = 
  Node of 'a tree * 'a * 'a tree | 
  Leaf;;

好的，这是我的问题: fold_tree函数是如何工作的？你能给我举一些例子，用人类语言解释一下吗？

Answer 1

让我们以树为例。

let t = Node (Node (Leaf, 10, Leaf), 1, Node (Node (Leaf, 20, Leaf), 11, Leaf))

fold操作的一般定义是在树中的任何地方用函数替换构造函数。

general_fold_tree node leaf t =
    node (node leaf 10 leaf) 1 (node (node leaf 20 leaf) 11 leaf)

node是一个从左边的东西、元素和右边的东西构造一个东西的函数，就像Node是一个从左子树、节点内容和右子树构造树的构造器一样。leaf是一个常量，与Leaf常量构造函数相匹配。

let rec general_fold_tree (node : 'b -> 'a -> 'b -> 'b) (leaf : 'a) (t : 'a tree) : 'b =
  let recurse t = general_fold_tree node leaf t in
  match t with
  | Node (l, x, r) -> node (recurse l) x (recurse r)
  | Leaf -> leaf

注意，函数的类型与类型定义的类型相匹配，除了类型定义描述'a tree的构建，而fold函数描述任何'b的构建。

看起来很像普通折叠的操作仍然被称为折叠。例如，在列表中，根据上面的定义，List.fold_right是通用的fold；List.fold_left是反过来应用函数的变体(fold_left等同于reverse + fold_right + reverse，尽管它更清晰、更有效)。

您自己的fold_tree是这个通用文件夹的简单变体，其中节点函数以不同于构造函数的顺序接受参数：

let equrts_fold_tree f a t =
  let node l x r = f x l r in
  general_fold_tree node a t

Answer 2

下面是一种在列表上考虑fold_right的方法:例如，列表

(1 :: (2 :: (3 :: [])))

然后用一个新的二元运算代替:：(和一个代替[]的新常量)重新解释这个列表。

fold_right (+) l 0 = (1 + (2 + (3 + 0)))

如果您不想对列表执行任何操作，可以将函数cons作为函数传递，并将空列表作为中性元素传递。因此，在某种意义上，fold_right是非常通用的:它甚至允许您完全不丢失任何信息。

您问题中的fold_tree与树的数据类型的概念相同。如果你想重新解释你的树，你给它传递一个新的节点函数，这个函数将被应用，而不是构造函数Node。如果你想得到一个完全相同的树，你可以用Leaf作为中立函数，(fun x l r -> Node (l, x, r))作为函数。与列表的fold_left类似，这个示例应用程序不是很有趣，但它意味着fold_left是一个非常通用的转换(技术术语是morphism)。

例如，您还可以使用函数(fun x l r -> x + l + r)对树的元素求和。

Answer 3

看起来f是一个三参数约简函数，a是我们约简的中性元素，t是根，所以：

给出一个像这样的二进制(我不太记得变量类型的语法，所以请在这里居高临下)

let r = Node(Node(Node(Leaf,3,Leaf),2,Node(Leaf,4,Leaf)),1,Node(Node(Leaf,6,Leaf),5,Node(Leaf,7,Leaf)))

如果要对所有节点求和，则该函数的调用方式如下：

let add x y z = x + y + z
fold_tree add 0 r

我们会将t作为一个节点进行匹配，所以我们有：

(add 1 (fold_tree add 0 Node(Node(Leaf,3,Leaf),2,Node(Leaf,4,Leaf))) (fold_tree add 0 Node(Node(Leaf,6,Leaf),5,Node(Leaf,7,Leaf))))

如果我们进一步扩展它，我们得到：

(add 1 (add 2 (fold_tree add 0 Node(Leaf,3,Leaf)) (fold_tree add 0 Node(Leaf,4,Leaf))) (add 5 (fold_tree add 0 Node(Leaf,6,Leaf)) (fold_tree add 0 Node(Leaf,7,Leaf))))

再一次，我们匹配树叶：

(add 1 (add 2 (add 3 0 0) (add 4 0 0)) (add 5 (add 6 0 0) (add 7 0 0))
(add 1 (add 2 3 4) (add 5 6 7))
(add 1 9 18)

要最终获得：

28

希望能有所帮助。