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

Ryan Ingram wrote:

On Tue, Nov 18, 2008 at 12:46 PM, Luke Palmer 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@tcs.inf.tu-dresden.de