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 mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 097C3BBC1 for ; Wed, 5 Mar 2008 18:37:29 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAOhozkfAXQImh2dsb2JhbACQcgEBAQgKKZpY X-IronPort-AV: E=Sophos;i="4.25,451,1199660400"; d="scan'208";a="8044675" Received: from discorde.inria.fr ([192.93.2.38]) by mail2-smtp-roc.national.inria.fr with ESMTP; 05 Mar 2008 18:37:28 +0100 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id m25HbRev000616 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Wed, 5 Mar 2008 18:37:28 +0100 X-IronPort-AV: E=Sophos;i="4.25,451,1199660400"; d="scan'208";a="23403442" Received: from mga02.intel.com ([134.134.136.20]) by mail4-smtp-sop.national.inria.fr with ESMTP; 05 Mar 2008 18:37:27 +0100 Received: from orsmga002.jf.intel.com ([10.7.209.21]) by orsmga101.jf.intel.com with ESMTP; 05 Mar 2008 09:37:25 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="4.25,451,1199692800"; d="scan'208";a="260969872" Received: from azsmsx602.amr.corp.intel.com ([10.2.163.6]) by orsmga002.jf.intel.com with ESMTP; 05 Mar 2008 09:34:22 -0800 Received: from azsmsx501.amr.corp.intel.com ([10.2.167.99]) by azsmsx602.amr.corp.intel.com ([10.2.163.6]) with mapi; Wed, 5 Mar 2008 10:34:21 -0700 From: "Harrison, John R" To: Berke Durak , Caml-list List Date: Wed, 5 Mar 2008 10:34:21 -0700 Subject: RE: [Caml-list] Canonical Set/Map datastructure? Thread-Topic: [Caml-list] Canonical Set/Map datastructure? Thread-Index: Ach+4U6IDnU/2YWmSEWazyBOq/yflwABKjDA Message-ID: References: <47CECF23.1020508@exalead.com> In-Reply-To: <47CECF23.1020508@exalead.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: acceptlanguage: en-US Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Miltered: at discorde with ID 47CEDA57.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; berke:01 ocaml:01 lib:01 ocaml:01 pons:01 hashes:01 caml-list:01 functions:01 lazy:02 modules:02 implemented:02 functional:02 theoretical:03 canonical:03 unit:03 Hi Berke, | 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? I have an implementation, which you're welcome to use/adapt. It's certainly not particularly well optimized, but I've relied on it for a few years with no problems. The code is in this file: http://www.cl.cam.ac.uk/~jrh13/atp/OCaml/lib.ml Search for "Diego" and the relevant stuff starts there; a few earlier functions (like "uniq") are used, but they are easy to copy or replace. This was the outcome of a similar question I asked on the OCaml list a few years ago. Diego Olivier Fernandez Pons not only pointed me at some interesting theoretical results, but also suggested an idea using hashes and Patricia trees that works very well in practice. That's what I implemented. My implementation is for maps only, but it's easy to adapt for sets. Or you could just use maps to type "unit" if you're lazy like me. John.