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