OCaml中的fold_tree

你可能知道，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 函数如何工作？你能给我一些例子并用人类语言解释一下吗？

这是一个样式建议，将条形放在行的开头。它使案件从哪里开始变得更清楚。为了保持一致性，第一个栏是可选的，但建议使用。

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

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);;

至于它是如何工作的，请考虑以下树：

let t = Node(Leaf, 5, Node(Leaf, 2, Leaf));;

随类型int tree.

从视觉上看，t看起来像这样：

   5
  / \
 ()  2
    / \
   () ()
  

调用fold_tree，我们需要一个函数来组合这些值。根据中的用法Node case, f接受 3 个参数，所有参数都与树的类型相同，并且返回相同的值。我们将这样做：

let f x l r = x + l + r;; (* add all together *)
fold_tree f 1 t;;

这将有助于了解每种情况下发生的情况。对于任何Leaf，返回a。对于任何Node，它将存储的值和左右子树折叠的结果结合起来。在本例中，我们只是将每片叶子算作 1 的数字相加。这棵树折叠的结果是10.