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

[Luke Palmer]

On Tue, Nov 18, 2008 at 8:51 PM, Ryan Ingram <ryani.spam at gmail.com> 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?

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