Proposal: priority queues in containers

[Bryan O'Sullivan]

On Wed, Mar 17, 2010 at 4:52 AM, Yitzchak Gale <gale at sefer.org> wrote:

> This I'm not sure about. I've considered using PQ's perhaps
> two or three times during the past few years, and ended up not using
> them at all.


I'd prefer for personal anecdote not to be the driver of discussions like
this. Personally, I've never used Data.Tree or Data.Graph from the
containers package, and doubt that I ever will, but it doesn't break my arm
or steal my wristwatch if they're available.

The types in the containers package have subtly different APIs and degrees
of control over things like strictness, and also have almost no test
coverage along with few signs of usage-driven optimisation. The bar for
adding more code to that package is thus pretty low, in my opinion. If I had
time, I'd replace it entirely.

My advice would be not to stress over whether priority queues go into
containers. It's not some pristine thing of beauty that deserves treatment
with velvet gloves. If you want a good source of stress, create a
replacement package that makes me happy :-)


> True, perhaps I would have used them if there had been a
> simple and reliable PQ implementation at my fingertips. But it's
> definitely not a ubiquitous meme like Map or Set.
>
> How about recording this great work as yet one more PQ package
> on hackage. But make it far more usable than all of the others
> by two simple steps:
>
> 1. In the package description, say simply and clearly what purpose
> this package is designed to serve, as you have described in this
> thread.
>
> 2. Submit this package for canonicalization as part of the Haskell
> Platform. I would for one would support its inclusion.
>
> > both the C++ STL and java.util.* provide just a vanilla priority queue,
> > reflecting those design choices in those languages
>
> As does Python. In Python, though, the PQ implementation is not
> a built-in class in the default namespace (as are dict and set).
> Rather, it is one of the "batteries included" libraries that come with
> Python. I think that's the right place for it in Haskell, too.
>
> Please do consider this suggestion. However, if we do not quickly
> reach a consensus on this, I will withdraw my suggestion and advocate
> inclusion in containers as originally proposed. The difference between
> those options is far less important than the risk of losing this great work
> to haggling.
>
> Thanks,
> Yitz
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20100317/eeed190b/attachment.html