On Sun, Jun 14, 2009 at 9:18 PM, Richard O'Keefe <o...@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@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
