[Haskell-cafe] trees and pointers

Jake McArthur jake.mcarthur at gmail.com
Thu Jul 15 23:26:22 EDT 2010

On 07/15/2010 05:33 PM, Victor Gorokhov wrote:
>> 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.

Excluding DiffArray under certain usage patterns of course, but 
DiffArray is slow for unknown reasons besides algorithmic complexity.

>> From the docs, lookup is O(min(n,W))
> Actually worse than O(log n).

Perhaps I am misunderstanding you, but O(min(n,W)) is either better than 
or the same as O(log n), depending on how you look at things, but I 
don't see any way that the former could be *worse* than the latter.

- Jake

More information about the Haskell-Cafe mailing list