Beginning with OCaml Modules

Learning
1

Please excuse my poor English.

I’m trying to test binary search trees with the help of « Learning Programming with OCaml ».
That’s what I wrote :

module type Ordered = sig
  type t
  val compare : t -> t -> int
end

module type PersistentSet = sig
  type elt
  type t
  val empty : t
  val add : elt -> t -> t
  val mem : elt -> t -> bool
  val min_elt : t -> elt
  val remove : elt -> t -> t
  val cardinal : t -> int
end

module Make(X : Ordered) : PersistentSet with type elt = X.t = struct
   type elt = X.t
   type t = Empty | Node of t * elt * t * int
   let empty = Empty

   let rec min_elt = function
     | Empty -> raise Not_found
     | Node (Empty, v, _, _) -> v
     | Node (l, _, _, _) -> min_elt l 

  …
  …
 end

module OrderedInt : Ordered = struct type t = int let compare = compare end
module SearchTree = Make (OrderedInt)

let rec from_list = function
  | [] -> SearchTree.empty
  | a :: q -> SearchTree.add a (from_list q)

But, when I type from_list [ 4; 3; 20; 0 ]
I get the error Error: This expression has type “int” but an expression was expected of type
“SearchTree.elt” = “OrderedInt.t”

Can you please help me to solve my problem ?

2

The issue is the module type signature constraint : Ordered.

This effectively tells the type checker that it should forget whatever information it learned about OrderedInt (in particular that OrderedInt.t = int), and instead consider that its signature is exactly Ordered. In particular, the typechecker now considers OrderedInt.t to be an abstract type (and no longer equal to int).

Removing : Ordered or replacing it by Ordered with type t = int should resolve your issue.

Cheers,
Nicolas

2 Likes