Proposal: priority queues in containers

[Louis Wasserman]

Also, looking through the packages you linked to: "queue" and
"priority-queue" seem to have extremely icky interfaces, nothing as readable
as a containers module.  "pure-priority-queue" is a wrapper around Data.Map,
which is definitely slower than a specialized priority queue.

Similarly, "fingertree-psqueue" and "PSQueue", while they expose nicely
readable interfaces, are *priority search queues,* which provide
considerably stronger functionality than a priority queue.  (Specifically,
they provide things like lookup-priority and increase-priority.)  When being
used as a vanilla priority queue, PSQs are considerably slower than
specialized priority queues -- this was one of the implementations we
tested.

The priority search queue is a useful structure for a number of
applications, but much more commonly, a simple priority queue is all that is
required.  In particular, both the C++ STL and java.util.* provide just a
vanilla priority queue, reflecting those design choices in those languages.


Since priority search queues are actually much more natural in imperative
languages than in functional languages -- since we can maintain pointers to
the node associated with each key -- I think it makes even less sense for
Haskell to use PSQueues in containers.  I think it's fair to say that most
algorithms which need it only really require priority queues, and that it
makes sense to provide for that majority in containers, though we might
consider recommending the PSQueue package to programmers who need the full
power of priority search queues.

My own queuelike library...is decent, but not spectacular, and reflected
some early experimentation.  The implementation attached to the ticket,
however, is more reliable than the implementations I wrote in queuelike.
 (In particular, Data.PQueue has worst-case O(n) delete-min, and in a
persistent context, its amortized performance is still O(n).  Ouch.)

Louis Wasserman
wasserman.louis at gmail.com
http://profiles.google.com/wasserman.louis
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20100316/7cafaec0/attachment.html