8

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

4

5 回答 5

8

这是一个风格建议，将横杠放在行首。它使案件从哪里开始变得更加清晰。为了保持一致性，第一个栏是可选的，但建议使用。

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

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

于 2010-11-15T23:10:25.017 回答
5

让我们举一个例子树。

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

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

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

node是一个从左子树、节点内容和右子树构造树的构造函数，它从左子树、元素和右子树构造某物。是一个常量，匹配常量构造函数。NodeleafLeaf

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，折叠函数描述了任何的构建'b。

看起来很像一般折叠的操作仍然称为折叠。例如，在列表上，List.fold_right是根据上述定义的一般折叠；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
于 2010-11-16T00:39:49.780 回答
4

这是一种考虑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)。

于 2010-11-15T23:12:03.890 回答
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

希望能帮助到你。

于 2010-11-15T22:58:26.547 回答
3

你可能会喜欢阅读

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

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

它们在 F# 中，但 F# 与 OCaml 非常相似。

于 2010-11-16T02:01:32.240 回答