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

On Tue, Nov 18, 2008 at 8:51 PM, 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?

But that requires a special reimplementation.

...

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, but the constant hidden inside the O() will generally be worse.

I say this as a goal. If we're in a performance competition, we can't say "well, it's okay that Haskell is slower because its data structures can be used persistently". Python's dictionaries can also, by inserting explicit copies. In this use case Python performs better, and we should strive to perform as well as it does. Persistence has no bearing on this, because the persistence is not used. I'm not saying it's always possible to perform just as well. But persistence *by itself* is not a valid argument for poor performance. Luke