Proposal: priority queues in containers

Louis Wasserman wasserman.louis at
Tue Mar 16 12:54:35 EDT 2010


I wrote this one.  Heh.  This is an improvement on it.

More importantly, what I wanted to achieve by adding priority queues to
containers was having a canonical implementation for a ubiquitous data
structure, which has a simple and user-friendly interface (something the
queuelike package, above, attempts but isn't extraordinarily successful at),
which is guaranteed to perform efficiently and correctly.

As a comparison example, there are many, many finite map implementation
packages.  (I wrote TrieMap, which is a pretty involved automatic
generalized trie map type inference system...yeah.)  There's a reason,
however, that Data.Map exists, and that so many people use it when an
algorithmically superior implementation might exist on Hackage -- because
it's programmer-friendly and accessible, and because its performance is
well-understood and has been thoroughly verified.  When I use Data.Map, I'm
not trusting some random schlub to have written bug-free code -- I'm
trusting the Haskell built-in libraries, and the people who write and
maintain those libraries.

I think priority queues are ubiquitous enough to deserve the same treatment.

On another note, Ian, it's really not very clear what the proper procedure
for adding test suites is.  Is it to just add a tester program separately
from the patch?  Is it to put the test suites somewhere within the
containers folder, and have them be an integral part of the patch?  There
seem to be some sort-of-test-ish files in the containers package already,
but I have no idea how to add new tests, and if the existing interface is
extensible, it's not at all clear how to extend it.
-------------- next part --------------
An HTML attachment was scrubbed...

More information about the Libraries mailing list