[Haskell-cafe] implementing python-style dictionary in Haskell
voigt at tcs.inf.tu-dresden.de
Sun Nov 23 02:11:53 EST 2008
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
mailto:voigt at tcs.inf.tu-dresden.de
More information about the Haskell-Cafe