[Haskell] ANN: Reusable Corecursive Queues via Continuations
leon.p.smith at gmail.com
Mon Jun 22 22:31:34 EDT 2009
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,” 
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 , 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.
 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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell