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

[Martin Percossi <martin@martinpercossi.com>]

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
        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. Essentially, my intent is to have a table 
accessed by strings, pointing to anything == T. When I call 'diff', I 
would like to get Set of T. It's trivial to rewrite this in haskell 
(admittedly, using some extensions), like so:

module NoProblem where
import Data.Map as M
import Data.Set as S
type Table t = M.Map String t
type Entries t = S.Set (String, t)
class StringTable t where
  diff :: Table t -> Table t -> Entries t
instance Ord t => StringTable t where
  diff tl tr = let setOf t = S.fromList (M.assocs t) in
               setOf tl `S.difference` setOf tr

Is there a way I can accomplish the same thing in O'Caml?

Many thanks in advance,
Martin