Priority queues and Erlang

[John Haugeland]

> I was surprised to discover that there is no priority queue
> implementation in OTP.  This was a few years back when
> I needed one. I don't know if that has changed lately.
> It seems like an obvious extension to the queue module.

If I remember correctly, it is not possible to implement an efficient
priority queue without mutability, which is well demonstrated in CLRS.
 The general performance of a tree cannot be matched, let alone
beaten, by an immutable priority queue.  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.

It is possible through skew binomial queues to achieve better
theoretical growth cases than the trees have, but the linear overhead
is so large that you're talking several tens of gigabytes before they
become even remotely competitive.  It's kind of like how if you have a
C++ container with 20 or so elements, bubble sort pantses almost every
other sort, despite being ridiculously inappropriate in nearly any
other context, except that in this case, the case sample is basically
everything that's done with computers in the normal world today and
for the forseeable next decade easy.

It's the same reason so many other fundamental datastructures are
missing: they just aren't practical in immutable languages.  Skew
trees, splay trees, judy trees, julia trees, Knuth's Algorithm X
container, Zobrist hashing, basically any ply tree strategy, basically
every tree culling algorithm, et cetera - half of the stuff you find
in NIST DADS - are casualties.  Erlang can't have real mtd(f).  Erlang
can't have real A*.  Erlang can't have real negascout.  Erlang can't
have real stochastic octrees.  Erlang can't have half the stuff you
want for caching.

You'd do well to just write an interface for a tree or hash to get the
expected API behavior and call it a day.  If you can't, it's time to
write a port.

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