fold_tree in OCaml

As You may know, there are higher order functions in OCaml, such as fold_left, fold_right, filter etc.

On my course in functional programming had been introduced function named fold_tree, which is something like fold_left/right, not on lists, but on (binary) trees. It looks like this:

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

Where tree is defined as:

type 'a tree = 
  Node of 'a tree * 'a * 'a tree | 
  Leaf;;

OK, here's my question: how does the fold_tree function work? Could you give me some ex开发者_如何转开发amples and explain in human language?

Here's a style suggestion, put the bars on the beginning of the line. It makes it clearer where a case begins. For consistency, the first bar is optional but recommended.

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

As for how it works, consider the following tree:

let t = Node(Leaf, 5, Node(Leaf, 2, Leaf));;

With the type int tree.

Visually, t looks like this:

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

And calling fold_tree, we'd need a function to combine the values. Based on the usage in the Node case, f takes 3 arguments, all the same type of the tree's and returns the same. We'll do this:

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

It would help to understand what happens in each case. For any Leaf, a is returned. For any Node, it combines the stored value and the result of folding the left and right subtrees. In this case, we're just adding the numbers where each leaf counts as one. The result on the folding of this tree is 10.

Let's take an example tree.

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

The general definition of a fold operation is that you replace constructors by functions, everywhere in the tree.

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

node is a function that constructs a something from a left something, an element and a right something, just like Node is a constructor that constructs a tree from a left subtree, a node content and a right subtree. leaf is a constant, matching the Leaf constant constructor.

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

Notice that the types of the functions match those of the type definition, except that where the type definition describes the building of an 'a tree, the fold function describes the building of any 'b.

Operations that look a lot like the general fold are still called fold. For example, on lists, List.fold_right is the general fold according to the definition above; List.fold_left is a variation that applies the function the other way round (fold_left is equivalent to reverse + fold_right + reverse, though it's clearer and more efficient).

Your own fold_tree is a simple variation of this general fold where the node function takes its arguments in a different order from the constructor:

let equrts_fold_tree f a t =
  let node l x r = f x l r in
  general_fold_tree node a t

Here is a way to think about fold_right on lists: a list is for instance

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

and you re-interpret the list with a new binary operation in place of :: (and a new constant instead of []).

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

If you wanted to do absolutely nothing to your list, you could pass the function cons as the function and the empty list as the neutral element. So in a sense, fold_right is very general: it even allows you not to lose any information at all.

The fold_tree in your question is the same idea for the datatype of trees. If you want to re-interpret your tree, you pass it a new function for nodes that will be applied instead of the constructor Node. If you wanted to get an identical tree, you could apply it with Leaf as neutral and (fun x l r -> Node (l, x, r)) as function. Similarly to fold_left for lists, this example application is not very interesting, but it means that fold_left is a very general transformation (the technical term is morphism).

You can also sum the elements of the tree with the function (fun x l r -> x + l + r), for instance.

You might enjoy reading

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

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

which are in F#, but F# is very similar to OCaml.

It seems that f is a three parameter reduction function, a is the neutral element of our reduction, and t is the root, so:

given a binary like (I don't remember very well the syntax of variant types, so please be condescendent here)

let r = Node(Node(Node(Leaf,3,Leaf),2,Node(Leaf,4,Leaf)),1,Node(Node(Leaf,6,Leaf),5,Node(Leaf,7,Leaf)))

if you want to sum all the nodes, the function will be called like:

let add x y z = x + y + z
fold_tree add 0 r

and we'll get t matched as a node, so we have:

(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))))

if we expand it a little bit more, we get:

(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))))

and once more, we are matching the leaves:

(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)

to finally get:

28

Hope it helps.