from array update algorithm to nice Haskell code

[Daan Leijen]

Hi Wolfgang,

> is there some documentation about the complexity of the FiniteMap and Set operations?

My DData library gives some useful links to papers about this subject, also
take a look at the "IntSet" and "IntMap" libraries as they have an interesting
complexity class. Also, all DData functions have their complexity listed in the documentation.

See: <http://www.cs.uu.nl/~daan/ddata.html>

The operations in the "Data.FiniteMap" library in Ghc have the same complexity
of the operations in the "DData.Map" library. The "Data.Set" library in Ghc is
based on the FiniteMap library (and thus has the same complexity)


On Tue, 30 Dec 2003 23:14:05 +0100, Wolfgang Jeltsch <wolfgang at jeltsch.net> wrote:
> I have an algorithm which updates one or more arrays in a loop.  The update
> operations depend on the (old) contents of the arrays, so I cannot use
> accumArray.  I want to implement this algorithm without mutable arrays in
> Haskell.  Are there any possibilities to do so efficiently?  Are there some
> hints about how to do this?

Storing the incremental changes might be a good options. You can get this
somewhat automatically by using (lazy) balanced trees -- every insertion/update will
only copy the changed 'path' in the tree, giving you a logarithmic copy time
while being persistent (maintaining all old versions).


-- Daan.

>
> Wolfgang
>
> _______________________________________________
> Haskell mailing list
> Haskell at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell
>