Oh, god, so much to respond to...heh.

 Submit this package for canonicalization as part of the Haskell Platform. I would for one would support its inclusion.

This is an option I seriously hadn't considered.  To be fair, that's because I've never used the Platform myself, preferring rather to have the most up-to-date version of GHC at all times, heh.  That said, while I'd be okay with this option, I'd prefer putting it into containers, because I feel like a canonical, reliable priority queue implementation is the sort of thing a self-respecting language ought to have built in.

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.

I don't know Python, but according to Wikipedia, dict and set are built into the language.  I don't think it's a fair comparison: set and dict in Python seem to have a role almost as ubiquitous as [] in Haskell, much more ubiquitous than e.g. Data.Set or Data.Map.  I'm also not entirely sure that "batteries included" doesn't describe containers, given all the other packages that come with GHC.

 >   * There is no distinction between keys and priority values.  A utility type
 >     Prio p a with the instance Ord p => Ord (Prio p a) is exported to allow
 >     usage of distinct keys and priority values. 
I disagree with this one.  It requires an Ord instance that isn't really an ordering, and makes a Functor instance impossible.  I would prefer an interface separating keys and values like that of Data.Map (which would also increase consistency within the package).

I'd be okay with separating out a priority/value version.  However, I'm still clueless as to what you're talking about with respect to Functor -- what's wrong with the following?
data Prio p a = Prio p a
instance Ord p => Ord (Prio p a) where ...
instance Functor (Prio p) where fmap f (Prio p a) = Prio p (f a)

I can understand if you're uncomfortable with (==) and (\ x y -> compare x y == EQ) being inequivalent, but neither the H98 Report nor the Prelude make any such claim, as far as I can tell.

 The Foldable instance breaks the abstraction.  I think it should process elements in order.

I think that wanting to iterate over the priority queue in the middle of the computation, without caring about order, is a perfectly legitimate desire for a programmer!  Moreover, the only way to make a Foldable instance process elements in order would be something like
data Ord a => PQueue a = ....
which I think is an awfully dirty approach.  I'm not at all a fan of adding restrictions like that, not least because it adds lots of awkward overhead.
Would you be okay with not exporting a Foldable instance at all, but still exporting a toList method which doesn't guarantee any ordering on the return list?

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.

I'm...not sure how to respond to this claim.  At least part of me wants to say, I genuinely do think the containers package is a piece of art...and then another part pipes up, "except for the inconsistencies between the various minView/maxView versions, and the little differences between IntMap and Map, and..."  That said, I wouldn't be a fan of scrapping the style which the containers package has at least tried to create.  I could be convinced that rewriting the rest of containers would be a good thing to do, though...and I might just want to do that myself.  Hah.

 How does this implementation compare with using Map/Set as a priority queue?

Continuing the discussion of the benchmarks: first, Jim, it appears that I'm the one who made a n00b benchmarking error.  TT_____TT  That said, as you found, my implementation is still slightly faster when the benchmark is corrected.  Some comments:
Sorting 500,000 elements, compiled with -O2, run with +RTS -H128m -K64m, with another few implementations thrown in for good measure:
Times (ms)
               min      mean      +/-sd    median      max  
Pairing:    1440.090  1482.893    31.501  1482.093  1532.095
Binomial:   1356.084  1389.687    26.881  1388.087  1436.090
SBinomial:  1376.086  1422.489    48.453  1400.088  1520.095
Data.Set:   1712.107  1800.912    74.880  1782.111  1976.123
Skew:       1584.099  1644.503    85.702  1602.101  1848.116

Some other benchmarks were done by Milan Straka earlier, when we hadn't decided what heap implementation to use at all.  His comments:
I think the pairing heaps are out of the question now. I would choose between Binomial and Leftist. The Binomial have O(1) amortized inserts, but beware, that this does not work in persistent setting -- the insert is O(log N) when the heaps are used persistently (there are Skew Binomial Heaps with O(1) insert in the persistent setting too). 
 I vote for current (v5) Binomial implementation, even if the O(1) amortized inserts works only non-persistently (ie. under heavy persistent usage, leftist heaps might be a _little_ better).

Conclusions: There aren't any differences in asymptotics, and as it stands, the existing implementation is just as fast.  It's also a) done, and b) full of Haskellish type goodness.

After about five hours' work (!!!) I *finally* managed to install Criterion yesterday, so I'll send out those tests ASAP.

Louis Wasserman
wasserman.louis@gmail.com
http://profiles.google.com/wasserman.louis