Finding the height of a multiway (general tree) using OCaml

Question

As a newbie in functional programming (OCaml), I stuck with that problem.

I came up with a code shown below:

let rec height tr =
match tr with
  | Node(d,[]) -> 1 
  | Node(d,[t1]) -> 1 + height t1
  | Node(d,[t1;t2]) -> 1 + max (height t1) (height t2)

But the top-level (utop) for OCaml gives a warning:

Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
Node (_, _::_::_::_)

And when I run

let t : int gt =
Node('a',
     [Node('b',[]);
     Node('c',
      [Node('d',
        [Node('e',[])]);
      Node('f',[]);
      Node('g',[])])
     ]);;

height t;;

utop throws exception about match failure.

I also implemented this:

let rec height' tr =
match tr with
  | Node(d,[]) -> 1 
  | Node(d,_::xs) -> 1 + max (List.map height' xs) 

and it returns with

Line31 |   | Node(d,_::xs) -> 1 + max (List.map height' xs) 
                              ^^^^^^^^^^^^^^^^^^^^^^^^^
Error: This expression has type int list -> int list
       but an expression was expected of type int

In addition, I also tried another way:

let rec height tr =
match tr with
  | Node(d,[]) -> 1 
  | Node(d,[t1]) -> 1 + height t1
  | Node(d, t1::t2) -> 
  if t2=[]
  then 2
  else
  2 + height t2

then the error was:

Line26 |   2 + height t2 
                  ^^
Error: This expression has type 'a gt list
       but an expression was expected of type 'a gt

So, how can I overcome this problem?

Answer 1

Your problem

Your height function expects a value of type 'a gt. When you call height t2, t2 is the tail of a list, which is a a gt list. If you pass this to height you get a type mismatch.

How to approach this problem

Given a tree definition:

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

Writing a height function is straightforward, and I think you may be overthinking it given the number of cases in your pattern matching.

With any recursion the key is a base case. You have that:

let rec height tr =
  match
  | Node (_, []) -> 1

A node with an empty list has a height of 1. The actual data in the tree is unimportant, so we use _ in the pattern match.

The only other possibility is that the list is not empty. So we can pattern match a non-empty list. Again, the first node doesn't matter.

let rec height tr =
  match
  | Node (_, []) -> 1
  | Node (_, _::xs) -> 2 + ...

Now we have to turn a 'a gt list into an int. height will turn a 'a gt value into an int for me. So why don't I just map xs?

let rec height tr =
  match
  | Node (_, []) -> 1
  | Node (_, _::xs) -> 2 + List.map height xs

Ah, but that turns xs into an int list, which we can't add to an int. We can sum that list using fold_left.

let rec height tr =
  match
  | Node (_, []) -> 1
  | Node (_, _::xs) -> 
    let sum = List.fold_left (+) 0 in
    2 + sum (List.map height xs)

One more thing

Using the function keyword, we can simplify this.

let rec height =
  function
  | Node (_, []) -> 1
  | Node (_, _::xs) -> 
    let sum = List.fold_left (+) 0 in
    2 + sum (List.map height xs)