[Haskell-cafe] implementing python-style dictionary in Haskell

[Janis Voigtlaender]

Ryan Ingram wrote:
> On Sat, Nov 22, 2008 at 5:33 AM, Janis Voigtlaender
> <voigt at tcs.inf.tu-dresden.de> wrote:
> 
>>>You can generally make a persistent data structure with the same
>>>asymptotic bounds as the ephemeral structure, ...
>>
>>I would be very careful with the "generally" here. At least, I am not
>>aware that this has been proved to always be possible.
> 
> 
> Here's an informal proof:
> 
> You can use an intmap to emulate pointers, to turn any ephemeral data
> structure into a persistent one.  That adds at most a log-n factor to
> lookups and updates.  For many structures, this is enough to prove
> asymptotic bounds equivalence.
> 
> However, the standard 'pointer' model for ephemeral structures makes
> the assumption that memory size is limited; otherwise you have to add
> a log(n) factor there anyways, both to hold the large pointer values
> that get generated and to actually send the bits to the memory bus.
> Given this assumption you can take log(memory size) as a constant and
> argue that pointer lookup and update via the map is O(1).

Ah, that makes sense.

-- 
Dr. Janis Voigtlaender
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:voigt at tcs.inf.tu-dresden.de