Re: [Haskell-cafe] Performance of functional priority queues

2009/12/25 Svein Ove Aas :

On Mon, Jun 15, 2009 at 4:18 AM, Richard O'Keefe 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.

To be fair, I am not aware of any asymptotically efficient (as efficient as their imperative counterparts) purely functional (t.i. not using mutation) implementations of, say, the "union-find" datastructure. However, that does not pose any constraints on the efficiency of Haskell because of the existence of the ST monad.

-- Svein Ove Aas _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Web IR developer, market.yandex.ru