CODEWITHSUNDEEP
typesocaml
Addem
Addem

Reputation: 3919

Why does this OCaml functor not recognize the structure type?

I've written the following functor and instance, 

module type Set = sig
  type elt
  type t
  val empty : t
  val insert : elt -> t -> t
  val find : elt -> t -> bool
end

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

module BstSet(M: OrderedSet) : Set = struct
  type elt = M.t
  type t = M.t tree
  let empty = Leaf
  let rec insert x tr = match tr with
    | Leaf -> Node(Leaf, x, Leaf)
    | Node (lt, y, rt) -> let c = M.compare x y in
                          if c < 0 then Node (insert x lt, y, rt)
                          else if c > 0 then Node (lt, y, insert x rt)
                          else Node (lt, y, rt)
  let rec find x tr = match tr with
    | Leaf -> false
    | Node (lt, y, rt) -> let c = M.compare x y in
                          if c = 0 then true
                          else if c < 0 then find x lt
                          else find x rt
end

module MyString : OrderedSet = struct
  type t = string
  let compare s1 s2 = compare s1 s2
end

module StringSet = BstSet(MyString);;

StringSet.empty |> StringSet.insert "abc";;

and the compiler raises the error 

StringSet.empty |> StringSet.insert "abc";;
                                          ^^^^^
Error: This expression has type string but an expression was expected of type
         StringSet.elt = BstSet(MyString).elt
Command exited with code 2.

This confuses me because I would have thought that something like this would be going on in the compiler:

  1. We construct BstSet(MyString) with the functor, so that the argument M is MyString.
  2. That means when we call M.t this is string.
  3. That means elt is string.
  4. That means, in the signature for insert, we have a function string -> string tree -> string tree.

So this should compile. Or put more directly, I would have thought StringSet.elt would be equal to string.

Upvotes: 2

Views: 175

Answers (1)

ivg
ivg

Reputation: 35210

The definition

module BstSet(M: OrderedSet) : Set = struct ... end

says nothing about the equality between Set.elt and M.t (indeed, they are not required to be the same, e.g., the implementation could embed extra information into the elt type). To express this equality you have to add the sharing constraint, e.g.,

module BstSet(M: OrderedSet) : Set with type elt = M.t = struct ... end

alternatively, you can remove the module type and let the compiler to look into the implementation, e.g., like this

module BstSet(M: OrderedSet) = struct ... end

This is useful when you're not going to export your functor from your module and are using it for internal purposes only.

Upvotes: 5

Related Questions