From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <Xavier.Leroy@inria.fr>
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=AWL autolearn=disabled 
	version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83])
	by yquem.inria.fr (Postfix) with ESMTP id 46F26BBAF
	for <caml-list@yquem.inria.fr>; Thu, 26 Jun 2008 11:26:27 +0200 (CEST)
X-IronPort-AV: E=Sophos;i="4.27,707,1204498800"; 
   d="scan'208";a="12547310"
Received: from estephe.inria.fr (HELO [128.93.11.95]) ([128.93.11.95])
  by mail2-relais-roc.national.inria.fr with ESMTP; 26 Jun 2008 11:26:27 +0200
Message-ID: <486360C3.5020701@inria.fr>
Date: Thu, 26 Jun 2008 11:26:27 +0200
From: Xavier Leroy <Xavier.Leroy@inria.fr>
User-Agent: Thunderbird 1.5.0.7 (X11/20060915)
MIME-Version: 1.0
To: Fabrice Marchant <fabricemarchant@free.fr>
Cc: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Building a Set module for elements of a Map
References: <20080625153043.3bd7895c@free.fr>
In-Reply-To: <20080625153043.3bd7895c@free.fr>
X-Enigmail-Version: 0.94.0.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Spam: no; 0.00; functor:01 struct:01 struct:01 filliatre:01 pervasives:01 pervasives:01 functor:01 orderedtype:01 elt:01 wrote:01 parameterize:01 caml-list:01 constraint:01 data:02 argument:02 

Fabrice Marchant wrote:

> Please consider a functor F that takes as input the output signature of a Map.
>
> Here is the only way I see to declare a Set module whose elements type are
Map.S.key :
>
> module F ( M : Map.S ) = struct
>   module MKeySet =
>     Set.Make ( struct type t = M.key let compare = compare end )
> end

Jean-Christophe Filliātre replied:

> Using Pervasives.compare instead of a user-defined comparison function
> may even be incorrect. (Suppose the intended comparison function should
> identify (x,y) and (y,x), for instance; obviously, Pervasives.compare
> will not.)
>
> A possible solution to your problem is to have functor F taking instead
> a module for keys as argument, and then to build module M inside F; thus
> it would look like:
>
> 	module F(K : OrderedType) = struct
> 	  module M = Map.Make(K)
> 	  module MKeySet = Set.Make(K)
> 	  ...
> 	end

Jean-Christophe is right that Pervasives.compare is not the solution.

Yet another alternative is to parameterize F over both a Map and a Set,
adding a sharing constraint to ensure that they work on compatible
data types:

module F (M: Map.S) (MKeySet: Set.S with type elt = M.key) = struct
  ...
end

- Xavier Leroy