[Haskell-cafe] Performance of functional priority queues

[Eugene Kirpichov]

2009/12/25 Svein Ove Aas <svein.ove at aas.no>:
> 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.
>

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



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