Fold_tree in OCaml

Question

As you know, in OCaml there are higher-order functions like fold_left, fold_right, filter, etc.

In my course on functional programming, I introduced a function called fold_tree, something like fold_left / right, not in lists, but on (binary) trees. It looks like this:

let rec fold_tree fat = match t with Leaf -> a | Node (l, x, r) -> fx (fold_tree fal) (fold_tree far);; 

Where the tree is defined as:

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

OK, here is my question: how does the function fold_tree work? Could you give some examples and explain human language?

Answer 1

Here's a suggestion for style, put the bars at the beginning of the line. This makes it clearer where the event 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 fat = match t with | Leaf -> a | Node (l, x, r) -> fx (fold_tree fal) (fold_tree far);; 

---

How it works, consider the following tree:

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

With type int tree .

Visually, t as follows:

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

When calling the fold_tree function, we need a function to combine the values. Based on the use in the Node case, f takes 3 arguments, all the same type of tree and returns the same. We will do the following:

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

This will help to understand what happens in each case. For any Leaf returned. For any Node it combines the stored value and the result of folding the left and right subtrees. In this case, we simply add numbers in which each sheet is considered one. The result of folding this tree is 10 .

Answer 2

Take the example of a 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 with functions throughout 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 creates something from left something, an element and something right, just like node is a constructor that builds a tree from the left subtree, the contents of the node and the right subtree. leaf is a constant corresponding to 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 

Note that function types correspond to types of type definitions, except that if the type definition describes the construction of 'a tree , the fold function describes the construction of any 'b .

Operations that look very much like a common fold are still called fold. For example, in lists, List.fold_right is the total amount as defined above; List.fold_left is a variation that applies the function in the opposite direction ( fold_left equivalent to the opposite + fold_right + the opposite, although it is more clear and efficient).

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

 let equrts_fold_tree fat = let node lxr = fxlr in general_fold_tree node at 

Answer 3

The following is an example of a description of fold_right in lists: for example, a list

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

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

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

If you do not want to do anything in your list, you can pass the cons function as a function and an empty list as a neutral element. Thus, in a sense, fold_right is very general: it even allows you not to lose information at all.

fold_tree in your question is the same idea for a data type of trees. If you want to reinterpret your tree, you pass it a new function for the nodes that will be used instead of the Node constructor. If you want an identical tree, you can apply it with Leaf as neutral and (fun xlr -> Node (l, x, r)) as a function. Like fold_left for lists, this fold_left application is not very interesting, but that means fold_left is a very general conversion (technical term is morphism ).

You can also summarize tree elements using the function (fun xlr -> x + l + r) , for example.

Answer 4

It seems that f is the function of reducing three parameters, a is the neutral element of our reduction, and t is the root, therefore:

for a binary type (I don't remember the syntax of the variant variants very well, so please be condescending)

 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 as:

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

and we get t as 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 open it a little 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 again, we map 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 this helps.

Answer 5

You may like to read

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.