From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA07223; Fri, 6 Jun 2003 18:09:19 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA07106 for ; Fri, 6 Jun 2003 18:09:18 +0200 (MET DST) Received: from lri.lri.fr (lri.lri.fr [129.175.15.1]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h56G9IH20269 for ; Fri, 6 Jun 2003 18:09:18 +0200 (MET DST) Received: from pc8-123 (pc8-123 [129.175.8.123]) by lri.lri.fr (8.11.6p2/jtpda-5.3.2) with ESMTP id h56FxDB12126 for ; Fri, 6 Jun 2003 17:59:13 +0200 (MEST) Received: from filliatr by pc8-123 with local (Exim 3.35 #1 (Debian)) id 19OJcX-00045T-00 for ; Fri, 06 Jun 2003 17:59:13 +0200 From: Jean-Christophe Filliatre MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Message-ID: <16096.47697.220142.533361@gargle.gargle.HOWL> Date: Fri, 6 Jun 2003 17:59:13 +0200 To: caml-list@inria.fr Subject: [Caml-list] red-black trees X-Mailer: VM 7.03 under Emacs 20.7.2 Reply-To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre) X-MailScanner: Found to be clean X-Spam: no; 0.00; filliatre:01 lri:01 red-black:01 riders:01 implemented:01 ocaml's:01 filliatr:01 baire:01 ocaml:01 caml:01 optimized:02 interface:03 library:03 uses:06 20%:92 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Hello Caml riders, I've implemented sets using red-black trees, with the same interface as Ocaml's sets (that is Set.S). This implementation is not better than Ocaml's sets but (1) it uses a little less space (20% less to be precise), and (2) a formal proof of this library is work in progress (to be available soon). This red-black trees implementation is available from http://www.lri.fr/~filliatr/software.en.html PS: please note that another implementation of red-black trees is contained in Baire, which is more optimized with some respects but does not provide exactly the same interface as Ocaml sets. -- Jean-Christophe Filliātre ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners