Proposal: priority queues in containers

[Louis Wasserman]

Okay, here's my current plan:  I think I'm going to withdraw the ticket for
containers, and launch a package to be included in a future release of the
Haskell Platform.

First off, I'd like to know what the procedure is for adding something to
the Platform.  I haven't been able to find a mailing list dedicated to it,
so I don't know where it should be discussed.  (In all likelihood, I'm
missing some obvious link on either Trac or HaskellWiki or something...)

First, people should look at my current setup, and complain at me about the
design.  Haddock documentation is
here<http://code.haskell.org/containers-pqueue/pqueue-1.0.0/html/>,
though I've only so far documented the minimum-queue variants; in general, I
aimed to use the same function names used by Data.Map and Data.Set wherever
possible, so "extract," "top," and "delete" have been replaced by the
function names used for the analogous methods in Data.Map and Data.Set.

Probably the single aspect of the design I'm least happy about is how I
distinguish between the priority queues that distinguish a key and an
element, and those which don't.  Currently, the Data.Map-style key/element
version is named MinPQueue k a, and lives in the module
Data.PQueue.Prio.Min, and the Data.Set-style version is named MinQueue a,
and lives in the module Data.PQueue.Min.  Can anybody think of better names
for these things?

Finally, I'm not going to consider any more alternative implementations at
this point.  My implementation has performed outstandingly on benchmarks,
and has beaten a number of competitors.  If someone believes that they have
a superior implementation, they should email me off-list, and perhaps a
later version of the package will be based on a different implementation,
but for the moment I'm sticking to the type-magical binomial heap
implementation.

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/20100321/0506e1d8/attachment.html