Depth of n-ary tree OCaml

Question

I had to calculate the depth of a n-ary tree in OCaml using only functional paradigm whitout the use of external homemade function. Here's the struc :

type nTree = 
  Id of int
  | Leaf of string
  | Tree of string * string * nTree list

and here is my result :

  let rec height t = match t with
     | Id _ -> 0
     | Leaf _ -> 0
     | Tree(_,_,n) -> if n = [] then 1
                      else let e::r = n in max 
                      (List.fold_left (fun acc x -> acc + height x) 1 [e])
                      (List.fold_left (fun acc x -> acc + height x) 1 r)

It work but I find it very ugly and the e::r bit cause a warning because of not matching the [] pattern. Is there a way to make this warning free and "prettier" ?

Thx!

Answer 1

the e::r bit causes a warning because of not matching the [] pattern

You'd just use pattern matching instead of if:

match n with
  | [] -> 1
  | e::r -> …

But actually there's no point in distinguishing these at all. You should be doing

  let rec height = function
     | Id _ -> 0
     | Leaf _ -> 0
     | Tree(_,_,n) -> 1 + List.fold_left max 0 (List.map height n)