Dear Magnus,
I wonder what the performance of the FiniteMap type is in Haskell. Lookup is of course done in O(log n) but is insertion done in O(n) or O(log n)? ... If it belongs to O(n), aren't the maps really really useless? If it belongs to O(log n), how is this achieved? (my guess is that it is O(n) of course : )
I have once been thinking the same, but you can rest assured, insert is O(log n) (for a balanced tree map implementation). A pure language must indeed copy its values (since it is a new one) but it can also *share* values that stay the same. In the case of the balanced tree, the "path" to the inserted node will be copied since they consist of new and different nodes, but all the subtrees of this path stay the same and will be shared among all new insertions. It is rather mind-boggling when you start thinking about how the actual heap looks after a while, but fortunately, you never have to think about that in Haskell :-) (btw. This is really fun to watch if you got a tool like the graphical Hood). All the best, Daan. ps. I have written a fairly extensive (and documented) data structure library called DData that has efficient Maps, Sets, Bags etc. Also works well with Hugs and other haskell98 compilers. http://www.cs.uu.nl/~daan/ddata.html
For example, does the function
addToFM :: Ord key => FiniteMap key elt -> key -> elt -> FiniteMap key elt
belong to O(n) or O(log n) (where n is the size of the map) ?
If it belongs to O(n), aren't the maps really really useless? If it belongs to O(log n), how is this achieved? (my guess is that it is O(n) of course : )
Best regards, Magnus Lindberg _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell