Values do not match

Question

I am pretty sure I am not squinting hard enough to see where the mismatch is ... but I have been staring at my screen for a long time and thus asking this question.

My MLI file looks like

type ('k, 'v) t

val empty: ('k, 'v) t 

val find: 'k -> ('k, 'v) t -> 'v option

val bindings: ('k, 'v) t -> ('k * 'v) list

val insert: 'k -> 'v -> ('k, 'v) t -> ('k, 'v) t

and I have an implementation for each of these in my ML file

type color = Red | Black
type ('k, 'v) t = Leaf | Node of (color * ('k, 'v) t * ('k * 'v) * ('k, 'v) t)

let empty = Leaf

let rec find k = function 
  | Leaf -> None
  | Node (_, l, (x, y), r) -> 
      if k < x then find k l
      else if k > x then find k r
      else Some y

let rec bindings = function 
  | Leaf -> []
  | Node (_, l, t, r) -> List.append (t :: bindings l) (bindings r)

let balance = function 
  | (Black, Node (Red, Node (Red, a, (xk, xv), b), (yk, yv), c), (zk, zv), d)
  | (Black, a, (xk, xv) ,Node (Red, b, (yk, yv), Node (Red, c, (zk, zv), d)))
  | (Black, Node (Red, a, (xk, xv), Node (Red, b, (yk, yv), c)), (zk, zv), d)
  | (Black, a, (xk, xv), Node (Red, Node (Red, b, (yk, yv), c), (zk, zv), d)) 
    -> Node (Red, Node (Black, a, (xk, xv), b), (yk, yv), Node (Black, c, (zk, zv), d))
  | t -> Node t

let rec insert_aux k v = function 
  | Leaf -> Node (Red, Leaf, (k, v), Leaf)
  | Node (c, l, (x, y), r) as n -> 
      if k < x then balance (c, insert_aux k v l, (x, y), r)
      else if k > v then balance (c, l, (x, y), insert_aux k v r)
      else n

let insert k v m = 
  match insert_aux k v m with 
  | Leaf -> failwith "Not possible"
  | Node (_, l, t, r) -> Node (Black, l, t, r)

As you can see that the insert function has been implemented and I can see it has the right type being returned. but when I do dune build I get the following error from the ocaml compiler

File "redblacktreemap/redBlackTreeMap.ml", line 1:
Error: The implementation redblacktreemap/redBlackTreeMap.ml
       does not match the interface redblacktreemap/.RedBlackTreeMap.objs/byte/redBlackTreeMap.cmi:
       Values do not match:
         val insert : 'a -> 'a -> ('a, 'a) t -> ('a, 'a) t
       is not included in
         val insert : 'k -> 'v -> ('k, 'v) t -> ('k, 'v) t
       File "redblacktreemap/redBlackTreeMap.mli", line 19, characters 0-48:
         Expected declaration
       File "redblacktreemap/redBlackTreeMap.ml", line 32, characters 4-10:
         Actual declaration

Answer 1

From the erroneous type a -> 'a -> ('a, 'a) t -> ('a, 'a) t you can see that your code is doing something that makes the compiler deduce that keys and values are the same type. This isn't what you want--the whole reason to have two type parameters (k, v) is so the types are independent.

Aha, you have this subexpression:

k > v

which means that k and v must be the same type.

Probably you meant k > x.