On Mon, Jun 15, 2009 at 4:18 AM, 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. I think he's cuckoo. But I'd like to have some > numbers to back me up. > Regardless of whether he is correct or not, the result would not apply to haskell.
Lazyness can be considered to be a controlled form of mutation, which Okasaki takes advantage of in a number of his data structures. Most (all I've seen) arguments stating that purely functional languages have asymptotic performance worse than mutating languages simply don't apply to lazy ones. -- Svein Ove Aas _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
