From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <puech@cs.unibo.it>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: *
X-Spam-Status: No, score=1.4 required=5.0 tests=SPF_NEUTRAL 
	autolearn=disabled version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104])
	by yquem.inria.fr (Postfix) with ESMTP id 7081EBC37
	for <caml-list@yquem.inria.fr>; Thu, 17 Sep 2009 10:47:44 +0200 (CEST)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Ap0EAGOUsUqCiAFm/2dsb2JhbACPcs5AhBgF
X-IronPort-AV: E=Sophos;i="4.44,402,1249250400"; 
   d="scan'208";a="34456642"
Received: from leb.cs.unibo.it ([130.136.1.102])
  by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/ADH-AES256-SHA; 17 Sep 2009 10:47:43 +0200
Received: from ssl.cs.unibo.it (ssl.cs.unibo.it [127.0.0.1]) (Authenticated sender: hidden)
	by leb.cs.unibo.it (Postfix) with ESMTPSA id 228B82364 ;
	Thu, 17 Sep 2009 10:47:41 +0200 (CEST)
Message-ID: <4AB1F740.9020404@cs.unibo.it>
Date: Thu, 17 Sep 2009 10:45:52 +0200
From: Matthias Puech <puech@cs.unibo.it>
User-Agent: Thunderbird 2.0.0.23 (X11/20090817)
MIME-Version: 1.0
To: CUOQ Pascal <Pascal.CUOQ@cea.fr>
Cc: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Sets and home-made ordered types
References: <20090917030607.927BCBCA9@yquem.inria.fr> <5EFD4D7AC6265F4D9D3A849CEA9219191AB20D@LAXA.intra.cea.fr>
In-Reply-To: <5EFD4D7AC6265F4D9D3A849CEA9219191AB20D@LAXA.intra.cea.fr>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
X-Spam: no; 0.00; unibo:01 home-made:01 pointer:01 cuoq:01 orderedtype:01 struct:01 beginner's:01 ocaml:01 bug:01 .......:98 beginners:01 caml-list:01 caml-list:01 bin:01 caml:02 

Hello and thanks to all for your answers,

If I understand correctly, you're all (David, Elnatan, Vincent, 
Tiphaine, Pascal) suggesting more or less the same solution (the one 
below). Do you have an idea of its memory overhead compared to just 
using Sets? I guess the value is not copied twice but shared between 
keys and elements right? So what, one pointer more for each association 
in the Map? That would be rather acceptable (but still not ideal, sorry 
I'm very demanding).

Thanks again,

    -- Matthias

CUOQ Pascal a écrit :
> Since you already have the "compare" function between objects of
> type t, why don't you make your map associate values of type t to
> identical values of type t instead of trying to have different type
> for keys and elements?
>
> You can even do it generically, and obtain with little effort an
> implementation of sets that supports find.
>
> module Set_With_Find(X:Set.OrderedType) = 
> struct
>       module M = Map.Make(X)
>       type t = X.t M.t (* with invariant that value v is always associated to v *)
>       let find = M.find
>       let add v s = M.add v v s
>       .......
> end
>
> Pascal
>
>
>
>   
> ------------------------------------------------------------------------
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>