Forgot the reply-to-all....

---------- Forwarded message ----------
From: Till Varoquaux <till.varoquaux@gmail.com>
Date: Jun 5, 2007 12:18 AM
Subject: Re: [Caml-list] Comparison of OCaml and MLton for numerics
To: skaller <skaller@users.sourceforge.net>


Hmm....

At a first glance these could be translated to persistent data
structures, although with a cost  (they are "upside down": inserting a
new element modifies one of the leafs... but this is also the case
with red/black trees). It doesn't seem to me that most operations
would be O(1) (sounds too good to be true anyways*), I'd rather guess
O(ln(n)) (where log is base 256 and n is length of the element we are
storing/querying etc...). I do wonder how well these would scale when
used with big elements. they might prove an interesting back-end for
an implementation of maps (values would be stored in the nodes).

Most of the optimizations seem to reside more on the low level details
of the implementation rather than on the algorithmic side (which seems
fairly classical from a distance).

For more functional data structures you might be interested by vlists.
There is even an OCaml version.

Regards,
Till

* Since hashtables have to deal with collisions and hashing of large
values, I do not consider their operations to be O(1).
[1]http://en.wikipedia.org/wiki/VList
[2]http://www.imada.sdu.dk/~bardur/personal/45-programs/index.html


On 6/4/07, skaller <skaller@users.sourceforge.net> wrote:
> On Mon, 2007-06-04 at 15:39 +0100, Jon Harrop wrote:
>
> > 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.
>
> It might be worth considering a functional version of Judy arrays:
>
> http://judy.sourceforge.net/
>
> They're fairly close to ideal: all operations are O(1),
> they never need rebalancing, and they work just as well with
> sparse arrays as compact ones. Judy arrays are digital tries
> with compressed nodes. It's not clear whether a functional
> variation would retain the performance claimed for the mutable
> version.
>
> --
> John Skaller <skaller at users dot sf dot net>
> Felix, successor to C++: http://felix.sf.net
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>