functional programming - fold_tree in OCaml -

as may know, there higher order functions in ocaml, such fold_left, fold_right, filter etc.

on course in functional programming had been introduced function named fold_tree, fold_left/right, not on lists, on (binary) trees. looks this:

 let rec fold_tree f t =    match t     leaf -> |     node (l, x, r) -> f x (fold_tree f l) (fold_tree f r);; 

where tree defined as:

type 'a tree =    node of 'a tree * 'a * 'a tree |    leaf;; 

ok, here's question: how fold_tree function work? give me examples , explain in human language?

here's style suggestion, put bars on beginning of line. makes clearer case begins. consistency, first bar optional recommended.

type 'a tree =    | node of 'a tree * 'a * 'a tree   | leaf;;  let rec fold_tree f t =      match t       | leaf ->       | node (l, x, r) -> f x (fold_tree f l) (fold_tree f r);; 

---

as how works, consider following tree:

let t = node(leaf, 5, node(leaf, 2, leaf));; 

with type int tree.

visually, t looks this:

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

and calling fold_tree, we'd need function combine values. based on usage in node case, f takes 3 arguments, same type of tree's , returns same. we'll this:

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

it understand happens in each case. leaf, returned. node, combines stored value , result of folding left , right subtrees. in case, we're adding numbers each leaf counts one. result on folding of tree 10.