[Haskell] ANN: Reusable Corecursive Queues via Continuations

[Leon Smith]

In a purely functional setting, real-time queues are traditionally thought
to be much harder to implement than either real-time stacks or amortized
O(1) queues.   In “Circular Programs and Self-Referential Structures,” [1]
Lloyd Allison uses corecursion to implement a queue by defining a lazy list
in terms of itself. This provides a simple, efficient, and attractive
implementation of real-time queues.

Now,  control-monad-queue is available on hackage [2],  which offers this
technique in a reusable library.   As Allison's queue is not fully
persistent,  it cannot be a first class value;  rather they are encoded in
specific algorithms written in an extended continuation passing style,  and
the use of continuations seems necessary in order to abstract the
corecursive queue operations.

Also, a substantially revised draft of the associated paper,  "Lloyd
Allison's Corecursive Queues:  Why Continuations Matter" is now available.
[3]   This paper will appear in the upcoming Monad Reader issue 14,  and
comments would be most appreciated.    It derives a reusable implementation
in an explicit continuation-passing style from Allison's original code,
demonstrates an alternate reusable implementation in direct style using
mapCont,   and argues that mapCont cannot be expressed in terms of callCC,
return, and (>>=).

Finally, this approach performs well in practice,  when compiled with
optimization using GHC.   However,  performance has regressed from GHC 6.8.3
to 6.10.3,  and there is a curious performance anomaly associated with the
generalized corecursive abstraction.

[1]   http://www.csse.monash.edu.au/~lloyd/tildeFP/1989SPE/
[2]   http://hackage.haskell.org/package/control-monad-queue
[3]   http://blog.melding-monads.com/2009/06/22/control-monad-queue/

Best,
Leon
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell/attachments/20090622/20cb582a/attachment-0001.html