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 concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 29090BC0B for ; Fri, 26 Jan 2007 11:52:37 +0100 (CET) Received: from ptb-relay03.plus.net (ptb-relay03.plus.net [212.159.14.214]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l0QAqdnL002608 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO) for ; Fri, 26 Jan 2007 11:52:39 +0100 Received: from [80.229.56.224] (helo=[10.0.0.5]) by ptb-relay03.plus.net with esmtp (Exim) id 1HAOh8-0007Qi-00 for caml-list@yquem.inria.fr; Fri, 26 Jan 2007 10:52:34 +0000 From: Jon Harrop Organization: Flying Frog Consultancy Ltd. To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] The OCaml Summer Project Date: Fri, 26 Jan 2007 10:45:17 +0000 User-Agent: KMail/1.9.5 References: <45B8E03F.7040802@janestcapital.com> In-Reply-To: <45B8E03F.7040802@janestcapital.com> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200701261045.17495.jon@ffconsultancy.com> X-Miltered: at concorde with ID 45B9DD77.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; ocaml:01 yaron:01 minsky:01 ocaml:01 functors:01 functor:01 stdlib:01 inlining:01 functors:01 polymorphism:01 iirc:01 camlp:01 arrays:01 literals:01 hashtbl:01 On Thursday 25 January 2007 16:52, Yaron M. Minsky wrote: > I am pleased to announce the OCaml Summer Project. Sounds like an excellent idea and the projects all look fascinating. However, I do have some comments on the "Binary tree library" project: OCaml currently has two separate implementations of AVL trees in Map and Set functors. Set already has fast union and split operations. Having two separate implementations is wasteful but more efficient. The underlying tree code could be factored out into another functor but this is costly in terms of performance. Also, the OCaml stdlib has used an odd choice of optimisations: inlining height calculation (which is quite a small benefit in the context of functors and polymorphism) but not amortising single-child trees into a separate constructor (which can remove up to 50% of the GC's effort). So the code can be made shorter and faster. I've already implemented my own AVL set using the node-specialisation trick. Performance is ~30% faster, IIRC. I've also wanted to write a functional array based on AVL trees (O(log n) lookup but fast sub, append, insert, delete etc.) and a camlp4 extension to support pattern matching over this type. Lists and arrays are rather priviledged containers in OCaml, having pattern matching and literals, but trees are better in many respects and would make an excellent general-purpose container. Finally, having to use functors does obfuscate OCaml code that deal with Sets and Maps in many cases, particularly because there are no built-in Int and Float modules so you must write your own. I often find that this superfluous code is as long as all of the code using the Sets/Maps. Although it would be "dangerous", Sets and Maps implemented without functors are much easier to use. After all, Hashtbl is typically used in that way. It is also worth noting that several people (Diego, Jean-Christophe) have written other tree libraries using various data structures (RB, trie, splay etc.). As far as I can tell, AVL trees are a good all-rounder. Best of luck with the projects! -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. Objective CAML for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists