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