From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 85905BB81 for ; Fri, 24 Feb 2006 17:20:48 +0100 (CET) Received: from ext.lri.fr (ext.lri.fr [129.175.15.4]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id k1OGKl49001430 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Fri, 24 Feb 2006 17:20:48 +0100 Received: from smtp.lri.fr (serveur3-5 [129.175.3.5]) by ext.lri.fr (Postfix) with ESMTP id B9B77202653; Fri, 24 Feb 2006 17:20:45 +0100 (CET) Received: from pc9-152 (pc9-152 [129.175.9.152]) by smtp.lri.fr (Postfix) with ESMTP id CEB43CED9B; Fri, 24 Feb 2006 17:20:44 +0100 (CET) Received: from filliatr by pc9-152 with local (Exim 3.36 #1 (Debian)) id 1FCffp-0005EW-00; Fri, 24 Feb 2006 17:20:05 +0100 MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Message-ID: <17407.12848.419325.961992@gargle.gargle.HOWL> Date: Fri, 24 Feb 2006 17:20:00 +0100 To: Brian Hurt Cc: Damien Doligez , caml-list Subject: Re: [Caml-list] Map.fold behavior changed In-Reply-To: References: <20060224112209.51szurk2dc00oggg@www.sms.ed.ac.uk> <17406.61821.450737.625981@gargle.gargle.HOWL> <20060224132950.7l49sm2akg0sskkw@www.sms.ed.ac.uk> <1AEDE2F4-2D83-416F-AFDC-7ECAF892BFBD@inria.fr> X-Mailer: VM 7.19 under Emacs 21.4.1 From: Jean-Christophe Filliatre X-Virus-Scanned: by amavisd-new at lri.fr X-Miltered: at nez-perce with ID 43FF325F.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 filliatre:01 filliatr:01 lri:01 red-black:01 red-black:01 lri:01 filliatr:01 ocaml:01 filliatre:01 wrote:01 writes:01 tree:02 tree:02 element:02 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 Brian Hurt writes: > > I may take this opportunity to offer a red-black tree implementation of > Map as a replacement, if people are interested. The advantage a > red-black tree is that it uses one less word of memory per element in a > map. For information, I wrote an implementation of Set using red-black trees a long time ago. It is available here: http://www.lri.fr/~filliatr/software.en.html Note: this code was even formally proved correct using a proof assistant. Getting Map from Set is rather straightforward. I also did some benchmarks to compare red-black trees, patricia trees and Ocaml AVLs and, as time is concerned, the AVLs were (almost) always the most efficient. -- Jean-Christophe Filliātre (http://www.lri.fr/~filliatr)