having difficulties analyzing recursive steps of a function

user_10676586 0
Viewed 63

I'm currently studying OCaml for a functional programming exam and I'm having some difficulties trying to follow the steps of this recursive function in this exercise. The task is to find the most expensive leaf in a int N-ary tree (a leaf cost is given by the sum of integers on the path to a leaf).

This is the type definition:

type 'a ntree = Ntree of 'a * 'a ntree list

this is an auxiliary function for the exercise

let rec maxpair = function
  | [] -> failwith "empty list"
  | [(x, y)] -> (x, y)
  | (x, y) :: (a, b) :: rest -> 
      if y > b then maxpair ((x, y) :: rest) 
      else maxpair ((a, b) :: rest)

and finally here's the final function

let rec leaf_cost = function
  | Ntree (x, []) -> (x, x)
  | Ntree (x, tlist) -> 
      let (y, c) = maxpair (List.map leaf_cost tlist)
      in 
      (y, c + x)

This is the solution of the exercise, meaning it works. But I'm having trouble trying to analyze every recursive step in the function, especially because I'm a bit confused about the let (y, c) ... in (y, c + x) declaration.

tree recursion ocaml functional-programming
1 Answers

Given a tree, leaf_cost returns a pair (v, c) which is the value of the leaf node with the maximal cost v, and that cost c.

In the base case, when there is no child node, the value is x and its cost is also x.

In the general case, a node is made of an integer x and list of child node children (aka tlist).

List.map leaf_cost children

The above expression is a list of pairs, each one being the maximum leaf and its associated cost in the respective subtree rooted in each child node.

In general, there might be multiple leaves with the same cost, but your problem ignores that and selects, in an implementation-defined way, a pair with the maximal cost among all costs so far.

This is done by calling maxpair, which gives a pair (y, c) where y is the first leaf having the maximal cost c among all the pairs obtained recursively.

Knowing that among all subtrees, (y, c) is a leaf with cost c, and that your current node weights x, the cost of the current node is c + x. That's why the returned value in the general case is (y, c+x), keeping track of the leaf in the subtrees that lead to this cost.

user_1243190
Related