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