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 discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 6F9F8BC69 for ; Sun, 29 Oct 2006 18:47:38 +0100 (CET) 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 k9THlaNo018007 for ; Sun, 29 Oct 2006 18:47:38 +0100 Received: from db2.internal (db2.internal [10.202.2.12]) by frontend1.messagingengine.com (Postfix) with ESMTP id A5896DBF59C; Sun, 29 Oct 2006 07:50:11 -0500 (EST) Received: from heartbeat1.messagingengine.com ([10.202.2.160]) by db2.internal (MEProxy); Sun, 29 Oct 2006 07:50:13 -0500 X-Sasl-enc: xlMKp16FVey7HaRGpnTPuJbJ2Qb1SYMYUJvIL2Dr9/pi 1162126213 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 5EB2D219; Sun, 29 Oct 2006 07:50:12 -0500 (EST) Message-ID: <4544A388.7000407@martinpercossi.com> Date: Sun, 29 Oct 2006 12:50:16 +0000 From: Martin Percossi Reply-To: ocaml@martinpercossi.com User-Agent: Thunderbird 1.5.0.7 (X11/20060913) MIME-Version: 1.0 To: Martin Jambon Cc: caml-list@inria.fr Subject: Re: [Caml-list] Functorized map: How to go from (polymorphic) map to set? References: <45433F37.3030506@martinpercossi.com> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 4544E938.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; ocaml:01 ocaml:01 haskell: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 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 >