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);;
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:
x >= k, then beautifuls nodes in Node(x, [son1; son2; ...]) of value greater than k are:
So by induction on the size of trees, it H(t) is true for all t.