>> 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.
He is cuckoo, and here's proof: http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf <http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf>This demonstrates a functional priority queue that performs every desired operation in asymptotically optimal time. Granting that its constant factor could be significantly improved, realize that there are more complicated functional data structures with similar asymptotic guarantees. (Observation: I'm pretty sure that the Fibonacci heap is actually surprisingly functional.) Louis Wasserman wasserman.lo...@gmail.com http://profiles.google.com/wasserman.louis
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
