Re: [Caml-list] Functorized map: How to go from (polymorphic) map to set?

[Martin Jambon <martin1977@laposte.net>]

On Sat, 28 Oct 2006, Martin Percossi wrote:

> Hello, I'm a bit of a newbie to ocaml - I've programmed more in haskell plus 
> all the other "standard" languages (C, java, ...). I'm testing ocaml by 
> writing a little language of my own. Unfortunately, I'm somewhat stuck with 
> something that I know in haskell would be quite easy to code using type 
> classes. Here is a minimal example:
>
> module type AbstractStringTable =
> sig
>   type 'a table
>   type 'a set
>   (* Give me the set of entries, i.e. (string, value)
>   pairs that are in the first table but not in the
>   second, as a set *)
>   val diff   : 'a table -> 'a table -> 'a set
> end;;
> module StringTable : AbstractStringTable =
> struct
>   module M = Map.Make(String)
>   type 'a table = 'a M.t
>   type 'a settype = string * 'a
>   module IdTy : Set.OrderedType =
>     struct
>       type 'a t = 'a settype
              ^^^^

The problem is here: "type t" is expected, not "type 'a t".

>       let compare (s1, _) (s2, _) = String.compare s1 s2
>     end
>   module S = Set.Make(IdTy)
>   (* HERE'S THE PROBLEM! A SET WANTS A MONOMORPHIC TYPE!!!  *)
>   type 'a set = 'a S.t
> end;;
>
> And the compiler error I get is:
> File "problem.ml", line 22, characters 6-112:
> Signature mismatch:
> Modules do not match:
> sig
>   type 'a t = 'a settype
>   val compare : String.t * 'a -> String.t * 'b -> int
> end
> is not included in
> Set.OrderedType
> Type declarations do not match:
> type 'a t = 'a settype
> is not included in
> type t
>
> So basically the compiler doesn't like me trying to make the Set.t type 
> polymorphic, as it is in Map.

If you look at the keys, in both cases they are monomorphic. So the 
solution here is to implement your StringTable module as a functor which 
takes the type of elements as argument.

Here's something that compiles:

module type AbstractStringTable =
sig
   type table
   type set
     (* Give me the set of entries, i.e. (string, value)
        pairs that are in the first table but not in the
        second, as a set *)
   val diff   : table -> table -> set
end;;

module type Elt_type =
sig
   type elt
end

module StringTable (E : Elt_type) : AbstractStringTable =
struct
   open E
   module M = Map.Make(String)
   type table = elt M.t
   type settype = string * elt
   module IdTy : Set.OrderedType =
      struct
        type t = settype
        let compare (s1, _) (s2, _) = String.compare s1 s2
      end
   module S = Set.Make(IdTy)
   (* HERE'S THE PROBLEM! A SET WANTS A MONOMORPHIC TYPE!!!  *)
   type set = S.t
   let diff = failwith "not implemented"
end;;



Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr