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 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 E18E2BBAF for ; Wed, 23 Sep 2009 12:46:51 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AlMCAL+ZuUrZSMDdi2dsb2JhbACBUZknAQEBCgsKBxEFum6EGwU X-IronPort-AV: E=Sophos;i="4.44,438,1249250400"; d="scan'208";a="47123720" Received: from fmmailgate01.web.de ([217.72.192.221]) by mail4-smtp-sop.national.inria.fr with ESMTP; 23 Sep 2009 12:46:07 +0200 Received: from smtp08.web.de (fmsmtp08.dlan.cinetic.de [172.20.5.216]) by fmmailgate01.web.de (Postfix) with ESMTP id ED10211F93028; Wed, 23 Sep 2009 12:46:03 +0200 (CEST) Received: from [95.208.117.111] (helo=frosties.localdomain) by smtp08.web.de with asmtp (TLSv1:AES256-SHA:256) (WEB.DE 4.110 #314) id 1MqPMJ-0006LA-00; Wed, 23 Sep 2009 12:46:03 +0200 Received: from mrvn by frosties.localdomain with local (Exim 4.69) (envelope-from ) id 1MqPMJ-0002jE-At; Wed, 23 Sep 2009 12:46:03 +0200 From: Goswin von Brederlow To: Matthias Puech Cc: 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> <4AB15AD4.4030809@cs.unibo.it> Date: Wed, 23 Sep 2009 12:46:03 +0200 In-Reply-To: <4AB15AD4.4030809@cs.unibo.it> (Matthias Puech's message of "Wed, 16 Sep 2009 23:38:28 +0200") Message-ID: <87k4zqx7kk.fsf@frosties.localdomain> User-Agent: Gnus/5.110006 (No Gnus v0.6) XEmacs/21.4.22 (linux) MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Sender: goswin-v-b@web.de X-Sender: goswin-v-b@web.de X-Provags-ID: V01U2FsdGVkX1/OnNmSnU9E1oAMpA2/Y/8vcDosOXamZ9X5uOaG Ui2gypigtM64gcQ1tWHg4O4BIKUuSvRTi5vPT9sTXb//dIDvqI /S0yo+RYA= X-Spam: no; 0.00; home-made:01 unibo:01 model:01 intersection:01 node:01 ord:01 first-order:01 pervasives:01 cstr:01 cstr:01 ocaml:01 mfg:98 rec:01 caml-list:01 functions:01 Matthias Puech writes: > 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. If your key is part of the value then you could use the value itself as key. You still get a key and a value but they would point to the same object in memory. >> 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. Don't define a cstr but use the t as key and value. You still need to make sure (A, B) isn't added but you can trivialy wrap the Map module with functions like let add m x = Map.add m x x that hide the duplication of key and value. The problem I see with your approach though is that you can't find m (F) but must use find m (F(A)) You need a dummy value for F to create a F key. Idealy I think type prefixes could solve your problem. But ocaml doesn't have them. MfG Goswin