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

Janis Voigtlaender voigt at tcs.inf.tu-dresden.de
Sat Nov 22 08:33:32 EST 2008

Ryan Ingram wrote:
> On Tue, Nov 18, 2008 at 12:46 PM, Luke Palmer <lrpalmer at gmail.com> wrote:
>>But when these persistent data structures are used in a
>>single-threaded way, why should we not hope for the performance to be
> If you can guarantee single-threaded use, then you can just use ST and
> implement the ephemeral structure, right?
>>It may not be easy, but just saying "they are persistent" is not
>>really an excuse.
> 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. 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...

Ciao, Janis.

Dr. Janis Voigtlaender
mailto:voigt at tcs.inf.tu-dresden.de

More information about the Haskell-Cafe mailing list