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 <[EMAIL PROTECTED]> 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 [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
_______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
