[Haskell-cafe] trees and pointers

Victor Gorokhov me at rkit.pp.ru
Thu Jul 15 18:33:12 EDT 2010

> 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.

More information about the Haskell-Cafe mailing list