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=AWL 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 AC5E4BBCB for ; Wed, 5 Mar 2008 18:16:42 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAANNkzkfAXQInh2dsb2JhbACQcgEBAQgKKZpU X-IronPort-AV: E=Sophos;i="4.25,451,1199660400"; d="scan'208";a="9918458" Received: from concorde.inria.fr ([192.93.2.39]) by mail3-smtp-sop.national.inria.fr with ESMTP; 05 Mar 2008 18:16:17 +0100 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id m25HGGZj003657 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Wed, 5 Mar 2008 18:16:17 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAADZkzkdCm3xrnWdsb2JhbACQcgEBAQEBCg+afQ X-IronPort-AV: E=Sophos;i="4.25,451,1199660400"; d="scan'208";a="8999583" Received: from www.janestcapital.com (HELO smtp.janestcapital.com) ([66.155.124.107]) by mail1-smtp-roc.national.inria.fr with ESMTP; 05 Mar 2008 18:16:16 +0100 Received: from [172.25.129.161] [38.96.172.125] by janestcapital.com with ESMTP (SMTPD-9.10) id A55E04A0; Wed, 05 Mar 2008 12:16:14 -0500 Message-ID: <47CED556.4070208@janestcapital.com> Date: Wed, 05 Mar 2008 12:16:06 -0500 From: Brian Hurt User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.2) Gecko/20040804 Netscape/7.2 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Berke Durak Cc: Caml-list List Subject: Re: [Caml-list] Canonical Set/Map datastructure? References: <47CECF23.1020508@exalead.com> In-Reply-To: <47CECF23.1020508@exalead.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 47CED560.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; berke:01 durak:01 functors:01 pervasives:01 wrote:01 caml-list:01 modules:02 modules:02 tree:02 functional:02 canonical:03 canonical:03 hoc:03 brian:05 brian:05 Berke Durak wrote: > The Map and Set modules use AVL trees which are efficient but not > canonical - a given > set of elements can have more than one representation. This means > that you cannot use > ad hoc comparison on sets and maps, and this is why they are presented > as functors. However, as you can walk the tree in O(N), it's still possible to do set/map compare in O(N) worst case. All this means is that Pervasives.compare is not equivalent to Set.compare. > > Does anyone know if, in the many years that have passed since the > implementation of > those fine modules, someone has invented a (functional) datastructure > that is as > efficient while being canonic? The preserves "fast" (O(log N)) insert and removal? No. If you're willing to accept O(N) insert/removal cost, simple sorted lists work. I'm not sure if it's possible to have both fast insert/removal and a canonical form. Brian