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

[Martin Percossi <ocaml@martinpercossi.com>]

Thanks v. much for your help!

Martin Jambon wrote:
> 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
>