From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <Jean-Christophe.Filliatre@lri.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 mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82])
	by yquem.inria.fr (Postfix) with ESMTP id D797ABBAF
	for <caml-list@yquem.inria.fr>; Thu, 26 Jun 2008 11:19:24 +0200 (CEST)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AgEFAKj7YkiBrw8EWGdsb2JhbACSVgEbIZ9w
X-IronPort-AV: E=Sophos;i="4.27,707,1204498800"; 
   d="scan'208";a="14438973"
Received: from ext.lri.fr ([129.175.15.4])
  by mail1-smtp-roc.national.inria.fr with ESMTP; 26 Jun 2008 11:19:24 +0200
Received: from localhost (localhost [127.0.0.1])
	by ext.lri.fr (Postfix) with ESMTP id 422B9A498F;
	Thu, 26 Jun 2008 11:20:08 +0200 (CEST)
X-Virus-Scanned: Debian amavisd-new at lri.fr
Received: from ext.lri.fr ([127.0.0.1])
	by localhost (ext.lri.fr [127.0.0.1]) (amavisd-new, port 10024)
	with ESMTP id 24ACocfFY9O3; Thu, 26 Jun 2008 11:19:57 +0200 (CEST)
Received: from [129.175.4.117] (lri4-117 [129.175.4.117])
	(using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits))
	(No client certificate requested)
	by ext.lri.fr (Postfix) with ESMTP id CFA49A498E;
	Thu, 26 Jun 2008 11:19:57 +0200 (CEST)
Message-ID: <48635F85.4030108@lri.fr>
Date: Thu, 26 Jun 2008 11:21:09 +0200
From: =?ISO-8859-1?Q?Jean-Christophe_Filli=E2tre?= <Jean-Christophe.Filliatre@lri.fr>
User-Agent: Thunderbird 1.5.0.14ubu (X11/20080306)
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.2.0
OpenPGP: url=http://www.lri.fr/~filliatr/mykey.asc
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Spam: no; 0.00; filliatre:01 filliatre:01 lri:01 functor:01 struct:01 struct:01 orderedtype:01 pervasives:01 orderedtype:01 pervasives:01 functor:01 lri:01 filliatr:01 wrote:01 caml-list:01 

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
> 
>   The problem is to access the OrderedType that permitted to build the Map M. It seems to have disappeared inside the output Map signature S. So the trial of regeneration :
> struct type t = M.key let compare = compare end
> 
>   It maybe exists a straightforward signature we could pick somewhere inside Map related modules ?
>   Moreover I'm afraid this "Ersatz" of signature based on _Pervasives_.compare is in some cases deficient, because different from original OrderedType of Map elements...

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

Hope this helps,
-- 
Jean-Christophe Filliātre
http://www.lri.fr/~filliatr/