The magic code for traversing a binary level tree - what's going on?
We have a definition of a binary tree:
type 'a tree =
| Node of 'a tree * 'a * 'a tree
| Null;;
And also a useful function for traversing the tree "
let rec fold_tree f a t =
match t with
| Null -> a
| Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);;
And here is a "magic" function that, when specifying a binary tree, returns a list in which we have lists of elements at certain levels, for example, when specifying a tree:
(source: ernet.in )
the function returns [[1]; [2; 3]; [4; five; 6; 7]; [8; nine]].
let levels tree =
let aux x fl fp =
fun l ->
match l with
| [] -> [x] :: (fl (fp []))
| h :: t -> (x :: h) :: (fl (fp t))
in fold_tree aux (fun x -> x) tree [];;
And obviously it works, but I can't seem to focus on it. Can anyone explain in simple terms what is happening? Why does this feature work?
source to share
How do you combine two lists of layers from two subtrees and get the list of layers of the bugger tree? Suppose you have this tree
a
/ \
x y
where x
and y
are arbitrary trees, and they have layer lists as [[x00,x01,...],[x10,x11,...],...]
and [[y00,y01,...],[y10,y11,...],...]
respectively.
The list of layers of the new tree will be [[a],[x00,x01,...]++[y00,y01,...],[x10,x11,...]++[y10,y11,...],...]
. How does this function create it?
Look at this definition
let rec fold_tree f a t = ...
and see what arguments we go to fold_tree
in our definition levels
.
... in fold_tree aux (fun x -> x) tree []
So the first argument aux
is some kind of long and complicated function. We'll come back to it later.
The second argument is also a function - the identity function. This means it fold_tree
will also return a function because it fold_tree
always returns the same value type as the second argument. We will argue that the function applied to this set of arguments fold_tree
takes a list of layers and adds the layers of the given tree to it.
The third argument is our tree.
Wait, what's the fourth argument? fold_tree
should only get a tree? Yes, but since it returns a function (see above), this function is applied to that fourth argument, an empty list.
So back to aux
. This function aux
takes three arguments. One of them is a tree element, and the other two are the results of subtree folds, i.e. Refund any fold_tree
. In our case, these two things are functions again.
So, it aux
gets a tree element and two functions and returns another function. What function is this? It takes a list of layers and adds the layers of the given tree to it. How does this happen? It adds the root of the tree to the first item (which is the top layer) of the list, and then adds the layers of the right subtree to the tail of the list (which is all the layers below the top) by calling the right function on it, and then adds the layers of the left subtree to the result by calling on it left function. Or, if the incoming list is empty, it is simply a list of layers again, applying the above step to empty lists.
source to share