Feedback request: priority queues in containers

[Jim Apple]

> I wrote a pretty efficient skew binomial heap implementation -- the first
> step of Okasaki's approach -- and found it was already slower than the
> optimized binomial heap.  I'm not sure whether or not I uploaded that
> benchmark, though.  I'll do that at some point today, just to keep everyone
> happy.

The skew binomial heaps you implemented should only be asymptotically
faster than the usual binomial heaps on one special case: comparing a
binomial heap in a state that would case an \Omega(lg n) time cascade
on insert to the worst-case O(1) insert of binomial heaps.

I think it would also be worth comparing binomial heap merge against
Brodal-Okasaki heap merge.

Finally, if speed is the ultimate goal, I suspect the clever nested
type approach to guaranteeing binomial tree shape slows things down a
bit. For reference, the type in the latest patch is:

data BinomForest rk a = Nil
                      | Skip !(BinomForest (Succ rk) a)
                      | Cons {-# UNPACK #-} !(BinomTree rk a)
!(BinomForest (Succ rk) a)

data BinomTree rk a = BinomTree a (rk a)

data Succ rk a = Succ {-# UNPACK #-} !(BinomTree rk a) (rk a)

data Zero a = Zero

I suspect the following might be faster:

data BinomForest2 a = Empty
                    | NonEmpty a [BinomTree2 a]

data BinomTree2 a = BinomTree2 a [BinomTree2 a]

This eliminates the "Skip" constructor, which contributes only to the
nested type guarantee.