[Haskell-cafe] Performance of functional priority queues

[Svein Ove Aas]

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