On Sun, Jun 14, 2009 at 9:18 PM, 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.
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe