From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 29108BC68 for ; Sat, 28 Oct 2006 22:16:24 +0200 (CEST) Received: from out1.smtp.messagingengine.com (out1.smtp.messagingengine.com [66.111.4.25]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id k9SKGJn1001593 for ; Sat, 28 Oct 2006 22:16:23 +0200 Received: from db2.internal (db2.internal [10.202.2.12]) by frontend1.messagingengine.com (Postfix) with ESMTP id DDC20DBEE8B for ; Sat, 28 Oct 2006 16:16:17 -0400 (EDT) Received: from heartbeat1.messagingengine.com ([10.202.2.160]) by db2.internal (MEProxy); Sat, 28 Oct 2006 16:16:20 -0400 X-Sasl-enc: PZZ6O05gW1ApuzkeJlRzXde9oAkOQ/V/E8wIpczU7FEJ 1162066580 Received: from adsl-75-20-182-22.dsl.sndg02.sbcglobal.net (adsl-75-20-182-22.dsl.sndg02.sbcglobal.net [75.20.182.22]) by mail.messagingengine.com (Postfix) with ESMTP id 56DA81DE87; Sat, 28 Oct 2006 16:16:19 -0400 (EDT) Date: Sat, 28 Oct 2006 13:16:11 -0700 (PDT) From: Martin Jambon X-X-Sender: martin@droopy To: Martin Percossi Cc: caml-list@inria.fr Subject: Re: [Caml-list] Functorized map: How to go from (polymorphic) map to set? In-Reply-To: <45433F37.3030506@martinpercossi.com> Message-ID: References: <45433F37.3030506@martinpercossi.com> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-j-chkmail-Score: MSGID : 4543BA93.001 on concorde : j-chkmail score : X : 0/20 1 X-Miltered: at concorde with ID 4543BA93.001 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 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