fold_tree OCaml中

Question

正如你可能知道，有OCaml中高阶函数，如fold_left，fold_right，过滤等

在我的函数式编程过程中已经引入的功能命名fold_tree，这是一样的东西fold_left /对，不在列表上，但在（二进制）树上。它看起来像这样：

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

OK，这里是我的问题：请问在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，它将存储的值和折叠左右子树的结果相结合。在这种情况下，我们只是添加每个叶子作为一个的数字。折叠这棵树的结果是10。

Answer 2

看来f是三个参数还原功能，a是我们减少的中性元素，t是根，所以：

给予相同的二进制（我不记得很清楚的语法变异类型，因此，请在这里condescendent）

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 

希望它有帮助。

Answer 3

这里有一个方法来思考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 4

我们以树为例。

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的建筑物中，折叠功能描述了任何'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 

Answer 5

你可能会喜欢读

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

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

哪些在F＃中，但F＃非常相似到OCaml。