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

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

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 情况中的用法，f 采用 3 个参数，所有参数都与树的类型相同，并且返回相同的值。我们将这样做：

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

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

Answer 2

让我们举一个例子树。

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 是一个函数，它从左侧 something、一个元素和右侧 something 构造一个 something，就像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 树 的构建，而 Fold 函数描述任何 'b< 的构建/代码>。

看起来很像一般折叠的操作仍然称为折叠。例如，在列表上，List.fold_right 是根据上面定义的一般折叠； List.fold_left 是一种以相反方式应用该函数的变体（fold_left 相当于反向 + fold_right +反向，尽管它更清晰更有效率）。

您自己的 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 3

以下是考虑列表上的 fold_right 的方法：例如

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

，使用一个新的二元操作代替 ::（以及一个新的常量代替 []）来重新解释该列表。 。

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

如果您不想对列表执行任何操作，则可以将函数 cons 作为函数传递，将空列表作为中性元素传递。所以从某种意义上说，fold_right 非常通用：它甚至可以让你根本不丢失任何信息。

您问题中的 fold_tree 与树的数据类型的想法相同。如果你想重新解释你的树，你可以向它传递一个新的节点函数，而不是构造函数Node。如果您想获得一棵相同的树，可以将 Leaf 作为中性，将 (fun xlr -> Node (l, x, r)) 作为函数来应用。
与列表的 fold_left 类似，这个示例应用程序并不是很有趣，但这意味着 fold_left 是一个非常通用的转换（技术术语是 态射）。

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

Answer 4

您可能会喜欢阅读

http://lorgonblog.wordpress.com/2008/ 04/06/catamorphisms-part-two/

http: //lorgonblog.wordpress.com/2008/04/09/catamorphisms-part-third/

位于 F# 中，但 F# 与 OCaml 非常相似。

Answer 5

看起来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

希望它有帮助。