More compact Prio queues

For plain queues, we can trim wasted space by changing

data Plain.Zero a = Plain.Zero

newtype Plain.Zero a = Plain.Zero a

and recover the extra flexibility we need with a wrapper in front. This approach doesn't really work for Prio queues, because data Zero k a = Zero !k a needs three words for the Zero constructor.

In the shower just now, I realized there's probably a way to do it which is even simpler than what we can do for plain queues: store the value associated with each key as its rightmost child.

data Succ rk k a = Succ {-# UNPACK #-} !(BinomTree k a) !(rk k a)
newtype Zero k a = Zero a -- Stores a value
data BinomTree rk k a = BinomTree !k (rk k a) -- No value field; the second field must be lazy
data BinomForest rk k a
  = Nil
  | Skip (BinomForest (Succ rk) k a)
  | Cons {-# UNPACK #-} !(BinomTree rk k a) (BinomForest (Succ rk) k a)

tip :: k -> a -> BinomTree Zero a
tip k a = BinomTree k (Zero a)

incr :: BinomTree rk a -> BinomForest rk a -> BinomForest rk a
incr t Nil = Cons t Nil
incr t (Skip f) = Cons t f
incr t1@(BinomTree k1 ts1) (Cons t2@(BinomTree k2 ts2) !f)
  | k1 <= k2
  = Skip $ incr (BinomTree k1 (Succ t2 ts1)) f
  | otherwise
  = Skip $ incr (BinomTree k2 (Succ t1 ts2)) f

On extraction, we wait for the value associated with the minimal key to be revealed at the top; no problem.

Where this technique might run into some minor difficulties is with unordered operations (including mapWithKey). I haven't worked through how those need to go yet, but they'll certainly be more complex than what we do now. Still, getting more compact queues without compromising complexity or performance of the key operations seems likely to be an overall win.

lspitzner / pqueue

More compact Prio queues #115