Re: [Caml-list] Comparison of OCaml and MLton for numerics

[Jon Harrop <jon@ffconsultancy.com>]

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