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 SAA17738; Fri, 10 May 2002 18:59:58 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f 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 SAA17918 for ; Fri, 10 May 2002 18:59:58 +0200 (MET DST) Received: from moutng0.schlund.de (moutng0.kundenserver.de [212.227.126.170]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g4AGxvH29100 for ; Fri, 10 May 2002 18:59:57 +0200 (MET DST) Received: from [212.227.126.160] (helo=mrelayng0.kundenserver.de) by moutng0.schlund.de with esmtp (Exim 3.22 #2) id 176DkL-0001va-00 for caml-list@inria.fr; Fri, 10 May 2002 18:59:57 +0200 Received: from [80.129.99.38] (helo=gate.gerd-stolpmann.de) by mrelayng0.kundenserver.de with asmtp (Exim 3.22 #2) id 176DkL-0004JH-00 for caml-list@inria.fr; Fri, 10 May 2002 18:59:57 +0200 Received: from ice.gerd-stolpmann.de (ice.gerd-stolpmann.de [192.168.0.13]) by gate.gerd-stolpmann.de (Postfix) with ESMTP id 8E585CCCF for ; Fri, 10 May 2002 18:59:55 +0200 (CEST) Received: from ice (localhost [127.0.0.1]) by ice.gerd-stolpmann.de (Postfix) with ESMTP id DFBCF1AD75 for ; Fri, 10 May 2002 18:59:54 +0200 (MEST) Date: Fri, 10 May 2002 18:59:54 +0200 From: Gerd Stolpmann To: caml-list@inria.fr Subject: [Caml-list] Suggestion about balanced trees in stdlib Message-ID: <20020510185954.C635@ice.gerd-stolpmann.de> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Mailer: Balsa 1.2.4 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Hello list, I have always wondered why there are two implementations of balanced trees in the standard library: Set and Map. The set of operations is different, but the representation is (almost) identical. Furthermore, neither of the two modules claims to implement balanced trees in the interface; for example Set.iter does not specify the order of iteration although the implementation iterates linearly from the smallest to the largest element. The idea is to introduce a third module Balanced_tree, defining all of the operations for the two mentioned modules, but announcing them as balanced trees. This would have the advantage that the operations could be specified in a more complete way (Balanced_tree.iter is specified as iterating in an ascending way), and it would be reasonable to add further operations that know about the representation. Of course, Set and Map would recur to that more special module. Balanced_tree would have the representation of Map, i.e. the elements are pairs of keys and attached values. To emulate Set, the value () is used. Balanced_tree would have the following operations: - all of Set - all of Map - operations on intervals: "iter_interval", "fold_interval", and "interval" (returning the subset) The interval operations have an important application: One can program indexes that can be accessed by coordinates (e.g.: return all objects that are currently visible in the viewbox). What do you think about this? Gerd -- ---------------------------------------------------------------------------- Gerd Stolpmann Telefon: +49 6151 997705 (privat) Viktoriastr. 45 64293 Darmstadt EMail: gerd@gerd-stolpmann.de Germany ---------------------------------------------------------------------------- ------------------- 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