Priority queues and Erlang

[Imre Palik]

> Feladó: John Haugeland [stonecypher@REDACTED]
>
> If I remember correctly, it is not possible to implement an efficient
> priority queue without mutability, which is well demonstrated in CLRS.

Where in the CLRS?

AFAIK you cannot implement an efficient decrease key operation with
persistency.  Which is needed for efficient implementations of e.g. Dijkstra's
algorithm on dense graphs.  But for a barebone priority queue you don't
need that.

>  The general performance of a tree cannot be matched, let alone
> beaten, by an immutable priority queue.

You are comparing apples and oranges here.

>  The priority queue in that
> PFDS book is, essentially, a naive joke (which isn't surprising, given
> that the book is named for pure functionality when it's actually about
> immutability, a difference Okasaki doesn't seem to understand; he
> frequently compares functional datastructures to imperative
> datastructures, which is hilarious.)  There is no purpose to
> implementing a priority queue in Erlang until mutability is available.

Trying to be offensive?
I had pretty good reasons to implement one ;-)
BTW how do you do mutability without side effect? ;-)
Also, mutability is available in erlang.  You know the old maxim: Write in C ;-)

> I would love to be proven wrong with benchmarks, though; a priority
> queue would be epic useful to me in Erlang.

Then stop bitching and write one for yourself.  If it is epic useful, e.g.,
moving from O(N^2) memory, to O(lg N) and from O(N^1.5) speed to O(N/lg N),
then it will pay off.  And if you are half as knowledgable with data structures as you,
claim, it would have taken less time than to write your mail.

I.