I’m proud to announce
that a draft of the release of my paper, “Lloyd Allison’s Corecursive Queues: Why Continuations Matter“, is now available. (Source code available here, with a hackage package soon to come available here) Wouter Swierstra has informed me that he will publish it in the Monad Reader. However, it will appear in the next issue after the upcoming one, due to an unexpectedly large number of submissions this time around. Here is the abstract:
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.
While Allison’s queues are general, in the sense it is straightforward to adapt his technique to a new algorithm, a significant problem has been the lack of a reusable library implementation. This paper solves this problem through the use of a monadic interface and continuations.
Because Allison’s queues are not fully persistent, they cannot be first class values. Rather, they are encoded in particular algorithms written in an extended continuation passing style. In direct style, this extension corresponds to
mapCont, a control operator found in
Control.Monad.Cont, part of the Monad Template Library for Haskell. This paper conjectures that
mapContcannot be expressed in terms of
I intend to include a careful performance comparison before this becomes an official Monad Reader article. Allison’s queues come out very well; often better than two stack queues. I have conducted a careful performance comparison in the past, although with older versions of GHC, and older versions of my code. While I did take reasonably careful notes, things have changed. Haskell being what it is, figuring out why is often a challenge. In the meantime I am interested in feedback.
For fun, here is something I wrote right after I first came up with the basic idea behind the paper. It’s still the best error message I’ve gotten out of GHC. Kudos to whomever came up with that strategically placed bit of humor!
Thursday, August 25th, 2005, 5:22 am: Back to the Future
I’ve been up all night, but I now have a working fragment of computer code that is entirely too cute. It’s easily the cleverest bit I’ve written in years. I managed to implement… a queue.
Yes, a queue. One queue, not two. One purely functional queue, with one esoteric implementation! On my penultimate attempt, which was an utter failure except that it got me thinking in the right direction, I came by the most amusing error message I’ve seen to date out of GHC:leon@deleon:~/Programs/snippets $ ghci -fglasgow-exts Queue.hs ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.2.2, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base ... linking ... done. Compiling Queue ( Queue.hs, interpreted ) Queue.hs:84: My brain just exploded. I can't handle pattern bindings for existentially-quantified constructors. ... Failed, modules loaded: none. Prelude>
Yeah, mine did too. Even I don’t fully understand my own code yet.
It should be noted that I knew full well that the code I was trying wouldn’t work… but after hours of bewilderment, not even trying to load anything into GHCi, for amusement’s sake I simply had to try something.
Update: (March 23)
— Data.Sequence is not a real time queue: rather, they are amortized.
— Added citation to Chris Okasaki’s Purely Functional Data Structures
— Other minor changes