Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] const equivalent for mutable types?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@e...>
Subject: Re: [Caml-list] Functional arrays

> > > 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 Archives:
Bug reports: FAQ:
Beginner's list: