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

Ryan Ingram wrote:

On Sat, Nov 22, 2008 at 5:33 AM, Janis Voigtlaender 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@tcs.inf.tu-dresden.de