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 KAA10455; Mon, 20 Sep 2004 10:35:09 +0200 (MET DST) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id KAA08979 for ; Mon, 20 Sep 2004 10:35:08 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id i8K8Z7Rt017298 for ; Mon, 20 Sep 2004 10:35:07 +0200 Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.11/jtpda-5.4) with ESMTP id i8K8XYSE019688 ; Mon, 20 Sep 2004 10:33:34 +0200 (CEST) X-Ids: 168 Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id KAA23168 ; Mon, 20 Sep 2004 10:32:49 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id KAA708832 ; Mon, 20 Sep 2004 10:32:36 +0200 X-Authentication-Warning: ibm1.cicrp.jussieu.fr: fernande owned process doing -bs Date: Mon, 20 Sep 2004 10:32:35 +0200 (DST) From: Diego Olivier Fernandez Pons X-X-Sender: fernande@ibm1 To: Seth Fogarty cc: caml-list@pauillac.inria.fr Subject: Re: [Caml-list] Re: Set and Map question In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at nez-perce with ID 414E963B.007 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 414E95DE.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Loop: caml-list@inria.fr X-Spam: no; 0.00; pons:01 pons:01 etu:99 caml-list:01 implemented:01 implemented:01 baire:01 list':01 red-black:01 red-black:01 ralf:01 hinze:01 list':01 fernandez:01 fernandez:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Bonjour, > Yes, sorry, sorted. I know it is possible, I was wondering if it was > implemented. I never understood how worked those functions building a balanced search tree from a sorted list in O(n) _without_ first counting the number of elements in the list. Hence it is not implemented in Baire. As far as I know, there is no Caml implementation of any of them either (they all iter on the list applying O(log n) insertion function) but I may be wrong. SML/NJ standard library has a O(n) 'from_ordered_list' function for red-black trees. SML/NJ implementation of red-black trees uses zippers to handle insertion and deletion operations. It may be difficult to understand if you are not used to them. Ralf Hinze wrote a good paper on red-black trees (Constructing red-black trees, WAAAPL'99, available from his website). It explains how to implement 'from_ordered_list' in O(n) and most of existent functional implementations must be more or less based on it. Diego Olivier ------------------- 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