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 7D241BC0A for ; Mon, 4 Jun 2007 16:45:31 +0200 (CEST) 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 l54EjTdX024361 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO) for ; Mon, 4 Jun 2007 16:45:31 +0200 Received: from [80.229.56.224] (helo=beast.local) by ptb-relay03.plus.net with esmtp (Exim) id 1HvDoG-00046U-11 for caml-list@yquem.inria.fr; Mon, 04 Jun 2007 15:45:28 +0100 From: Jon Harrop Organization: Flying Frog Consultancy Ltd. To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Comparison of OCaml and MLton for numerics Date: Mon, 4 Jun 2007 15:39:03 +0100 User-Agent: KMail/1.9.7 References: <5195a210705302250u6a9e5adey4ed857480f9e5cd8@mail.gmail.com> <200706011813.48515.jon@ffconsultancy.com> <46641BC1.9090305@cs.umd.edu> In-Reply-To: <46641BC1.9090305@cs.umd.edu> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200706041539.03286.jon@ffconsultancy.com> X-Miltered: at concorde with ID 46642589.002 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; ocaml:01 ocaml:01 filliatre:01 okasaki:01 markus:01 mottl:01 stdlib:01 iter:01 foo:01 indirection:01 read-only:01 read-only:01 indirection:01 functors:01 polymorphism:01 On Monday 04 June 2007 15:03:45 Mike Furr wrote: > My OCaml summer project to build an improved data structure library This is an absolutely incredible project and I am eagerly awaiting your results. As I am sure you already know, Jean-Christophe Filliatre, Chris Okasaki and Markus Mottl have done fantastic work in this area already. I would be very happy to see this collated. Diego Fernandez also did some good work with Baire but it seems to have evaporated. I'll gladly submit my stdlib2 if you're interested. Its main benefit is autogenerated functions (like iter, map, fold) that act upon tuples of different arities: let fa, fb, fc = T3.map foo (a, b, c) You might also consider lazy rebalancing, as rebalancing is both expensive and often unnecessary. > forcing all invariant information into the last cell. Implementations > that require more than a single value here must use an extra level of > indirection (so in your example, 'inv = height * size). I don't think > this will be too bad for performance since these values only need to be > retrieved for re-balancing leaving read-only operations unaffected. A functional array implemented as a balanced binary tree needs the number of elements (size) of a sub tree just to index into the tree. So that read-only operation must indirect unnecessarily using your approach. However, the indirection is a much smaller overhead compared to the cost of functors or polymorphism when the comparison functions are trivial (which they normally are) using the current approach. My feeling is that the use of functors in Set and Map are more of a hindrance than a benefit. The ubiquity of Hashtbl is testament to this. Also, the FAQ about having to use recursive modules to implement an expr type with a set of exprs in it. Using a record as F# does makes this easier. However, dispatch of comparison by run-time type makes the F# approach safer as well, which is always more important (and I have been bitten by this in OCaml). > However, this has the huge benefit of allowing me to only write *one* > version of find, min/max, fold, iter, etc. for all of the trees I > implement, which in and of itself is a big win. :) Perhaps we should consider the alternative approach where those functions are higher-order functions over the necessary low-level tree functions. This would only need support for inlining to recover optimal performance and it also lets you write the core functions only once. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e