[Haskell-cafe] trees and pointers

[Victor Gorokhov]

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