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

[Janis Voigtlaender]

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
>>comparable?
> 
> 
> 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
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:voigt at tcs.inf.tu-dresden.de