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

[David Menendez]

On Tue, Nov 18, 2008 at 3:46 PM, Luke Palmer <lrpalmer at gmail.com> wrote:
> On Tue, Nov 18, 2008 at 10:37 AM, David Menendez <dave at zednenem.com> 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 <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>