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。