Functorized map: How to go from (polymorphic) map to set?

Martin Percossi
 Martin Jambon
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Martin Jambon <martin1977@l...> 
Subject:  Re: [Camllist] Functorized map: How to go from (polymorphic) map to set? 
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 6112: > 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