[Haskell-cafe] Re: Performance of functional priority queues

[GüŸnther Schmidt]

Hi Richard,

just a wiiild guess on this, but anyway.

Maybe Oleg has something to say on this, in particular when it comes to 
his domain, ie. "delimited continuations".

As I said, just a wild guess.

Günther


Richard O'Keefe schrieb:
> 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.  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?