Proposal: priority queues in containers

[Yitzchak Gale]

Louis Wasserman wrote:
> ...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...
> which is guaranteed to perform efficiently and correctly.

This is a good goal.

> ...There's a reason, however, that Data.Map exists...
> I think priority queues are ubiquitous enough to deserve the same treatment.

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. 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