CODEWITHSUNDEEP
algorithmtreefunctional-programmingocamlfold
guser
guser

Reputation: 296

Weird function on trees Ocaml

A Node is called beautiful if it's value is greater than the value of any other node, which can be found on the way to the root. The problem is to count the beautiful nodes on a given tree.

Here is solution to the problem, but I can't understand the idea behind having an accumulator of functions.

Could anyone explain this solution?

open List;;

type 'a tree = Node of 'a * 'a tree list

let rec fold_tree f (Node (x, l)) =
  f x (map (fold_tree f) l);;

let beautiful_nodes t  =
  let merge x l k =
    if x < k then 
      fold_left (fun a h ->a + h k) 0 l
    else
      fold_left (fun a h ->a + h x) 0 l + 1
  in
  fold_tree merge t (-1);;

Upvotes: 1

Views: 394

Answers (2)

guser
guser

Reputation: 296

May be also useful the following interpretation. I mean the following representation of the same code where explicitly is defined the function which is accumulated. It helped me to understand the idea behind the implementation.

let beautiful_nodes tree = 
   let merge x l = (fun k ->
    if (x>k) then
        1+ fold_left (fun acc h -> acc+ h x) 0 l
    else
        fold_left (fun acc h  -> acc + h k) 0 l
                    ) 
    in  fold_tree merge tree (-1);;

Upvotes: 0

Marc
Marc

Reputation: 766

For all integer k, the function "fold_tree merge t k" returns the number of beautiful nodes in t with value greater than k. Let's call this hypothesis H(t).

(Note that if you suppose all values are positive, then "fold_tree merge -1" returns the number of beautiful nodes (or "fold_tree merge 0" !)).

From the definitions, the following pseudo-code equation holds:

fold_tree merge (Node (x, [son1; son2; ...])) k = if x < k then sum ([fold_tree merge son1 k; fold_tree merge son2 k; ...])) else 1 + sum ([fold_tree merge son1 x; fold_tree merge son2 x; ...]))

Now you should be able to convince yourself that if H(son1), H(son2), ... holds then H(Node(x, [son1; son2; ...])) holds as well.

There are two cases:

  1. x < k, then the beautifuls nodes in Node(x, [son1; son2; ...]) of value greater than k are exactly the beautiful nodes of value greater than k in son1, son2, ... (because the root is not greater than x).

  2. x >= k, then beautifuls nodes in Node(x, [son1; son2; ...]) of value greater than k are:

    • The root (root are always beautiful),
    • The beautifuls nodes in son1, son2, ... of value greater than x.

So by induction on the size of trees, it H(t) is true for all t.

Upvotes: 1

Related Questions