Thanks for an example! Probably, one can think about using Arrays
instead of Map or IntMap in order to achieve 'true' O(1) in pure. But
I suppose that there are some trouble with array expanding. Or
somebody would already make it.
Pure arrays have O(n) modification time.
From the docs, lookup is O(min(n,W))
Actually worse than O(log n).
B-tree with 4 or even 8 child nodes will be the best solution. This
trees have better lookup time and worse space efficiency, but we can
almost eliminate space overhead by using dense keys.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
