[Haskell-cafe] Re: Literate Priority Queue, plus question

[apfelmus]

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