Unable to understand type requirement

Learning
1

Hello,

Ported Haskell code which I think is very concise to OCaml. This code creates a BTree. It seems to be fine except the type requirement of the print_bTree function.
I am trying to print to test it.

let tree  = LF in
  let tree = insert 32 tree in

  print_bTree tree 0;
 
print_bTree tree 0;
                  ^^^^
Error: This expression has type
         (('a, int) t -> 'b) ->
         (('a, int) t -> int -> ('a, int) t -> 'b) -> 'b
       but an expression was expected of type ('c, int) t

This is the code.

type ('n, 'a) n =
  | Type1 of ('n, 'a) t * 'a * ('n, 'a) t
  | Type2 of ('n, 'a) t * 'a * ('n, 'a) t * 'a * ('n, 'a) t
and ('n, 'a)  t =
  | BR of('n, 'a)  n
  | LF


type ('n, 'a ) tree = Tree of ('n, 'a ) t

type ('n, 'a, 't ) normal_replace = ('n, 'a ) t -> 't
type ('n, 'a, 't ) insert_or_pushup = ('n, 'a ) t -> 'a -> ('n, 'a ) t -> 't

type order = LESS | EQUAL | GREATER

let compare k1 k2 : order =
  if k1 < k2 then LESS
  else if k1 = k2 then EQUAL
else GREATER



let compare_normal v1 v2 v1_lessthan_V2 v1_equalto_v2 v1_greaterthan_v2 =
  match compare v2 v2 with
  | LESS -> v1_lessthan_V2
  | EQUAL -> v1_equalto_v2
  | GREATER -> v1_greaterthan_v2


let compare_pushup v1 v2 v3 v1_lessthan_V2 v1_equalto_v2 v1_between v1_equalto_v3 v1_greaterthan_v3 =
  compare_normal v1 v2 v1_lessthan_V2 v1_equalto_v2 ( compare_normal v1 v3 v1_between v1_equalto_v3 v1_greaterthan_v3 )

let insert (value:int) tree  =
  let rec ins t normal_replace insert_or_pushup =
  match t with
  | LF -> insert_or_pushup LF value LF
  | BR br  ->
    match br with
    | Type1 ( a, b, c ) ->
      let v1_lessthan_v2 =

        ins a (fun k -> normal_replace (BR (Type1 (k,b,c)))) 
              (fun p q r -> normal_replace (BR (Type2 (p, q, r, b, c )))) in

      let v1_greaterthan_v2 =

        ins c (fun k -> normal_replace (BR ((Type1 (a, b, k)))))
              (fun p q r -> normal_replace (BR ((Type2 (a, b, p, q, r ))))) in

      let v1_equalto_v2 = normal_replace (BR ((Type1 (a,  value,  c)))) in
      compare_normal value b v1_lessthan_v2 v1_greaterthan_v2 v1_equalto_v2

    | Type2( a, b, c, d, e ) -> 
      let v1_lessthan_v2 =

       ins a (fun k -> normal_replace (BR (Type2 (k,b,c,d,e)))) 
         (fun p q r -> insert_or_pushup (BR (Type1 (p, q, r))) b  (BR (Type1 (c, d, e)))) in

      let v1_between =
          ins c (fun k -> normal_replace (BR (Type2 (a,b,k,d,e)))) 
                (fun p q r -> insert_or_pushup (BR (Type1 (a, b, p))) q (BR (Type1 (r, d, a) ))) in

      let v1_greaterthan_v3 =
          ins e (fun k -> normal_replace (BR (Type2 (a,b,c,d,k)))) 
                (fun p q r -> insert_or_pushup (BR (Type1 (a, b, c))) d (BR (Type1 (p, q, r)  ))) in

      let v1_equalto_v2  = normal_replace (BR ((Type2 (a,  value,  c, d, e)))) in

      let v1_equalto_v3  = normal_replace (BR ((Type2 (a,  b, c, value,  e)))) in
      compare_pushup value b d v1_lessthan_v2 v1_between v1_greaterthan_v3 v1_equalto_v2 v1_equalto_v3


  in
  ins tree


let rec print_bTree (bTree: ('n, 'a) t) d : unit =
  begin match bTree with
  |LF -> () 
  |BR n-> 
  begin match n with
  | (Type1 ( a,b,c)) ->
    print_bTree a (d + 1);
    for __i=0 to  (d - 1) do
      Printf.printf "  "
    done;
    Printf.printf "%d \n" b;
    print_bTree c (d+1); 

  | (Type2 ( a,b,c,d,e)) ->
    print_bTree a (d + 1);
    for __i=0 to  (d - 1) do
      Printf.printf "  "
    done;
    Printf.printf "%d %d\n" b d;
    print_bTree c (d+1); 
    print_bTree e (d+1); 
  end;
  end;

Thanks.

2

normal_replace and insert_or_pushup aren’t provided here, so the output of your insert application is actually a function that takes these two arguments, rather than a tree.

3

Thanks. I managed to make this work.

ins tree (fun t -> t)(fun a b c -> BR(Type1( a, b, c)))

Wondering still. The ‘insert’ function uses the types declared earlier at the top. Isn’t it ?
How are these parameters used now ?

4

The uses of normal_replace and insert_or_pushup throughout ins are not types/constructors, they are functions (the ones provided as parameters). Also, the types for normal_replace and insert_or_pushup are just aliases.