[Haskell-cafe] Performance of functional priority queues

[Richard O'Keefe]

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?