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

On Tue, Nov 18, 2008 at 3:46 PM, Luke Palmer wrote:

On Tue, Nov 18, 2008 at 10:37 AM, David Menendez wrote:

...

This isn't really a fair comparison. Map, IntMap, and Trie are persistent data structures, and Python dictionaries are ephemeral. (That is, when you "add" a key to a Map, you actually create a new one that shares structure with the old one, and both can be used in subsequent code. In Python, you would have to copy the dictionary.)

But when these persistent data structures are used in a single-threaded way, why should we not hope for the performance to be comparable?

It may not be easy, but just saying "they are persistent" is not really an excuse.

I guess that depends on what you mean by "comparable". Chris Okasaki demonstrated that, for some data structures, a persistent implementation could be made with the same asymptotic bounds as an ephemeral implementation, but I would still expect the persistent version to be worse by a constant factor when used ephemerally. Ephemeral data structures are naturally optimized for ephemeral use cases. (I would also expect the reverse to be true.) -- Dave Menendez http://www.eyrie.org/~zednenem/