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.<br>
<br>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.<br>
<br>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 (>>=). <br>
<br>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. <br>
<br>[1] <a href="http://www.csse.monash.edu.au/~lloyd/tildeFP/1989SPE/">http://www.csse.monash.edu.au/~lloyd/tildeFP/1989SPE/</a><br>[2] <a href="http://hackage.haskell.org/package/control-monad-queue">http://hackage.haskell.org/package/control-monad-queue</a><br>
[3] <a href="http://blog.melding-monads.com/2009/06/22/control-monad-queue/">http://blog.melding-monads.com/2009/06/22/control-monad-queue/</a><br><br>Best,<br>Leon<br>