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

[Ryan Ingram]

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).

> Also, in
> assertions about "the same asymptotic bounds", in this and a previous
> post in this thread, a distinction is important between worst-case and
> amortized costs. Just to complete the picture...

That's true, but I think the more important distinction is the
constant attached to the big O; persistent data structures tend to
have much worse constant factors and those factors translate to a
general 2x-3x slowdown.  It's often true that a worse asymptotic cost
algorithm is better because the constant factors are much better and
the expected N in your program is small enough.

  -- ryan