Literate Priority Queue, plus question
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
Michael T. Richter wrote:
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). [...] 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. [...] Am I missing something obvious? If so, what is it?
You're right, it's a serious bug. The last line should read link (Branch k a x y) z = Branch k a y (union x z) The crucial point about priority queues is of course that they run in logarithmic time and this property needs a proof. In other words, explaining an implementation of priority queues without proving that it fulfills this requirement is rather pointless. Lazy skew heaps are thoroughly explained in C. Okasaski. Fun with binary heap trees. In: The Fun of Programming. Palgrave. 2003. http://www.palgrave.com/pdfs/0333992857.pdf but the proof, while simple in practice, may require too much "machinery" (persistence + amortisation + lazy eval) to be reproduced on the literate programming wiki.
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?
To some extend, this would be pointless as well because that would make the Eratosthenes' Sieve inefficient again. It's much easier to stick with the old version then. Regards, apfelmus
apfelmus wrote:
Lazy skew heaps are thoroughly explained in
C. Okasaski. Fun with binary heap trees. In: The Fun of Programming. Palgrave. 2003. http://www.palgrave.com/pdfs/0333992857.pdf
Extremely cool stuff, that. I love it when people write material like this... Unfortunately, so many documents about Haskell are too hard to comprehend. :-(
Hello, On Saturday 16 June 2007 14:53, Michael T. Richter wrote:
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). ...
Surely you know this already, but to make absolutely sure: There was a lot of discussion on this subject on this mailing list a while back. Melissa O'Neill's own entry into this is http://www.haskell.org/pipermail/haskell-cafe/2007-February/022666.html as far as I can tell and you can go both forwards and backwards from there. Best regards Thorkil
participants (4)
-
Andrew Coppin -
apfelmus -
Michael T. Richter -
Thorkil Naur