Re: [Caml-list] Functional arrays

[Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@etu.upmc.fr>]

    Bonjour,


> > > Incidentally, does anyone have a functional array implementation

As far as I know there are 3 main techniques to implement functional
arrays :

- version arrays
- maps with indexed access
- random acces lists


A version array is a classical array (O(1) acces) where persistance is
handled by 'indirection' and 'cache' : a pointer based mechanism
allows you to restore the complete history of the array by writing
back when needed this information in the main array.

classical examples :

- an array of stamped lists (confer to the ML version of Martin
Erwing's functional graph library)

- an array of trees (confer to the work of Melissa O'Neill where the
underlying trees are splay trees - she has written a Master Thesis, a
JFP paper and part of her doctoral dissetation on the subject)



The other two techniques handle persistency by copying and sharing (as
usual in functional programming).

- The map family is just a classical tree-like data structure
optimized for fast index location (the n-th element). Usually, the
balanced scheme used is Stephen Adam's weight-balanced trees because
memoizing in every node the size of the subtree allows a fast index
computation (see Baire, /set folder)

- The random acces list family is based on the isomorphism of binary
numbers and a list of increasing 2^k sized trees. There are many well
known data structures that can be seen as a particular case of this
scheme including binomial heaps (Vuillemin) and their amortized
variants (Okasaki-Brodal), and functional arrays (Okasaki)

You will find functional arrays code in
- Edison (Okasaki's Haskell data structure library)
- Markus Mottl port of Okasaki's book
- Baire

> Well, by "array" I mean a container with O(1) random access where
> "n" is the number of elements already in the container.

- version array O(1) access to the current array / up to O(n) for
previous versions
- maps O(log n) access to all arrays
- ral O(log n) access to all arrays


        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners