Clever type nesting techniques for ensuring the structural correctness of binomial heaps have been invented before, including the technique that Louis Wasserman implemented so efficiently for his recent proposal http://hackage.haskell.org/trac/ghc/ticket/3909 . Perhaps these previous techniques could make the nested priority queue implementation even more efiicient. Ralf Hinze: (uses a different(?) extractMin algorithm) http://web.comlab.ox.ac.uk/oucl/work/ralf.hinze/publications/IAI-TR-98-12.ps... Mirror: http://scholar.google.com/scholar?cluster=5719010893172593338 Chris Okasaki: (stores children in a difference list to make their reversal fast) http://okasaki.blogspot.com/2009/10/binomial-queues-as-nested-type.html Bertram Felgenhauer: (suggests some space savings) http://www.haskell.org/pipermail/haskell-cafe/2009-October/068351.html Mirror: http://groups.google.com/group/fa.haskell/msg/cdffdbb12b28e027 Mirror 2: http://article.gmane.org/gmane.comp.lang.haskell.cafe/65428