[Haskell-cafe] trees and pointers

Jake McArthur jake.mcarthur at gmail.com
Thu Jul 15 09:07:32 EDT 2010


On 07/15/2010 02:30 AM, Stephen Tetley wrote:
> 2010/7/15 Jake McArthur<jake.mcarthur at gmail.com>:
>> On 07/14/2010 05:01 PM, Victor Gorokhov wrote:
>>>
>>> You can implement pure pointers on top of Data.Map with O(log n) time
>>
>> Or on top of Data.IntMap with O(1) time. ;)
>
> Unlikely...
>
>  From the docs, lookup is O(min(n,W))

Exactly. O(min(n,32)) or O(min(n,64))

- Jake


More information about the Haskell-Cafe mailing list