[Haskell-cafe] Performance of functional priority queues

[Luke Palmer]

On Sun, Jun 14, 2009 at 9:18 PM, Richard O'Keefe <ok at cs.otago.ac.nz> wrote:

> There's a current thread in the Erlang mailing list about
> priority queues.  I'm aware of, for example, the Brodal/Okasaki
> paper and the David King paper. I'm also aware of James Cook's
> priority queue package in Hackage, have my own copy of Okasaki's
> book, and have just spent an hour searching the web.
>
> One of the correspondents in that thread claims that it is
> provably impossible to have an efficient priority queue implementation
> without mutability.


If he so claims, maybe you can challenge him by asking for a proof?

Such a proof would probably only involve asymptotics, since it's very hard
to *prove* anything when actual raw speed is involved.   If that's the case,
you can use Okasaki to back yourself up (or back him up; I am not familiar
with the results in this area).

I've seen in a few programming circles now that "provably" is used as a
weasel word.  Provably, eh?  Where's the proof?

Luke



>  I think he's cuckoo.  But I'd like to have some
> numbers to back me up.
>
> Can anyone point me to some actual benchmark results comparing
> priority queue performance *with* mutation and priority queue
> performance *without* mutation, in the same functional or
> mostly-functional language?
>
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090615/19a88207/attachment.html