Unbound constructor error when using module signature

Question

module type Cont_map = sig
  type t
  type key
  type value = key (* values are the same type as keys *)
  val empty : t

  val lookup : key -> t -> value option

  val insert : key -> value -> t -> t

  val remove : key -> t -> t * value option

  val lub_key : key -> t -> key option

  val glb_key : key -> t -> key option

  val interpolated_lookup : key -> t -> value option

end

module Cont_map (Key : Interp with type t = float) : Cont_map = struct 
  type t = 
    | Leaf 
    | Branch of Key.t * Key.t * t * t

  type key = Key.t
  type value = key

  let empty = Leaf

  let rec lookup k dmap = 
    match dmap with
    | Leaf -> None
    | Branch (kk, vv, l, r) -> if k < kk then lookup k l else if k > kk then lookup k r else Some(vv)

  let rec insert kk vv dmap = 
    match dmap with
    | Leaf -> Branch (kk, vv, Leaf, Leaf)
    | Branch (k, v, l, r) -> 
      if kk < k then Branch (k, v, insert kk vv l, r)
      else if kk = k then Branch (k, vv, l, r)
      else Branch (k, v, l, insert kk vv r)

  let remove kk dmap = 
    let rec max_key (d: t) = 
      match d with
      | Leaf -> None
      | Branch (key, value, _, right) -> 
        match right with
        | Leaf -> Some(key, value)
        | Branch (_, _, _, _) -> max_key(right)
    in
    let rec remove_internal kk map =
      match map with
      | Leaf -> remove_internal kk map
      | Branch (k, v, l, r) -> 
        if kk < k then Branch (k, v, remove_internal kk l, r)
        else if kk = k then 
          match max_key(l) with
          | Some(key, value) -> Branch (key, value, remove_internal key l, r)
          | None -> r
        else Branch (k, v, l, remove_internal kk r)
    in
    match lookup kk dmap with
    | None -> (dmap, None)
    | Some(v) -> (remove_internal kk dmap, Some(v))
    
  let rec lub_key kk map = 
    let rec max_key (d: t) = 
      match d with
      | Leaf -> None
      | Branch (key, _, _, right) -> 
        match right with
        | Leaf -> Some(key)
        | Branch (_, _, _, _) -> max_key(right)
    in
    match map with
    | Leaf -> None
    | Branch (k, _, l, r) -> if kk < k then
      match max_key(l) with
      | None -> Some(k)
      | Some(kkk) -> if kkk < kk then Some(k) else lub_key kk l 
  else if kk = k then Some(k) else lub_key kk r

  let rec glb_key kk map =
    let rec min_key (d: t) = 
      match d with
      | Leaf -> None
      | Branch (key, _, left, _) -> 
        match left with
        | Leaf -> Some(key)
        | Branch (_, _, _, _) -> min_key(left)
    in
    match map with
    | Leaf -> None
    | Branch (k, _, l, r) -> if kk < k then glb_key kk l else if kk = k then Some(k)
    else match min_key(r) with
    | None -> Some(k)
    | Some(kkk) -> if kkk <= kk then glb_key kk r else Some(k)

  let interpolated_lookup kk map = 
    match lub_key kk map with
    | None -> None
    | Some(rk) -> match glb_key kk map with
                  | None -> None
                  | Some(lk) -> match lookup lk map, lookup rk map with
                                | Some(lv), Some(rv) -> Some(Key.interpolate (lk, lv) (rk, rv) kk)
                                | _ -> failwith "Can't reach here"

end

module Float_cont_map = Cont_map (Float_interp)

Above is my code in a file named abstraction.ml

open Core;;
open OUnit2;;

module M = Abstraction.Cont_map(Abstraction.Float_interp);;

let empty = M.empty

let d1 = M.(Branch (1.0, 1.0, Leaf, Branch (2.0, 2.0, Leaf, Branch (3.0, 3.0, Leaf, Branch (4.0, 4.0, Leaf, Leaf)))))

This is my test file named tests.ml

(test
 (name tests)
 (libraries 
  core
  ounit2
  abstraction
 ))

This is my dune file in tests directory.

However, it calls that "Unbound constructor Branch". And in code below I write:

let test_lookup _ = 
  assert_equal None @@ (M.lookup 1. empty);
  assert_equal (Some(1.0)) @@ (M.lookup 1. d1)

It doesn't say that M.lookup unbound value, but it says that expected M.value type but get float.

Answer 1

Like functions, e.g., empty, the constructors, e.g., Leaf are also a part of the signature. So when you constrained your module type with the signature that lacks constructors, you effectively hid it from the users of your module.

You should either make them public, e.g.,

module type Cont_map = sig
  type key
  type t = 
   | Leaf 
   | Branch of key * key * t * t

But this will break the abstraction of your module, since you don't want the users to create containers directly. So the right approach would be to use the public interface of your module to create containers, i.e., to use empty and insert.

You can also use inline_tests and test the implementation of the container module inside of your module, where you have access to your constructors.