Ocaml - wrong type

Question

I want check if tree is balanced (It means that each leaf is on the same depth) but I have problem with wrong type.

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 is_balanced t =
  fst(
    fold_tree 
      (fun _ (l: (bool * int) list ) ->  
        ((fold_left
           (fun h (flag,first_value)-> 
             ((fst h)=first_value)&&flag,first_value)
           (true,snd(hd l) ) 
           l))
       )
   t);;

The problem is there:

((fold_left(fun h (flag,first_value)-> ((fst h)=first_value)&&flag,first_value) (true,snd(hd l) ) l))

Ocaml tells me that this is type of bool * bool but I am convinced that this is type of bool * int because l is type of (bool * int) list so hd l is type of (bool * int) so snd(hd l) is type of int...

octachron octachron · Accepted Answer · 2018-11-12T13:59:15

Some pieces of advice:

Name your intermediary functions
Avoid opening List
Avoid using List.hd (in order properly handle the empty list case)
Believe the typechecker
Use type annotations when debugging with the typechecker help

In your case, you should have a look at the type of your inner function

fun (h:'a) (flag,first_value): 'a-> 
  (fst h=first_value) && flag,first_value

Ocaml - wrong type

1 Answers