I'm trying my hand at making an improved, more efficient, Sieve of Eratosthenes implementation based on Melissa O'Neil's paper (http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf) to augment the inefficient not-Sieve I've documented at http://en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell).  To get the most efficient version that she outlines in her paper, I've had to implement a priority queue.  Being a lazy^Wsmart programmer, I hunted for an implementation of a priority queue and found one at http://www.haskell.org/haskellwiki/Haskell_Quiz/Astar/Solution_Dolio which I promptly nicked and modified to suit the interface Melissa's code requires.  I then documented it exhaustively.  The output of this can be found at http://en.literateprograms.org/Priority_Queue_(Haskell).  (I'd appreciate any vetting people could make -- I did some minimal testing of my own, but some more experienced eyes will likely spot edge cases I'm not able to at this point.)

The vetting, however, isn't my main point.  My main point is the priority queue as found on the Haskell Wiki.  While I was explaining the code of my priority queue, I spotted something odd: although the queue is structured, essentially, as a binary tree (Branch key value leftNode rightNode), I could see no operations at all that ever put anything in the right node.  Ever.  At all.  Thinking this was because of the weird interface I put on the priority queue, I went back to look at the place I stole it from.  There, too, I could see no operations at all that put anything into the right node.  This bothers me a bit (to put it mildly) because it seems I'm carrying around this one data element that's perpetually set to "Nil" and that I'm basically now having my "priority queue" devolve, in effect, into a sorted list.

Am I missing something obvious?  If so, what is it?  If not, should I just bite the bullet and change my priority queue implementation into a sorted list or is there a way to actually use a binary tree there?

-- Michael T. Richter <ttmrichter@gmail.com> (GoogleTalk: ttmrichter@gmail.com) Theory is knowledge that doesn't work. Practice is when everything works and you don't know why. (Hermann Hesse)