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 mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by yquem.inria.fr (Postfix) with ESMTP id 86BD7BC37
	for <caml-list@yquem.inria.fr>; Wed, 16 Sep 2009 23:38:32 +0200 (CEST)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: ApoEAJj3sEqCiAFm/2dsb2JhbADfCoQYBQ
X-IronPort-AV: E=Sophos;i="4.44,400,1249250400"; 
   d="scan'208";a="46725200"
Received: from leb.cs.unibo.it ([130.136.1.102])
  by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/ADH-AES256-SHA; 16 Sep 2009 23:38:32 +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 D10762368 
	for <caml-list@yquem.inria.fr>; Wed, 16 Sep 2009 23:38:30 +0200 (CEST)
Message-ID: <4AB15AD4.4030809@cs.unibo.it>
Date: Wed, 16 Sep 2009 23:38:28 +0200
From: Matthias Puech <puech@cs.unibo.it>
User-Agent: Thunderbird 2.0.0.23 (X11/20090817)
MIME-Version: 1.0
To: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Sets and home-made ordered types
References: <4AB11511.2050506@cs.unibo.it> <002e01ca36fd$37656c60$a6304520$@metastack.com>
In-Reply-To: <002e01ca36fd$37656c60$a6304520$@metastack.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
X-Spam: no; 0.00; unibo:01 home-made:01 model:01 intersection:01 node:01 ord:01 first-order:01 pervasives:01 cstr:01 cstr:01 rec:01 caml-list:01 functions:01 constructor:01 constructor:01 

David Allsopp a écrit :
> Is it not possible to model your requirement using Map.Make instead - where
> the keys represent the equivalence classes and the values whatever data
> you're associating with them? 

Yes, that's exactly the workaround I ended up using, although I'm not
very happy with it because, among other things, these keys/class
disciminant get duplicated (once inside the key, once inside the
element). I'm getting more concrete below.

> In terms of a strictly pure implementation of a functional Set, it would be
> odd to have a "find" function - you'll also get some interesting undefined
> behaviour with these sets if you try to operations like union and
> intersection but I guess you're already happy with that! 

It seems to me rather natural to have it: otherwise, what's the point of
being able to provide your own compare, beside just checking for
membership of the class? The implementation of the function is
straightforward: just copy mem and  make it return the element in case
of success:

let rec find x = function
     Empty -> raise Not_found
   | Node(l, v, r, _) ->
       let c = Ord.compare x v in
       if c = 0 then v else
         find x (if c < 0 then l else r)

For union and inter, I don't see how their behavior would be undefined,
since neither the datastructure nor the functions are changed.


Here is what I want to do: Given a purely first-order datastructure,
let's say:
type t = F of t | G of t * t | A | B
I want to index values of type t according to their first constructor.
So in my set structure, there will be at most one term starting with
each constructor, and:
find (F(A)) (add (F(B)) empty) will return F(B)

With a Set.find, it's easy:

let compare x y = match x,y with
| (F,F | G,G | A,A | B,B) -> 0
| _ -> Pervasives.compare x y

module S = Set.Make ...

With the Map solution, i'm obliged to define:

type cstr = F' | G' | A' | B'
let cstr_of x = F _ -> F' | G _ -> G' etc.

and then make a Map : cstr |--> t, which duplicates the occurrence of
the constructor (F' in the key, F in the element). Besides, I'm
responsible for making sure that the pair e.g. (G', F(A)) is not added.

Thanks for your answer anyway!

	-- Matthias