From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <martin@martinpercossi.com>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled 
	version=3.1.3
Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38])
	by yquem.inria.fr (Postfix) with ESMTP id 61F2FBC6A
	for <caml-list@yquem.inria.fr>; Sat, 28 Oct 2006 19:37:34 +0200 (CEST)
Received: from out1.smtp.messagingengine.com (out1.smtp.messagingengine.com [66.111.4.25])
	by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id k9SHbSQS010833
	for <caml-list@inria.fr>; Sat, 28 Oct 2006 19:37:33 +0200
Received: from db2.internal (db2.internal [10.202.2.12])
	by frontend1.messagingengine.com (Postfix) with ESMTP id 2B20BDBA300
	for <caml-list@inria.fr>; Sat, 28 Oct 2006 07:29:58 -0400 (EDT)
Received: from heartbeat1.messagingengine.com ([10.202.2.160])
  by db2.internal (MEProxy); Sat, 28 Oct 2006 07:30:00 -0400
X-Sasl-enc: xELU49RdJxRA97dhtzbH/fSA2YfTfOeyGazhFGytaSMh 1162034999
Received: from [192.168.1.70] (87-194-55-10.bethere.co.uk [87.194.55.10])
	by mail.messagingengine.com (Postfix) with ESMTP id D1F511DD73
	for <caml-list@inria.fr>; Sat, 28 Oct 2006 07:29:59 -0400 (EDT)
Message-ID: <45433F37.3030506@martinpercossi.com>
Date: Sat, 28 Oct 2006 12:29:59 +0100
From: Martin Percossi <martin@martinpercossi.com>
User-Agent: Thunderbird 1.5.0.7 (X11/20060913)
MIME-Version: 1.0
To: caml-list@inria.fr
Subject: Functorized map: How to go from (polymorphic) map to set?
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Miltered: at discorde with ID 45439558.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Spam: no; 0.00; ocaml:01 haskell:01 ocaml:01 haskell:01 sig:01 val:01 struct:01 orderedtype:01 struct:01 compiler:01 mismatch:01 sig:01 val:01 orderedtype:01 compiler:01 

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