control-monad-queue 0.1 → 0.2

raw patch · 7 files changed

+275/−251 lines, 7 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Control/Monad/Queue/Allison.hs +13/−21
• Control/Monad/Queue/Class.hs +21/−0
• Control/Monad/Queue/Corec.hs +12/−22
• Control/Monad/Queue/Util.hs +3/−2
• control-monad-queue.cabal +17/−5
• doc/CorecQueues.bib +12/−7
• doc/CorecQueues.lhs +197/−194

@@ -1,17 +1,13 @@-{-# LANGUAGE MultiParamTypeClasses      #-}-{-# LANGUAGE FunctionalDependencies     #-}-{-# LANGUAGE FlexibleInstances          #-}-{-# LANGUAGE RankNTypes                 #-}+{-# LANGUAGE RankNTypes #-}  ----------------------------------------------------------------------------- -- | -- Module      :  Control.Monad.Queue.Allison--- Copyright   :  (c) Leon P Smith 2009+-- Copyright   :  (c) Leon P Smith 2009-2011 -- License     :  BSD3 ----- Maintainer  :  leon at melding-monads dot com+-- Maintainer  :  leon@melding-monads.com -- Stability   :  experimental--- Portability :  portable -- -- A library implementation of corecursive queues,  see -- /Circular Programs and Self-Referential Structures/ by Lloyd Allison,@@ -21,10 +17,10 @@ -- -- For an explanation of the library implementation, see -- /Lloyd Allison's Corecursive Queues:  Why Continuations Matter/--- by Leon P Smith,  in /The Monad Reader/, Issue 14.   This library+-- by Leon P Smith,  in /The Monad Reader/, Issue 14, Jul 2009.   This library -- corresponds to @CorecQ@ in that paper. ----- <http://themonadreader.files.wordpress.com/2009/07/issue14.pdf>+-- <http://themonadreader.files.wordpress.com/2009/07/issue142.pdf> -- ----------------------------------------------------------------------------- @@ -45,14 +41,19 @@      ,  exit      )  where -import qualified Control.Monad.Queue.Class as Class+import Control.Applicative import Control.Monad.Queue.Util import Data.List(genericIndex, genericTake, genericSplitAt) -type QSt e = LenType -> [e] -> [e]+newtype Q e a = Q { unQ :: Cont (LenType -> [e] -> [e]) a } -newtype Q e a = Q { unQ :: (a -> QSt e) -> QSt e }+instance Functor (Q e) where+  fmap f m  = Q (\k -> unQ m (k . f)) +instance Applicative (Q e) where+  pure a    = Q (\k -> k a)+  f <*> v   = Q (\k -> unQ f (\g -> unQ v (k . g)))+ instance Monad (Q e) where   return a  = Q (\k -> k a)   m >>= f   = Q (\k -> unQ m (\a -> unQ (f a) k))@@ -137,12 +138,3 @@ runQueue m = q   where     q = unQ m (\_ _ _ -> []) 0 q--instance Class.MonadQueue e (Q e) where-  enQ     = enQ-  peekQ   = peekQ-  peekQs  = peekQs-  peekQn  = peekQn-  deQ     = deQ-  deQs    = deQs-  lenQ    = lenQ

@@ -1,5 +1,6 @@ {-# LANGUAGE MultiParamTypeClasses      #-} {-# LANGUAGE FunctionalDependencies     #-}+{-# LANGUAGE FlexibleInstances          #-}  ----------------------------------------------------------------------------- -- |@@ -16,6 +17,8 @@ module Control.Monad.Queue.Class where  import Control.Monad.Queue.Util+import qualified Control.Monad.Queue.Allison as Allison+import qualified Control.Monad.Queue.Corec   as Corec  class Monad q => MonadQueue e q | q -> e where   -- | Enqueue an element to a queue@@ -45,3 +48,21 @@                             (\e ->  do                                     es <- deQs (n-1)                                     return (e:es))++instance MonadQueue e (Allison.Q e) where+  enQ     = Allison.enQ+  peekQ   = Allison.peekQ+  peekQs  = Allison.peekQs+  peekQn  = Allison.peekQn+  deQ     = Allison.deQ+  deQs    = Allison.deQs+  lenQ    = Allison.lenQ++instance MonadQueue e (Corec.Q w e) where+  enQ     = Corec.enQ+  peekQ   = Corec.peekQ+  peekQs  = Corec.peekQs+  peekQn  = Corec.peekQn+  deQ     = Corec.deQ+  deQs    = Corec.deQs+  lenQ    = Corec.lenQ

@@ -1,17 +1,13 @@-{-# LANGUAGE MultiParamTypeClasses      #-}-{-# LANGUAGE FunctionalDependencies     #-}-{-# LANGUAGE FlexibleInstances          #-}-{-# LANGUAGE RankNTypes                 #-}+{-# LANGUAGE RankNTypes #-}  ----------------------------------------------------------------------------- -- | -- Module      :  Control.Monad.Queue.Corec--- Copyright   :  (c) Leon P Smith 2009+-- Copyright   :  (c) Leon P Smith 2009-2011 -- License     :  BSD3 ----- Maintainer  :  leon at melding-monads dot com+-- Maintainer  :  leon@melding-monads.com -- Stability   :  experimental--- Portability :  portable -- -- Corecursive queues with return values.  This is a straightforward -- generalization of Control.Monad.Queue.Allison.   It corresponds to@@ -42,14 +38,19 @@      ,  exit      )  where -import qualified Control.Monad.Queue.Class as Class+import Control.Applicative import Control.Monad.Queue.Util import Data.List(genericIndex, genericTake, genericSplitAt) -type QSt w e = LenType -> [e] -> (w,[e])+newtype Q w e a = Q { unQ :: Cont (LenType -> [e] -> (w,[e])) a } -newtype Q w e a = Q { unQ :: (a -> QSt w e) -> QSt w e }+instance Functor (Q w e) where+  fmap f m  = Q (\k -> unQ m (k . f)) +instance Applicative (Q w e) where+  pure a    = Q (\k -> k a)+  f <*> v   = Q (\k -> unQ f (\g -> unQ v (k . g)))+ instance Monad (Q w e) where   return a  = Q (\k -> k a)   m >>= f   = Q (\k -> unQ m (\a -> unQ (f a) k))@@ -104,7 +105,7 @@        | n <= 0    = k Nothing n q        | otherwise = case q of                       [] -> error "Control.Monad.Queue.Corec.peekQ: empty list"-                      (e:q') -> k (Just e) n q+                      (e:_q') -> k (Just e) n q  -- | Examines the element currently at position @index@ in the queue,  indexing starts from @0@, like '!!' peekQn :: (Integral index) => index -> Q w e (Maybe e)@@ -141,14 +142,12 @@ wfix f = Q (\k n q -> let (w,q') = unQ (f w) k n q                        in (w,q')) - -- | Runs the computation,  returns the result of the computation and a list of all elements enqueued runResultQueue :: Q a e a -> (a,[e]) runResultQueue m = st   where     st@(_a,q) = unQ m (\a _ _ -> (a,[])) 0 q - -- | Runs the computation,  returns the result of the computation -- runResult :: Q a e a -> a@@ -157,12 +156,3 @@ -- | Runs the computation,  returns a list of all elements enqueued runQueue :: Q a e a -> [e] runQueue  = snd . runResultQueue--instance Class.MonadQueue e (Q w e) where-  enQ     = enQ-  peekQ   = peekQ-  peekQs  = peekQs-  peekQn  = peekQn-  deQ     = deQ-  deQs    = deQs-  lenQ    = lenQ

@@ -1,10 +1,10 @@ ----------------------------------------------------------------------------- -- | -- Module      :  Control.Monad.Queue.Util--- Copyright   :  (c) Leon P Smith 2009+-- Copyright   :  (c) Leon P Smith 2009-2011 -- License     :  BSD3 ----- Maintainer  :  leon at melding-monads dot com+-- Maintainer  :  leon@melding-monads.com -- Stability   :  experimental -- Portability :  portable --@@ -15,3 +15,4 @@ import Data.Word  type LenType = Word+type Cont r a = (a -> r) -> r

@@ -1,5 +1,5 @@ Name:                control-monad-queue-Version:             0.1+Version:             0.2 Description:   This library provides efficient real-time queues via self-referential   lazy lists.  The technique was first published in@@ -10,10 +10,13 @@   .   For an explanation of the library implementation, see   /Lloyd Allison's Corecursive Queues:  Why Continuations Matter/-  by Leon P Smith,  in /The Monad Reader/, Issue 14.+  by Leon P Smith,  in /The Monad Reader/, Issue 14,  Jul 2009.   .-  <http://themonadreader.files.wordpress.com/2009/07/issue14.pdf>-+  <http://themonadreader.files.wordpress.com/2009/07/issue142.pdf>+  .+  A lightly edited version of the paper above is available at:+  .+  <http://www.melding-monads.com/files/CorecQueues.pdf> License:             BSD3 License-file:        LICENSE Author:              Leon P Smith <leon@melding-monads.com>@@ -21,7 +24,7 @@ Build-Type:          Simple Category:            Control Synopsis:            Reusable corecursive queues, via continuations.-Cabal-Version:       >=1.2+Cabal-Version:       >=1.6  Library   Build-Depends:     base >= 2 && < 5@@ -29,3 +32,12 @@                      Control.Monad.Queue.Allison                      Control.Monad.Queue.Corec   Other-Modules:     Control.Monad.Queue.Util++source-repository head+  type:      darcs+  location:  http://patch-tag.com/r/lpsmith/control-monad-queue/pullrepo++source-repository this+  type:      darcs+  location:  http://patch-tag.com/r/lpsmith/control-monad-queue/pullrepo+  tag:       0.2

@@ -30,7 +30,7 @@   month   = {Feb},   year    = {1989},   url     = {http://www.csse.monash.edu.au/~lloyd/tildeFP/1989SPE/}-}  +}   @inproceedings{wadler89,@@ -50,27 +50,27 @@ @Article{friedman87,   author    = "Daniel P Friedman and David S Wise",   title     = "Cons should not evaluate it's arguments",-  journal   = "Automata, Languages, and Programming", +  journal   = "Automata, Languages, and Programming",   publisher = "Edinburgh University Press",   pages     = "257--284",   year      = 1976,   url       = {http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR44}, } -@PhdThesis{santos95, +@PhdThesis{santos95,   author = {Andr\'{e} L. M. Santos},   title  = {Compilation by transfomation in non-strict functional languages},   school = {University of Glasgow},   month  = {Jul},   year   = {1995},   url    = {http://www.di.ufpe.br/~alms/ps/thesis.ps.gz},-} +}   @Article{okasaki95,   author  = {Chris Okasaki},   title   = {Simple and Efficient Purely Functional Queues and Deques},-  journal = {Journal of Functional Programming}, +  journal = {Journal of Functional Programming},   volume  = {5},   number  = {4},   pages   = {583--592},@@ -119,7 +119,7 @@ @Book{haskellroad,   author    = {Kees Doets and Jan van Eijck},   title     = {The Haskell Road to Logic, Maths, and Programming},-  publisher = {King's College Publications}, +  publisher = {King's College Publications},   year      = {2004}, } @@ -150,7 +150,7 @@   author    = {Ralf Hinze and Ross Paterson},   title     = {Finger trees: a simple general-purpose data structure},   journal   = {Journal of Functional Programming},-  volume    = {16}, +  volume    = {16},   number    = {2},   pages     = {197--217},   year      = {2006},@@ -177,3 +177,8 @@     year = {1993},     url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.4052}, }++@misc{smith2010,+Author = {Leon P Smith},+Title = {Writer Monads via Continuations},+howpublished = {\url{http://blog.melding-monads.com/2010/03/14/writer-monads-via-continuations/}} }

@@ -11,7 +11,7 @@  \title{Lloyd Allison's Corecursive Queues:\\Why Continuations Matter} \author{Leon P Smith\email{leon@@melding-monads.com}}-\date{July 29, 2009} +\date{July 29, 2009}  \newcommand{\hiddencode}[1]{} \newcommand{\superscript}[1]{\ensuremath{^{\textrm{#1}}}}@@ -41,7 +41,7 @@ import Data.STRef.Strict  import Control.Monad(mapM_, liftM)        -- A few basic library functions-import Control.Arrow((***), (&&&), (>>>)) +import Control.Arrow((***), (&&&), (>>>)) import Data.List(zipWith3) import Data.Function(fix) import Data.Ratio@@ -80,7 +80,7 @@  In a purely functional setting,  real-time queues are traditionally thought to be much harder to implement than either real-time stacks or amortized $\mathcal O(1)$ queues.  In ``Circular Programs and Self-Referential Structures,''~\cite{allison89}  Lloyd Allison uses \emph{corecursion} and \emph{self-reference} 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 queue is general, in the sense it is straightforward to adapt  his technique to a new algorithm,  a problem has been the lack of a reusable library implementation.   This paper solves this problem by structuring the corecursion using a monadic interface and continuations. +While Allison's queue is general, in the sense it is straightforward to adapt  his technique to a new algorithm,  a problem has been the lack of a reusable library implementation.   This paper solves this problem by structuring the corecursion using a monadic interface and continuations.  Because Allison's queue is not fully persistent,  it cannot be a first class value.   Rather,  it is encoded inside 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.~\cite{gill99}  This paper argues that |mapCont| cannot be expressed in terms of |callCC|,  |return|,  and |(>>=)|. @@ -92,9 +92,9 @@  \begin{listing} \begin{code}-data  Tree a b -   =  Leaf    a   -   |  Branch  b (Tree a b) (Tree a b) +data  Tree a b+   =  Leaf    a+   |  Branch  b (Tree a b) (Tree a b)       deriving (Eq,Show)  labelDisj :: (a -> c) -> (b -> c) -> Tree a b -> c@@ -113,7 +113,7 @@ \begin{code} fib :: Int -> Tree Int Int fib n = fibs !! (n-1)-  where +  where     fibs = Leaf 0 : Leaf 0 : zipWith3 Branch [1..] fibs (tail fibs) \end{code} \centering@@ -126,7 +126,7 @@ \begin{code} sternBrocot :: Tree a (Ratio Integer) sternBrocot = loop 0 1 1 0-   where loop a b x y +   where loop a b x y           = Branch (m%n) (loop a b m n) (loop m n x y)             where  m  = a + x                    n  = b + y@@ -141,7 +141,7 @@  The second example defines  the Stern-Brocot tree, shown in Figure~\ref{sternbrocot}.   Despite that this definition does not employ self reference,  this is a corecursive definition because it is infinite and thus requires lazy evaluation. The Stern-Brocot tree is interesting because every positive rational number is generated in reduced form at exactly one branch.   Not only does this prove that the rationals are countable,  it can be computed more efficiently than the standard Cantor diagonalization. -These examples were chosen such that any two subtrees in this family are equal if and only if their labels are equal.  This is true even for the Fibonacci trees:  even though labels are repeated,  the subtrees are still equal.  This property can be exploited to efficiently and accurately test whether two breadth-first traversals might be equivalent. +These examples were chosen such that any two subtrees in this family are equal if and only if their labels are equal.  This is true even for the Fibonacci trees:  even though labels are repeated,  the subtrees are still equal.  This property can be exploited to efficiently and accurately test whether two breadth-first traversals might be equivalent.  Having separate types for the labels of branches and leaves enables one to better exploit Haskell's type system.   An example is the polymorphic leaf type for |sternBrocot|.  Along the lines of Philip Wadler's classic paper ``Theorems for Free'',~\cite{wadler89} this almost proves that the Stern-Brocot tree is both complete and infinite,  in the sense that every counterexample to this line of reasoning involves \emph{partial data}.  Common examples of partial data are \emph{infinite nonproductive loops} and the use of Haskell's |error| function,  such as this definition of |bot|: @@ -152,7 +152,7 @@  However,  not every corecursive definition produces a conceptually infinite data structure.  Lloyd Allison's queue is a good example:  it is self-referential, and thus depends on lazy evaluation.   Allison's queues can and often do produce a finite object. -A simple breadth-first traversal using Allison's queue is given along with a sample execution in Figure~\ref{levelOrder}.  The execution abuses notation slightly,  as necessary for readability:   the elements of the queue are trees, not labels.   However,  as the labels are unique for the examples given,  this does not lead to ambiguity.   +A simple breadth-first traversal using Allison's queue is given along with a sample execution in Figure~\ref{levelOrder}.  The execution abuses notation slightly,  as necessary for readability:   the elements of the queue are trees, not labels.   However,  as the labels are unique for the examples given,  this does not lead to ambiguity.  A corecursive queue is represented by a single lazy list.   The end of the queue is represented by a thunk, which can produce the next element on demand.  This thunk contains a pointer back to the first element in the queue and the number of elements currently in the queue.   When an element is enqueued,  call-by-need evaluation \emph{implicitly mutates} the end of the list. @@ -163,7 +163,7 @@ \begin{figure}[t] \begin{code} levelOrder ::  Tree a b  ->  [Tree a b]-levelOrder     tree      =   queue +levelOrder     tree      =   queue   where     queue = tree : explore 1 queue @@ -180,7 +180,7 @@  Pattern matching creates demand for computation,  thus pattern matching on the empty queue causes this thunk to reenter itself, creating an infinite nonproductive loop.   In effect,  in order to compute the answer, the answer must have already been computed.   Explicitly tracking length breaks this cycle.   By knowing via other means that the queue is empty,  we can avoid pattern matching and continue or terminate the queue as needed,  as illustrated in the last step of the sample execution. -Note that the type of the counter is explicitly given.  Otherwise,  Haskell would typically default to arbitrary precision integers.    This leads to a noticable, though modest, slowdown and increase in memory allocation in certain micro-benchmarks, such as a complete traversal of a Fibonacci trees.+Note that the type of the counter is explicitly given.  Otherwise,  Haskell would typically default to arbitrary precision integers.    On GHC, this leads to a noticable, though modest, slowdown and increase in memory allocation in certain micro-benchmarks, such as a complete traversal of a Fibonacci trees.  \begin{listing} \begin{code}@@ -191,11 +191,12 @@   where     queue  | isBranch tree   = tree :  explore 1 queue            | otherwise       =         explore 0 queue- -    explore :: Int -> [Tree a b] -> [Tree a b]  -    explore  0 _ = []-    explore  (n+1) (Branch _ l r : q') -      =  if (isBranch  l) ++    explore :: Int -> [Tree a b] -> [Tree a b]+    explore      0       _+      =  []+    explore   (  n+1) (  Branch _ l r : q')+      =  if (isBranch  l)          then   if (isBranch r)                 then   l :  r :  explore  (  n+2)  q'                 else   l :       explore  (  n+1)  q'@@ -215,36 +216,38 @@ levelOrder'2     tree      =      queue   where      queue = enqs [tree] 0 queue-  -     enqs  ::  [Tree a b] ->  Int ->  [ Tree a b ]  ->  [ Tree a b ]-     enqs      []             n              q      =        deq          n      q-     enqs      (t:ts)         n              q-               | isBranch t                         =   t :  enqs  ts  (  n+1)   q-               | otherwise                          =        enqs  ts     n      q- -     deq                      0              _      =        []-     deq                      (n+1)   ( t :  q'  )  =        enqs  ts'    n      q'-               where ts' = childrenOf t++     enqs  ::  [Tree a b] ->  Int ->     [ Tree a b ]  -> [ Tree a b ]+     deq   ::                 Int ->     [ Tree a b ]  -> [ Tree a b ]++     enqs      []                n       q             =        deq           n      q+     enqs      (t:ts)            n       q+           |  isBranch t                               =   t :  enqs  ts   (  n+1)   q+           |  otherwise                                =        enqs  ts      n      q++     deq                         0       _             =        []+     deq                      (  n+1)    ( t :  q'  )  =        enqs  ts'     n      q'+              where ts' = childrenOf t \end{code}-\caption{Removing the repeated branch}+\caption{Removing the repeated conditional branch} \label{levelOrder'2} \end{listing}  \hiddencode{ \begin{code}-prop_levelOrder'2 n tree = +prop_levelOrder'2 n tree =         take n ( map (labelDisj id id) (levelOrder'   tree) )     ==  take n ( map (labelDisj id id) (levelOrder'2  tree) ) \end{code} } -Because the code in Listing~\ref{levelOrder'2} makes use of |childrenOf|,  it easily generalizes to arbitrary trees.   This code is very similar to a breath-first graph searching algorithm I wrote in December 2000,  simplified to trees.   This is notable because it was the day after I first read Richard Bird's classic paper, which is also prominently cited by Allison.  +Because the code in Listing~\ref{levelOrder'2} makes use of |childrenOf|,  it easily generalizes to arbitrary trees.   This code is very similar to a breath-first graph searching algorithm I wrote in December 2000,  simplified to trees.   This is notable because it was the day after I first read Richard Bird's classic paper, which is also prominently cited by Allison.  \pagebreak  Although I didn't become aware of Lloyd Allison's work until six years later,  at the time I had guessed that somebody had come up with it before.  It is a testament to Bird's writing that he has inspired at least two people,  and probably more, to independently arrive at the same idea. -The code was rather difficult to write the first time,  but I immediately felt that I had a reasonable grasp of what was going on.   In fact, I remember part of the thought process behind my endeavor:   I was trying to implement a queue using naive list concatenation,  employing Richard Bird's technique to eliminate a quadratic number of passes.   +The code was rather difficult to write the first time,  but I immediately felt that I had a reasonable grasp of what was going on.   In fact, I remember part of the thought process behind my endeavor:   I was trying to implement a queue using naive list concatenation,  employing Richard Bird's technique to eliminate a quadratic number of passes.   \subsection{Reusable Corecursive Queues}@@ -264,48 +267,50 @@ \label{interfaces} \end{listing} -We have now written three corecursive queues.  A natural question to ask is how to implement a reusable library for this technique,  so that we don't have to start from scratch every time we would like to use it.   This subsection informally derives such an implementation. +We have now written three corecursive queues.  A natural question to ask is how to implement a reusable library for this technique,  so that we don't have to start from scratch every time we would like to use it.   This subsection informally derives such an implementation. -What kind of interface would this library have?   The traditional interface treats queues as first class values,  as given by |Queue| in Figure~\ref{interfaces}.  Because Haskell is pure,  all first class values are persistent.   This gives us the freedom to enqueue an element,   back up,  enqueue a different element,  and use both  results in subsequent computations,  as demonstrated by the |fork a b q = (enque a q, enque b q)|.   +What kind of interface would this library have?   The traditional interface treats queues as first class values,  as given by |Queue| in Figure~\ref{interfaces}.  Because Haskell is pure,  all first class values are persistent.   This gives us the freedom to enqueue an element,   back up,  enqueue a different element,  and use both  results in subsequent computations,  as demonstrated by the |fork a b q = (enque a q, enque b q)|.  Due to implicit mutation, Allison's queues cannot be used persistently.  This implies that they cannot be first class values in a pure language!   Thus looking for an implementation of |enque| and |deque| is futile, as  any interface must enforce linearity upon enqueue.   Monadic interfaces offer a well-known solution to this problem,  so it seems plausible that we could find an implementation of a monadic interface.  In the examples so far,  the logic that traverses the binary trees is entangled with the logic that defines the queue operations.   Our goal is to separate these concerns.  As the names suggest, |explore| in Listing~\ref{allison-code}  has no separation of concerns,   while |enqs| and |deqs| in Listing~\ref{levelOrder'2} isolate the basic operations into two mutually recursive functions. -If we had an implementation of |enQ|,  it would be easy to write a helper function that takes a single tree,  and enqueues it iff it is a |Branch|.  Perhaps if we had this helper,  it would be easier to factor out the queue operations.    We will work backwards from this guess,  and forwards from |levelOrder'2| to write this single-element filter.   --Currently,  |enqs| loops over candidates to possibly enqueue.   By inlining |childrenOf| and then unrolling |enqs|,  we get two helper functions,  |enq1| and |enq2|, that differ only in their \emph{continuation}.     By parameterizing the continuation, we can refactor these into a single function.   This process is demonstrated in Listing~\ref{helper}.+If we had an implementation of |enQ|,  it would be easy to write a helper function that takes a single tree,  and enqueues it iff it is a |Branch|.  Perhaps if we had this helper,  it would be easier to factor out the queue operations.    We will work backwards from this guess,  and forwards from |levelOrder'2| to write this single-element filter. -Continuations are \emph{required} because every queue operation must return the resulting queue from the rest of the computation.   Thus every enqueue or dequeue must be aware of what operation comes next.+Currently,  |enqs| loops over candidates to possibly enqueue.   By inlining |childrenOf| and then unrolling |enqs|,  we get two helper functions that differ only in their \emph{continuation}.     By parameterizing the continuation, we can refactor these into a single function.   Continuations are \emph{required} because every queue operation must return the resulting queue from the rest of the computation.   Thus every enqueue or dequeue must be aware of what operation comes next.  This process is demonstrated in Listings~\ref{unroll}~and~\ref{helper}. -The resulting definition of |levelOrder'4| is easily the best means of expression thus far:  unlike |levelOrder'| and |levelOrder'3| it does not repeat any logic,  and unlike |levelOrder'2|,  the queue operations are expressed much more directly,  and the logic is all but disentangled.    The last step should be easy,  all we have to do is pull the branch out of |enq| and define a separate helper function,  recovering the original |explore| and fully reusable queue operations,  as demonstrated in Listing~\ref{levelOrder'5}.  +The resulting definition of |levelOrder'4| is easily the best means of expression thus far:  unlike |levelOrder'| and |levelOrder'3| it does not repeat any logic,  and unlike |levelOrder'2|,  the queue operations are expressed much more directly.    All that is left to do is to parameterize the continuation of |deq|,  and to remove the conditional branch from |enq|.   Once this is completed, we are left with a fully disentangled traversal in Listing~\ref{levelOrder'5}. -\begin{listing}+\begin{listing}[p] \begin{code}-levelOrder'3 t = q-  where-    q = enq1 [t] (0::Int) q+levelOrder'3 tree = queue+  where  queue = enq1 [tree] (0::Int) queue -    enq2 [a,b]  n q  | isBranch a  = a :  (enq1 [b]  )  (  n+1)   q-                     | otherwise   =      (enq1 [b]  )     n      q+         enq2 [a,b]  n q  | isBranch a  = a :  (enq1 [b]  )  (  n+1)   q+                          | otherwise   =      (enq1 [b]  )     n      q -    enq1 [a]    n q  | isBranch a  = a :  (deq       )  (  n+1)   q-                     | otherwise   =      (deq       )     n      q+         enq1 [a]    n q  | isBranch a  = a :  (deq       )  (  n+1)   q+                          | otherwise   =      (deq       )     n      q -    deq  0                      _    = []   -    deq  (n+1) (Branch _ l r :  q')  = enq2 [l,r] n q'+         deq  0                  _    = []+         deq  n (Branch _ l r :  q')  = enq2 [l,r] (n-1) q'+\end{code}+\caption{Inlining |childrenOf| and unrolling |enqs|}+\label{unroll}+\end{listing} -levelOrder'4 t = q-  where-    q = (enq t $ deq) (0::Int) q+\begin{listing}[p]+\begin{code}+levelOrder'4 tree = queue+  where  queue = (enq tree $ deq) (0::Int) queue -    enq a k n q  | isBranch a  = a :  k  (  n+1  )  q-                 | otherwise   =      k     n       q+         enq a k n q  | isBranch a  = a :  k  (  n+1  )  q+                      | otherwise   =      k     n       q -    deq    0           _                    =  []-    deq (  n+1  )   (  Branch _ l r : q  )  =  (enq l $ enq r $ deq ) n q+         deq 0                     _    = []+         deq n  (  Branch _ l r :  q )  = (enq l $ enq r $ deq) (n-1) q \end{code}-\caption{Creating a reusable helper}+\caption{Parameterizing the continuations of |enq1| and |enq2|} \label{helper} \end{listing} @@ -313,11 +318,11 @@ \hiddencode{ \begin{code} prop_levelOrder'3 n tree =-        take n ( map (labelDisj id id) (levelOrder'   tree) ) +        take n ( map (labelDisj id id) (levelOrder'   tree) )     ==  take n ( map (labelDisj id id) (levelOrder'3  tree) )  prop_levelOrder'4 n tree =-        take n ( map (labelDisj id id) (levelOrder'   tree) ) +        take n ( map (labelDisj id id) (levelOrder'   tree) )     ==  take n ( map (labelDisj id id) (levelOrder'4  tree) )  prop_levelOrder'5 tree n =@@ -327,56 +332,53 @@ }  -\begin{listing}+\begin{listing}[p] \begin{code}-levelOrder'5 t = q-  where-    q = (handle t (\() -> explore)) (0::Int) q +levelOrder'5 tree = queue+  where  queue = (handle tree $ (\() -> explore)) (0::Int) queue -    handle t  | isBranch t   = enq t-              | otherwise    = ret ()-    -    explore =  deq        (\(Branch _ l r) -> -               handle l   (\() -> -               handle r   (\() -> -               explore    )))-                          -    enq  e  k        n            q     =  e :  k  ()  (  n+1)  q+         handle t  | isBranch t  = enq t+                   | otherwise   = ret () -    ret  a  k        n            q     =       k  a      n     q -        -    deq     k        0            q     =       []-    deq     k   (n+  1  )  ( e :  q' )  =       k  e      n     q'     +         explore =  deq        $  (\(Branch _ l r) ->+                    handle l   $  (\() ->+                    handle r   $  (\() ->+                    explore       )))++         enq  e     k  n        q     =  e :  k  ()  (  n+1)  q++         ret  a     k  n        q     =       k  a      n     q++         deq        k  0        q     =       []+         deq        k  n ( e :  q' )  =       k  e   (  n-1)  q' \end{code} \caption{A fully disentangled traversal in explicit CPS} \label{levelOrder'5} \end{listing} -In a sense,  we have re-invented the traditional continuation passing style~\cite{eopl} (CPS) with a slight twist,  namely,  that the tail of a list is considered to be a tail call.   This is not a problem relative to the current understanding of the CPS transform,  where any part of the program that is guaranteed to terminate,  such as lazy cons~\cite{friedman87},   may optionally be left untouched by the transform. +In a sense,  we have re-invented the traditional continuation passing style~\cite{eopl} (CPS) with a slight twist,  namely,  that the tail of a list is considered to be a tail call.   This is not a problem relative to the current understanding of the CPS transform,  where any part of the program that is guaranteed to terminate,  such as lazy cons~\cite{friedman87},   may optionally be left untouched by the transform. -Now,  the only difference between |deq| and the monadic |deQ| is that the |deq| breaks out of it's loop and leaves the computation,  whereas |deQ| returns |Nothing| in this case.    Although the breaking out of the computation is superficially pleasing in this particular case,  there are good reasons to prefer the latter in most cases.   So we are ready to split Listing~\ref{levelOrder'5} into two parts:  reusable corecursive queue operations versus the breadth-first tree traversal in Listings~\ref{CorecQ} and~\ref{levelOrder''} respectively. +Now,  the only difference between |deq| and the monadic |deQ| is that the |deq| breaks out of it's loop and leaves the computation,  whereas |deQ| returns |Nothing| in this case.    Although the breaking out of the computation is superficially pleasing in this particular case,  there are good reasons to prefer the latter in most cases.   So we are ready to split Listing~\ref{levelOrder'5} into two parts:  reusable corecursive queue operations versus the breadth-first tree traversal in Listings~\ref{CorecQ} and~\ref{levelOrder''} respectively.  \begin{listing} \begin{code}-type CorecQSt e = Int -> [e] -> [e]+newtype  CorecQ e a+      =  CorecQ (Cont (Int -> [e] -> [e]) a) deriving (Monad) -newtype CorecQ e a  -     =  CorecQ { unCorecQ :: (a -> CorecQSt e) -> CorecQSt e }+mkCorecQ  x = (CorecQ (Cont x))+unCorecQ  (CorecQ (Cont x)) =  x -instance Monad (CorecQ e) where-  return a  = CorecQ (\k -> k a)-  m >>= f   = CorecQ (\k -> unCorecQ m (\a -> unCorecQ (f a) k))+runCorecQ :: CorecQ element result -> [element]+runCorecQ m =  queue+        where  queue = unCorecQ m (\a n' q' -> []) 0 queue  instance MonadQueue e (CorecQ e) where-  enQ e  = CorecQ (\k n q -> e : (k () $! n+1) q)-  deQ    = CorecQ deq-    where-      deq k      0       q    = k Nothing   0 q-      deq k (n+  1) (e:  q')  = k (Just e)  n q'+  enQ e  =  mkCorecQ  enq+            where     enq k n      q    =  e :  k ()        (  n+1)  q+  deQ    =  mkCorecQ  deq+            where     deq k 0      q    =       k Nothing      0     q+                      deq k n (e:  q')  =       k (Just e)  (  n-1)  q' -runCorecQ :: CorecQ element result -> [element]-runCorecQ m =  q-        where  q = unCorecQ m (\a n' q' -> []) 0 q \end{code} \caption{A reusable implementation of Allison's queue} \label{CorecQ}@@ -385,22 +387,19 @@ \begin{listing} \begin{code} levelOrder'' :: MonadQueue (Tree a b) q => Tree a b -> q ()-levelOrder'' t = handle t >> explore-   where +levelOrder'' t = handle t >>= (\() -> explore)+   where      handle t  | isBranch t  = enQ t                | otherwise   = return ()-     explore = deQ >>=  maybe (return ()) -                        (\(Branch _ l r)  -> -                             do-                               handle l-                               handle r-                               explore    )+     explore =  deQ       >>=  maybe (return ()) (\(Branch _ l r)  ->+                handle l  >>=  (\() ->+                handle r  >>=  (\() ->+                explore        ))) \end{code}-\caption{A binary tree traversal using generic queues}-\label{levelOrder''} +\caption{Traversing a binary tree using generic queues}+\label{levelOrder''} \end{listing} - I first wrote something like |CorecQ| in August 2005,  although it took me several years to understand my own code.  Of course, this raises the question of how one can write code that one doesn't understand.  The answer is simple: type theory.   Following the reasoning at the beginning of this subsection,   I had been growing rather suspicious that corecursive queues could be abstracted via a monadic interface.  After reading Wouter Swierstra's ``Why Attribute Grammars Matter''~\cite{swierstra05} and coming to opinion that the examples contained therein are kind of lame,   I was motivated to produce better, more compelling examples.  Corecursive queues naturally came to mind.@@ -411,7 +410,7 @@  \subsection {Observing Monadic Computations} -Monadic computations must somehow be \emph{observed},  otherwise they are useless.  Note the type of |runCorecQ :: CorecQ e a -> [e]|.  The only observable aspect of the |CorecQ| monad is the list of enqueued elements.  In particular, the final return value |a| cannot be observed. +Monadic computations must somehow be \emph{observed},  otherwise they are useless.  Note the type of |runCorecQ :: CorecQ e a -> [e]|.  The only observable aspect of the |CorecQ| monad is the list of enqueued elements.  In particular, the final return value |a| cannot be observed.  Listing~\ref{byLevel} gives two generic combinators for level-order traversals.  They parameterize |childrenOf|, allowing arbitrary trees to be traversed.  In fact,  one need not even explicitly construct a tree: the Fibonacci trees could be traversed using this definition of |fibChildren|, for example. \begin{code}@@ -425,22 +424,23 @@  \begin{listing} \begin{code}-byLevel :: (MonadQueue a m) => (a -> [a]) -> [a] -> m ()+byLevel,  byLevel' :: (MonadQueue a m) => (a -> [a]) -> [a] -> m ()+ byLevel childrenOf as = mapM_ enQ as >> explore   where-    explore = deQ >>=  maybe (return ()) -                       (\a ->  do +    explore = deQ >>=  maybe (return ())+                       (\a ->  do                                mapM_ enQ (childrenOf a  )                                explore                  )  -byLevel' :: (MonadQueue a m) => (a -> [a]) -> [a] -> m ()+ byLevel' childrenOf as = mapM_ handle as >> explore   where     handle a = when (hasChildren a) (enQ a) -    explore = deQ >>=  maybe (return ()) -                       (\a ->  do +    explore = deQ >>=  maybe (return ())+                       (\a ->  do                                mapM_ handle (childrenOf a  )                                explore                     ) @@ -450,7 +450,7 @@ \label{byLevel} \end{listing} -There are two points worth noting about the definition of |byLevel| and |byLevel'|:  the top level definitions are not recursive,  and the recursive |explore| does not pass |childrenOf| to itself repeatedly.  This combination plays nice with the Glasgow Haskell Compiler as current implemented:  inlining |byLevel| opens up the possibility of inlining |childrenOf| as well, or at least eliminating an indirect jump.  +There are two points worth noting about the definition of |byLevel| and |byLevel'|:  the top level definitions are not recursive,  and the recursive |explore| does not pass |childrenOf| to itself repeatedly.  This combination plays nice with the Glasgow Haskell Compiler as current implemented:  inlining |byLevel| opens up the possibility of inlining |childrenOf| as well, or at least eliminating an indirect jump.  While this idiom can be worthwhile; it is far more important performance-wise that |enQ| and |deQ| be inlined.   Because we are using typeclasses to abstract over the queue operations,  inlining these operations is a clumsy thing to do in GHC.   Indeed,  ML-style functors are a superior choice for this type of abstraction. @@ -458,12 +458,12 @@ \begin{spec} approx n = map (labelDisj id id) . take n -prop_runCorecQ_runDebugQ_eq :: Eq a => Int -> (forall m ; (MonadQueue (Tree a a) m) => m ()) -> Bool  -prop_runCorecQ_runDebugQ_eq n m +prop_runCorecQ_runDebugQ_eq :: Eq a => Int -> (forall m ; (MonadQueue (Tree a a) m) => m ()) -> Bool+prop_runCorecQ_runDebugQ_eq n m     =   approx n (runCorecQ m)     ==  approx n (runQueue m) -prop_runCorecQ_levelOrder_eq n tree +prop_runCorecQ_levelOrder_eq n tree     =   approx n (levelOrder'2 tree)     ==  approx n (runCorecQ (byLevel' childrenOf [tree])) \end{spec}@@ -478,7 +478,7 @@ type   ListPtr  st a = STRef st (List st a)  type     STQSt st r e = ListPtr st e -> ListPtr st e -> ST st r-newtype  STQ e a +newtype  STQ e a      =  STQ { unSTQ :: forall r st . ((a -> STQSt st r e) -> STQSt st r e) }  instance Monad (STQ e) where@@ -497,7 +497,7 @@                          Null         -> k Nothing   a   z                          (Cons e a')  -> k (Just e)  a'  z -runSTQ :: STQ element result -> result +runSTQ :: STQ element result -> result runSTQ m = runST $ do   ref <- newSTRef Null   unSTQ m (\r _a _z -> return r) ref ref@@ -518,7 +518,7 @@  \begin{listing} \begin{code}-foldrByLevel  :: (MonadQueue a m) +foldrByLevel  :: (MonadQueue a m)               => (a -> [a]) -> (a -> b -> b) -> b -> [a] -> m b foldrByLevel  childrenOf f b as = mapM_ enQ as >> explore    where@@ -538,17 +538,17 @@  \begin{listing} \begin{code}-foldrByLevel'  :: (MonadQueue a m) -               => (a -> [a]) -> (a -> b -> b) -> b -> [a] -> m b +foldrByLevel'  :: (MonadQueue a m)+               => (a -> [a]) -> (a -> b -> b) -> b -> [a] -> m b foldrByLevel'  childrenOf f b as = handleMany as    where      handleMany []      = explore      handleMany (a:as)  = do-         when (hasChildren a) (enQ a) -         b <- handleMany as +         when (hasChildren a) (enQ a)+         b <- handleMany as          return (f a b) -     explore = deQ >>= maybe (return b) (handleMany . childrenOf) +     explore = deQ >>= maybe (return b) (handleMany . childrenOf)       hasChildren = not . null . childrenOf \end{code}@@ -573,18 +573,18 @@ \label{use-cases} \end{listing} -There is no need for |foldrByLevel| to enqueue leaf nodes.   Instead of folding elements after they are dequeued,  we could instead fold elements before they are enqueued.   Listing~\ref{foldrByLevel'} computes the same fold, even though it enqueues branches only.  +There is no need for |foldrByLevel| to enqueue leaf nodes.   Instead of folding elements after they are dequeued,  we could instead fold elements before they are enqueued.   Listing~\ref{foldrByLevel'} computes the same fold, even though it enqueues branches only. -An orthogonal change allows |foldrByLevel'| to be more lazy.  If the initial forest of trees is infinite,  |foldrByLevel| will get stuck in a nonproductive loop.   This is because Listing~\ref{foldrByLevel} enqueues the entire forest before doing any folding.   The enhanced version interleaves folding with enqueue operations.   Thus |foldrByLevel'| is a true generalization of |foldr|,  whereas the original is not.  +An orthogonal change allows |foldrByLevel'| to be more lazy.  If the initial forest of trees is infinite,  |foldrByLevel| will get stuck in a nonproductive loop.   This is because Listing~\ref{foldrByLevel} enqueues the entire forest before doing any folding.   The enhanced version interleaves folding with enqueue operations.   Thus |foldrByLevel'| is a true generalization of |foldr|,  whereas the original is not.  Of course, this property depends on the semantics of the monad:  the final result must be observed in a sufficiently lazy fashion.  This is not true of |runSTQ| even if the lazier variant of |ST| is used, and so |foldrByLevel| is semantically equivalent to |foldrByLevel'| relative to this monad.   This equivalency will be relaxed relative to |StateQ| in the next section.  \hiddencode{ \begin{spec}-prop_foldr_ByLevel childrenOf f b as = +prop_foldr_ByLevel childrenOf f b as =        foldr f   b (runCorecQ (byLevel   childrenOf as))-   ==  foldr f'  b (runCorecQ (byLevel'  childrenOf as)) -   where     +   ==  foldr f'  b (runCorecQ (byLevel'  childrenOf as))+   where        f' a b = foldr f b (childrenOf a) \end{spec} }@@ -593,7 +593,7 @@  \section{Monad Transformers} -This section briefly reviews the traditional two-stack queue,  and explores how they can be encapsulated inside a variety of different monads.   The first wraps the two-stack queue in a state monad,  thus guaranteeing amortized $\mathcal O(1)$ performance.  The second implementation employs a state transformer and a writer monad to observe both the elements enqueued and the final result.   The last introduces the continuation passing state monad,  which makes explicit an idiom already used in |CorecQ| and |STQ| of the previous sections. +This section briefly reviews the traditional two-stack queue,  and explores how they can be encapsulated inside a variety of different monads.   The first wraps the two-stack queue in a state monad,  thus guaranteeing amortized $\mathcal O(1)$ performance.  The second implementation employs a state transformer and a writer monad to observe both the elements enqueued and the final result.   The last introduces the continuation passing state monad,  which makes explicit an idiom already used in |CorecQ| and |STQ| of the previous sections.  We explore the guarantees that various types of monads provide,  and demonstrate how most of these guarantees are lost when the monad transformers are used.  We argue that monad transformers are not robust abstractions,  culminating in the rather fragile corecursive queue transformer of the next section. @@ -608,14 +608,14 @@ \begin{code} data TwoStackQ e = TwoStackQ [e] [e] -instance Queue TwoStackQ where +instance Queue TwoStackQ where    empty = TwoStackQ [] []     enque z  (TwoStackQ []     [])  =   TwoStackQ [z]     []    enque z  (TwoStackQ (a:as) zs)  =   TwoStackQ (a:as)  (z:zs)     deque    (TwoStackQ []     [])  =   ( Nothing  ,  TwoStackQ []   []  )-   deque    (TwoStackQ (a:as) zs)  +   deque    (TwoStackQ (a:as) zs)             |  null as             =   ( Just a   ,  TwoStackQ as'  []  )             |  otherwise           =   ( Just a   ,  TwoStackQ as   zs  )                where as' = reverse zs@@ -623,7 +623,7 @@ \caption{Two-Stack Queues} \end{listing} -Of course,  because two-stack queues are first-class values in Haskell,  they are automatically persistent.   Unlike an imperative language,  operations on the queue preserve older versions of the queue.   While |deque| is still $\mathcal O(n)$ in the worst case,  it works very well in practice because on average,  |deque| is actually $\mathcal O(1)$,  provided that the queue is not used persistently.   Under this assumption,  every element is moved at most once from the back to the front. +Of course,  because two-stack queues are first-class values in Haskell,  they are automatically persistent.   Unlike an imperative language,  operations on the queue preserve older versions of the queue.   While |deque| is still $\mathcal O(n)$ in the worst case,  it works very well in practice because on average,  |deque| is actually $\mathcal O(1)$,  provided that the queue is not used persistently.   Under this assumption,  every element is moved at most once from the back to the front.  There are implementations that guarantee $\mathcal O(1)$ worst-case operations,  even with persistent usage, such as Chris Okasaki's incremental reversals of lazy lists.~\cite{okasaki95}  However this solution has a relatively high constant factor,  in practice is often slower than other options,  sometimes significantly so. @@ -644,24 +644,26 @@ \caption{First-class Queues inside |Control.Monad.State.Lazy|} \end{listing} -Monadic interfaces can enforce linear, non-persistent usage of data structures, but do not necessarily do so.   The |StateQ| monad guarantees linearity by wrapping the queue in a |State| monad and hiding |get| and |put| operations,  ensuring amortized $\mathcal O(1)$ operations.  However,  the state transformer monad,  |StateT|,  cannot make this guarantee!  The ability to use state persistently can be recovered by choosing the nondeterministic list monad and lifting |MonadPlus| operations, for example.  +Monadic interfaces can enforce linear, non-persistent usage of data structures, but do not necessarily do so.   The |StateQ| monad guarantees linearity by wrapping the queue in a |State| monad and hiding |get| and |put| operations,  ensuring amortized $\mathcal O(1)$ operations.  However,  the state transformer monad,  |StateT|,  cannot make this guarantee!  The ability to use state persistently can be recovered by choosing the nondeterministic list monad and lifting |MonadPlus| operations, for example.  \subsection{The Writer Monad} +\emph{Editorial Note} This section is deeply flawed.  In particular, the standard implementation of the Writer monad does not ensure the efficient use of list concatination.  A continuation-based implementation of the Writer monad, on the other hand,  does.  This confusion probably arose because the corecursive queue monad essentially uses a continuation-based writer monad to add elements to the queue.  For example,  compare the use of |mapCont| in the implementation of |enQ| for |CorecQ'| in Listing~\ref{CorecQ'} and the |MonadWriter| instance for |Cont| in~\cite{smith2010}. \emph{End Note}+ So far, we have only been able to observe either the enqueued elements or the final result, but not both.   We can employ the state transformer in conjunction with the Writer monad to observe both aspects of the computation.   The amortized $\mathcal O(1)$ guarantee is unaffected by the use of |Writer|.  \begin{listing}[!b] \begin{code}-newtype WriterQ e a -     =  WriterQ (StateT (TwoStackQ e) (Writer [e])  a)  +newtype WriterQ e a+     =  WriterQ (StateT (TwoStackQ e) (Writer [e])  a)         deriving (Monad) -instance MonadQueue e (WriterQ e) where +instance MonadQueue e (WriterQ e) where     enQ e  = WriterQ (tell [e] >> modify (enque e))     deQ    = WriterQ (StateT (return . deque))  runWriterQ :: WriterQ element result -> (result, [element])-runWriterQ (WriterQ m) +runWriterQ (WriterQ m)     =  let  ((result, final_queue), queue) = runWriter (runStateT m empty)        in   (result, queue) \end{code}@@ -670,7 +672,7 @@ \end{listing}  -Writer monads partially enforce the efficient use of list concatenation.   In the MTL, |Writer [e] a| is just a newtype isomorphism for |([e],a)|.   It provides a function |tell| that takes a list and concatenates the remainder of the computation onto the end of the list.   This naturally associates to the right,  and thus avoids quadratic behavior.   Of course, |tell| accepts arbitrary length lists,  and one could inefficiently produce a long argument to |tell|.  +Writer monads partially enforce the efficient use of list concatenation.   In the MTL, |Writer [e] a| is just a newtype isomorphism for |([e],a)|.   It provides a function |tell| that takes a list and concatenates the remainder of the computation onto the end of the list.   This naturally associates to the right,  and thus avoids quadratic behavior.   Of course, |tell| accepts arbitrary length lists,  and one could inefficiently produce a long argument to |tell|.  Note the duplication of functionality present in |WriterQ|.   Essentially,  the Writer monad re-creates the queue in a parallel data structure.   This observation was another motivation behind the creation of my first corecursive queue, analogous to Listing~\ref{levelOrder'2}.   I started writing a graph traversal using first-class queues,  producing a list of nodes as they were visited.   Although I was not using monads, I noticed the duplication and saw an opportunity to eliminate it using circular programming. @@ -679,7 +681,7 @@  \begin{listing} \begin{code}-newtype CpSt st a +newtype CpSt st a       = CpSt { unCpSt :: forall res . (a -> st -> res) -> st -> res }  instance Monad (CpSt st) where@@ -699,8 +701,8 @@  \begin{listing} \begin{code}-newtype CpStQ r e a -     =  CpStQ { unCpStQ :: StateT (TwoStackQ e) (Cont r) a } +newtype CpStQ r e a+     =  CpStQ { unCpStQ :: StateT (TwoStackQ e) (Cont r) a }         deriving (Monad)  instance MonadQueue e (CpStQ r e) where@@ -710,30 +712,30 @@ runCpStQ :: CpStQ r e r -> r runCpStQ (CpStQ m) = runCont (runStateT m empty) (\(r,q) -> r) \end{code}-\caption{Queues via another contination passing state monad}+\caption{Queues via another continuation passing state monad} \label{CpStQ}-\end{listing} +\end{listing}  \begin{listing} \begin{code} class MonadMapCC a m | m -> a where     mapCC :: (a -> a) -> m b -> m b -instance MonadMapCC r (CpStQ r e) where  +instance MonadMapCC r (CpStQ r e) where     mapCC f = CpStQ . mapStateT (mapCont f) . unCpStQ   foldrByLevel''  :: ( MonadQueue  a m                    , MonadMapCC  b m )-                => (a -> [a]) -> (a -> b -> b) -> b -> [a] -> m b +                => (a -> [a]) -> (a -> b -> b) -> b -> [a] -> m b foldrByLevel''  childrenOf f b as = handleMany as    where      handleMany []      = explore      handleMany (a:as)  = do-         when (hasChildren a) (enQ a) +         when (hasChildren a) (enQ a)          mapCC (f a) (handleMany as) -     explore = deQ >>= maybe (return b) (handleMany . childrenOf) +     explore = deQ >>= maybe (return b) (handleMany . childrenOf)       hasChildren = not . null . childrenOf \end{code}@@ -741,7 +743,7 @@ \label{foldrByLevel_} \end{listing} -Less well known than the regular state monad is the continuation passing state monad, as shown in Listing~\ref{CpSt}.  This paper has already used this idiom twice.   It has been used to track the length and head of the queue inside |CorecQ|,  and to track the references to the start and end of the mutable list inside |STQ|. +Less well known than the regular state monad is the continuation passing state monad, as shown in Listing~\ref{CpSt}.  This paper has already used this idiom twice.   It has been used to track the length and head of the queue inside |CorecQ|,  and to track the references to the start and end of the mutable list inside |STQ|.  The lazy state monad is notoriously inefficient on current implementations of Haskell;  one is much better off using the strict state monad.  The continuation-passing state monad is even faster.  Compared to the lazy state monad, the biggest advantage is that we aren't returning many pairs of lazy tuples, at the cost of sacrificing some laziness. @@ -751,7 +753,7 @@  Listing~\ref{CpStQ} gives an implementation of the queue interface in terms of |StateT| and |Cont|.  However, |StateT| is \emph{lazy} but |CpStQ| is \emph{strict}!  Not only have we added a continuation semantics to |StateT|,  we have also changed part of the existing semantics.  This is in contrast to the use of |Writer| in |WriterQ|,  which left the state semantics undisturbed.  Not only are monad transformers not robust abstractions,  they are not robust in any sense of the word! -More precisely,  |StateQ| returns its result incrementally while |CpStQ| doesn't return anything until the entire computation terminates.   This is easily observed on the Stern-Brocot tree:  |runStateQ (getBranches foldrByLevel [sternBrocot])|  returns useful data,  while |runCpStQ (getBranches foldrByLevel [sternBrocot])| gets stuck in an infinite nonproductive loop.   +More precisely,  |StateQ| returns its result incrementally while |CpStQ| doesn't return anything until the entire computation terminates.   This is easily observed on the Stern-Brocot tree:  |runStateQ (getBranches foldrByLevel [sternBrocot])|  returns useful data,  while |runCpStQ (getBranches foldrByLevel [sternBrocot])| gets stuck in an infinite nonproductive loop.  Fortunately, incremental results can be recovered through the use of |mapCont|,  as illustrated in Listing~\ref{CpStQ}.   By tweaking |foldrByLevel| to use this control operator,  we can traverse the Stern-Brocot tree.   This would not be possible had we used the strict state monad,  or  hidden the final result type. @@ -796,7 +798,7 @@  \begin{listing}[p] \begin{code}-newtype CorecQ' e a +newtype CorecQ' e a      =  CorecQ' { unCorecQ' :: ContT [e] (Reader (Len [e])) a }         deriving (Monad) @@ -805,23 +807,24 @@     deQ    = CorecQ' (stepReader deQ_len)  runCorecQ' :: CorecQ' e a -> [e]-runCorecQ' (CorecQ' m) = q +runCorecQ' (CorecQ' m) = q    where  q = runReader (runContT m endpoint) (Len 0 q)           endpoint _ = return [] \end{code} \caption{Enqueue and dequeue in direct style}+\label{CorecQ'} \end{listing}  \hiddencode{ \begin{spec} prop_runCorecQ_runCorecQ'_eq :: Eq a => Int -> (forall m . (MonadQueue (Tree a a) m) => m ()) -> Bool-prop_runCorecQ_runCorecQ'_eq n m +prop_runCorecQ_runCorecQ'_eq n m    =   approx n (runCorecQ   m)    ==  approx n (runCorecQ'  m) \end{spec} }  -There are two styles for programming with continuations.  The first is by explicitly by writing functions in the continuation passing style.  (CPS)  In this style,  all calls to non-primitive functions are tail calls, and functions have an extra continuation parameter,  which this paper has called |k|.   By contrast,  the direct style does not manipulate continuations explicitly,  but rather uses them implicitly or via control operators such as |callCC|, or |shift| and |reset|.  +There are two styles for programming with continuations.  The first is by explicitly by writing functions in the continuation passing style.  (CPS)  In this style,  all calls to non-primitive functions are tail calls, and functions have an extra continuation parameter,  which this paper has called |k|.   By contrast,  the direct style does not manipulate continuations explicitly,  but rather uses them implicitly or via control operators such as |callCC|, or |shift| and |reset|.  This paper uses an extended CPS that allows the tail of a lazy cons to be considered a ``tail call'',  even though it is not a proper tail call.  In fact, the first four |levelOrder| variants are already written in this extended CPS,  albeit in a static form that does not parameterize the continuations.    They move towards a more direct style,  with only |enQ| and |deQ| written in an explicit,  parameterized CPS. @@ -839,13 +842,13 @@  \subsection{Independence of |mapCont|} -The use of |mapCont| is notable because I am confident that |enQ| cannot be expressed in terms of |callCC|,  |(>>=)|,  and |return|.   The MTL's continuations are partially delimited,  as seems necessary for the general utility of |mapCont|.  However,  the analogous conjecture in terms of |shift| and |reset| is certainly not true.  +The use of |mapCont| is notable because I am confident that |enQ| cannot be expressed in terms of |callCC|,  |(>>=)|,  and |return|.   The MTL's continuations are partially delimited,  as seems necessary for the general utility of |mapCont|.  However,  the analogous conjecture in terms of |shift| and |reset| is certainly not true.  It may not be obvious why |mapCont| is independent of the rest,  but it turns out to be fairly trivial:   |callCC|, |(>>=)|, and |return| simply offer no way to add to the control context by introducing something that is not a proper tail call.   More formally,  we can modify the type of |CpSt|,  which uses higher-ranked types to hide the result type,  into a form that admits |callCC|,  but prohibits a useful form of |mapCont|.  \begin{listing} \begin{code}-newtype CpSt' s a +newtype CpSt' s a       = CpSt' { runCpSt' :: forall r . (forall r'.  a -> s -> r') -> s -> r }  instance Monad (CpSt' s) where@@ -856,13 +859,13 @@   callCC f = CpSt' (\k -> runCpSt' (f (\a -> CpSt' (\_ -> k a))) k)  mapCpSt' :: (forall a . a -> a) -> CpSt' s b -> CpSt' s b-mapCpSt' f m  = CpSt' (\k -> f (runCpSt' m k))   +mapCpSt' f m  = CpSt' (\k -> f (runCpSt' m k)) \end{code} \caption{A ``proof'' of the independence of |mapCont|} \label{independence} \end{listing} -Note that the code in Listing~\ref{independence} is purely theoretical, not useful,  because computations inside of |CpSt'| cannot be observed without cheating.  The definitions are the same as the corresponding definitions of |Cont|.  Since the use of typeclasses are not essential, these definitions have meaning independent of their types.   +Note that the code in Listing~\ref{independence} is purely theoretical, not useful,  because computations inside of |CpSt'| cannot be observed without cheating.  The definitions are the same as the corresponding definitions of |Cont|.  Since the use of typeclasses are not essential, these definitions have meaning independent of their types.  The types of |callCC|, |return|, and |(>>=)| are unchanged,  however the definition of |mapCont| gives a type error without providing an explicit higher-ranked type. Thanks to free theorems,  there are only three inhabitants of type |forall a . a->a|:  |id|, |const bot| and |bot|,  none of which are useful.   This argument may not be complete,  but I believe it can be the basis for a formal proof of independence. @@ -870,11 +873,11 @@  Now that |CorecQ| is in the direct style,  it is somewhat easier to come up with a plausible monad transformer.   Unfortunately,  |runCorecQT| is mostly broken.   For example,  as noted previously,  the corecursive queue implementation makes use of implicit mutation,  and thus depends on enforced linearity.   The non-deterministic list monad enables us to regain non-linear, persistent use.   Not surprisingly, the list monad is incompatible with this transformer. -Those interested should experiment with which monads work and which don't.   Of particular interest is the |IO| monad.   Getting a simple variant of Unix's |tail| command to work properly around this transformer is an interesting exercise that presents some difficulty. +Those interested should experiment with which monads work and which don't.   Of particular interest is the |IO| monad.   Getting a simple variant of Unix's |tail| command to work properly around this transformer is an interesting exercise that presents some difficulty.  \begin{listing} \begin{code}-newtype CorecQT e m a +newtype CorecQT e m a       = CorecQT ( ContT (m [e]) (Reader (Len [e])) a )         deriving (Monad) @@ -891,15 +894,15 @@ \caption{A rather fragile queue transformer} \end{listing} -The |mfix :: a -> m a| used here is the topic of Levent Erk\"{o}k's Ph.D. thesis,  ``Value Recursion in Monadic Computations''.~\cite{erkok02}  The thesis argues that there is no |mfix| on continuations.    Note that this transformer does not contradict this conjecture,  as we are using  |mfix| to define the run operation,  not defining an |mfix| for |CorecQT|.  +The |mfix :: a -> m a| used here is the topic of Levent Erk\"{o}k's Ph.D. thesis,  ``Value Recursion in Monadic Computations''.~\cite{erkok02}  The thesis argues that there is no |mfix| on continuations.    Note that this transformer does not contradict this conjecture,  as we are using  |mfix| to define the run operation,  not defining an |mfix| for |CorecQT|.  Value recursion is also a primary topic of this paper,  however, our application requires the use of continuations.   Thus it would appear that we are discussing an alternate form of value recursion,  and that CPS enables some varieties of value recursion while disabling others. -The |StateQ| monad is implemented via |State|,  which has an |mfix| operator.  Intuitively,  it would seem as though this |mfix| semantics makes sense for any |MonadQueue| implementation.  Whether or not a corecursive implementation can actually compute this semantics for |mfix| is a very interesting question.  Perhaps |CorecQ| would be a good avenue for research regarding Remark 5.2.1 on page 61 of Erk\"{o}k's thesis, speculating on the existence of special cases when continuations happen to have an |mfix|.  +The |StateQ| monad is implemented via |State|,  which has an |mfix| operator.  Intuitively,  it would seem as though this |mfix| semantics makes sense for any |MonadQueue| implementation.  Whether or not a corecursive implementation can actually compute this semantics for |mfix| is a very interesting question.  Perhaps |CorecQ| would be a good avenue for research regarding Remark 5.2.1 on page 61 of Erk\"{o}k's thesis, speculating on the existence of special cases when continuations happen to have an |mfix|.  Matt Morrow has observed that by hiding the result type of a continuation via higher-ranked types,  a |mfix| operator can in fact be implemented.   Of course, this technique also prohibits implementations of |callCC| and |mapCont|.  An |mfix| for |CpSt| is given in Listing~\ref{fixpoints}.   This does not directly contradict Erk\"{o}k's conjecture,  because the type of |CpSt| differs from |Cont|.  Currently,  this observation is a bit of a mystery, so this paper will not attempt to expound further. -Also included in Listing~\ref{fixpoints} is the alternate fixpoint operator |mfixish| that is at the heart of this paper.  It does not have the same type as |mfix|; so neither does it contradict Erk\"{o}k's conjecture.  +Also included in Listing~\ref{fixpoints} is the alternate fixpoint operator |mfixish| that is at the heart of this paper.  It does not have the same type as |mfix|; so neither does it contradict Erk\"{o}k's conjecture.  \begin{listing} \begin{code}@@ -918,17 +921,17 @@  One might assume, as this paper tacitly does, that there is no |mfix| over a monad implemented using continuations with an exposed return type.  This would imply that |CorecQ| cannot be used in conjunction with |CorecQT|,  ruling out an way that one might intuitively try to implement multiple queues. -\section {Returning Results from Corecursive Queues} +\section {Returning Results from Corecursive Queues} -Thankfully,  |Control.Monad.Writer| is compatible with the queue transformer of the last section.   This enables us to observe results other than the queue itself.  The benefit is that we can now usefully execute |foldrByLevel| and its variants using corecursive queues.  +Thankfully,  |Control.Monad.Writer| is compatible with the queue transformer of the last section.   This enables us to observe results other than the queue itself.  The benefit is that we can now usefully execute |foldrByLevel| and its variants using corecursive queues. -Unfortunately, because the writer monad expects monoids,  this approach isn't really suitable for preserving the result semantics of |STQ| and other implementations given in this paper.  The type |Writer e a| is just a newtype alias for |(a,e)|,  so instead of using our monad transformer directly,   we will simply use lazy pairs and start over.  +Unfortunately, because the writer monad expects monoids,  this approach isn't really suitable for preserving the result semantics of |STQ| and other implementations given in this paper.  The type |Writer e a| is just a newtype alias for |(a,e)|,  so instead of using our monad transformer directly,   we will simply use lazy pairs and start over.  Because |CorecQW| can return results other than the queue,  it makes sense to implement |mapCont| and |mfixish| for this monad.  For a demonstration of |mfixishQW|,  we implement Chris Okasaki's breadth-first renumbering algorithm~\cite{okasaki00} in Listing~\ref{renum}.  \begin{listing} \begin{code}-newtype CorecQW w e a +newtype CorecQW w e a      =  CorecQW { unCorecQW :: ContT ([e],w) (Reader (Len [e])) a }         deriving (Monad) @@ -952,23 +955,23 @@ \end{listing}  -Chris Okasaki's algorithm uses two queues and a stack to relabel a tree with increasing integers.  Our implementation makes use of two seperate,  corecursive queues in place of the first-class queues used in the original paper.   In both Chris Okasaki's original implementation and ours,  the stack is represented implicitly using the program stack.   As the stack guards the second queue from falling off the end and entering a nonproductive loop,  there is no need to track the length of this second queue explicitly. +Chris Okasaki's algorithm uses two queues and a stack to relabel a tree with increasing integers.  Our implementation makes use of two seperate,  corecursive queues in place of the first-class queues used in the original paper.   In both Chris Okasaki's original implementation and ours,  the stack is represented implicitly using the program stack.   As the stack guards the second queue from falling off the end and entering a nonproductive loop,  there is no need to track the length of this second queue explicitly.  Although our rendering of Chris Okasaki's solution is \emph{implemented} using corecursion;  the function itself is \emph{not} corecursive.   It cannot renumber the Stern-Brocot tree, for example.   Instead it gets stuck in an infinite nonproductive loop.   For a truly corecursive implementation of breadth-first renumbering,  we recall Jones and Gibbons' solution~\cite{okasaki00}\cite{jones93} in Listing~\ref{lazyRenum}.  \begin{listing} \begin{code} renum :: Integral int => Tree a b -> Tree int int-renum t = last q2 +renum t = last q2   where     (_, q2) = runCorecQW (mfixishQW (\q2 -> trav 0 q2 t >> return [])) -    trav n q t@(Leaf _) -       =  do -          q' <- mtrav (n+1) q +    trav n q t@(Leaf _)+       =  do+          q' <- mtrav (n+1) q           mapCC ((Leaf n):) (return q')-    trav n q t@(Branch _ l r) -       =  do  +    trav n q t@(Branch _ l r)+       =  do           enQ l >> enQ r           mtrav (n+1) q >>= \(r':l':q') ->             mapCC ((Branch n l' r'):) (return q')@@ -998,11 +1001,11 @@  \subsection{Performance of CorecQW} -|CorecQW| exhibits a subtle performance discrepancy;  due to the fact that we are returning lazy pairs,  there are two paths of execution through the computation.   Which path is followed depends on whether the consumer is demanding elements of the queue,  or part of the result.  This concept is fairly well known among logic programmers,  but may be suprising to many functional programmers. +|CorecQW| exhibits a subtle performance discrepancy;  due to the fact that we are returning lazy pairs,  there are two paths of execution through the computation.   Which path is followed depends on whether the consumer is demanding elements of the queue,  or part of the result.  This concept is fairly well known among logic programmers,  but may be suprising to many functional programmers.  When applied to the running example of breadth first search, returning lazy pairs incurs either about 25\% or 63\% abstraction penalty compared to the original |CorecQ|,  even if the extra result is |()|.  Eager programmers accustomed to quality implementations of ML and Scheme are used to returning multiple values with little or no undue overhead.  To be fair,  GHC performs similar optimizations on strict pairs~\cite{bgj04}, and neither Scheme nor ML offer lazy tuples nativly.   Supporting lazy tuples efficiently is a significantly harder problem. -As a thought experiment,  I attempted to implement my own value return mechanism,  by starting with the original |CorecQ| and using |unsafePerformIO| and |IORefs| to open up a ``side channel.''  In the process,  I broke the full laziness optimization, \cite{santos95}  which must be turned off in order for this code to terminate.   It was instructive,   as I'm suspicious I ended up creating something similar to what GHC is already doing.   +As a thought experiment,  I attempted to implement my own value return mechanism,  by starting with the original |CorecQ| and using |unsafePerformIO| and |IORefs| to open up a ``side channel.''  In the process,  I broke the full laziness optimization, \cite{santos95}  which must be turned off in order for this code to terminate.   It was instructive,   as I'm suspicious I ended up creating something similar to what GHC is already doing.  The basic idea is that if we demand the result,  we enter a thunk which forces a small bit of queue computation, and then re-reads itself.   This process repeats until the queue computation terminates:  then the thunk gets replaced with a concrete value which gets returned the next time the thunk re-reads itself.   By enabling the trace output and running this code,  you can see it in action. @@ -1024,12 +1027,12 @@  instance Show e => MonadQueue e (Q r e) where   enQ x = Q (\k r e !n xs ->  let  xs' = (k () r e $! n+1) xs-                              in   trace ("enQ $ " ++ show x) +                              in   trace ("enQ $ " ++ show x)                                    (unsafeWrite e xs' `seq` (x:xs'))  )   deQ   = Q delta     where       delta k r e      0        xs   = k Nothing r e 0 xs-      delta k r e (n+  1)  (x:  xs)  = trace  ("deQ " ++ show x) +      delta k r e (n+  1)  (x:  xs)  = trace  ("deQ " ++ show x)                                               (k (Just x) r e n xs)  runQ m = (trace "reading return value" `seq` unsafeRead r (), queue)@@ -1042,7 +1045,7 @@                  trace "reading return value\n" (return ())                  f <- readIORef r                  return (f ())-     e  = unsafeNew queue +     e  = unsafeNew queue      queue = unQ m breakK r e 0 queue  force []     = return ()@@ -1054,7 +1057,7 @@ \caption{Side channel thought experiment} \end{listing} -Let me emphasize I am not advocating this style of programming, nor the use of this code!  In fact,  GHC's native tuples are faster!  This code is simply to demonstrate the two code paths,  and as such will produce different output depending on whether or not one demands the result.    +Let me emphasize I am not advocating this style of programming, nor the use of this code!  In fact,  GHC's native tuples are faster!  This code is simply to demonstrate the two code paths,  and as such will produce different output depending on whether or not one demands the result.  This experiment appears to be a constant factor slower than GHC's tuples.  It exhibits the same performance dissimilarity between the two code paths.  It appears to work in the presence of |callCC|, but only implements |mapCont| for the queue, not the result.   Thus an incremental |foldrByLevel| is not possible with this monad. @@ -1062,20 +1065,20 @@  \begin{figure} \begin{center}-\tabular{l r r r r r} +\tabular{l r r r r r} Description & \multicolumn{2}{c}{Time} & \multicolumn{2}{c}{-H500M} & Bytes \\   & mean & $\sigma$ & mean & $\sigma$ &  \\ \hline-levelOrder'      &  446 &  5 &   172 &  15 &  44.0 \\ -CorecQ           &  555 &  5 &   619 &   4 & 133.5 \\ +levelOrder'      &  446 &  5 &   172 &  15 &  44.0 \\+CorecQ           &  555 &  5 &   619 &   4 & 133.5 \\ CorecQW \_       &  696 &  5 &  1128 &   6 & 213.6 \\-CorecQW ()       &  907 & 56 &  2235 &  11 & 213.6 \\ -Side Channel \_  &  959 &  3 &  1171 &   7 & 228.7 \\ -Side Channel ()  & 1500 & 56 &  2171 &   7 & 276.4 \\ -STQ              & 1140 &  8 &  1087 &  14 & 371.2 \\ -TwoStack         & 1158 &  4 &   778 &  10 & 185.8 \\ +CorecQW ()       &  907 & 56 &  2235 &  11 & 213.6 \\+Side Channel \_  &  959 &  3 &  1171 &   7 & 228.7 \\+Side Channel ()  & 1500 & 56 &  2171 &   7 & 276.4 \\+STQ              & 1140 &  8 &  1087 &  14 & 371.2 \\+TwoStack         & 1158 &  4 &   778 &  10 & 185.8 \\ %  Wrapped in CpSt    & 1177 &  5 &   971 &   6 & 219.0 \\-%  returning list     & 1345 &  8 &  1144 &   6 & 281.9 \\ -Okasaki          & 1553 &  7 &  1574 &  12 & 209.0 \\ +%  returning list     & 1345 &  8 &  1144 &   6 & 281.9 \\+Okasaki          & 1553 &  7 &  1574 &  12 & 209.0 \\ Data.Sequence    &  962 &  5 &  1308 &   5 & 348.1 \\ %  return listing   & 1046 &  5 &  1525 &  11 & 412.5 \\ \caption{Performance using GHC 6.10.3}@@ -1087,13 +1090,13 @@  \begin{figure} \begin{center}-\tabular{l r r r r r} +\tabular{l r r r r r} Description & \multicolumn{2}{c}{Time} & \multicolumn{2}{c}{-H500M} & Bytes \\   & mean & $\sigma$ & mean & $\sigma$ &  \\ \hline-levelOrder'      &  461 &  2 &   173 &  15 &  44.1 \\ -CorecQ           &  458 &  4 &   267 &  13 &  67.5 \\ -CorecQW \_       &  526 &  5 &   713 &   5 & 141.2 \\ -CorecQW ()       &  781 & 62 &  1775 &  62 & 141.3 \\ +levelOrder'      &  461 &  2 &   173 &  15 &  44.1 \\+CorecQ           &  458 &  4 &   267 &  13 &  67.5 \\+CorecQW \_       &  526 &  5 &   713 &   5 & 141.2 \\+CorecQW ()       &  781 & 62 &  1775 &  62 & 141.3 \\ \endtabular \caption{Performance using GHC 6.8.3} \end{center}@@ -1105,7 +1108,7 @@  Note that the code in this paper was not benchmarked directly for a variety of reasons. Each description is essentially equivalent to |levelOrder''| (Listing~\ref{levelOrder''}) run with the appropriate monad.   This means that the bottom four variants don't return anything useful.  While this isn't fair for implementing a drop-in replacement for |levelOrder' :: Tree a b -> [Tree a b]|,  it is more fair for comparing the relative performance of the queues themselves. -The tests were also attempted using the {\tt -Hsize} option to set a suggested heap size and reduce the frequency of garbage collection;  this did indeed reduce the percentage of time spent in the garbage collector,  but this was usually more than offset in increased time spent in the mutator.  +The tests were also attempted using the {\tt -Hsize} option to set a suggested heap size and reduce the frequency of garbage collection;  this did indeed reduce the percentage of time spent in the garbage collector,  but this was usually more than offset in increased time spent in the mutator.  \section{Related Work} @@ -1121,7 +1124,7 @@  \section{Acknowledgements} -I'd like to thank Amr Sabry and Olivier Danvy for particularly useful comments, Matt Hellige for a fun discussion that lead to the |unsafePerformIO| thought experiment, Matt Morrow the insight that |mapCont| could not be implmented on |CpSt|,  Andres L\"oh for some assistance with LaTeX,  Stefan Ljungstrand for some criticism,  and others including Dan Friedman, Will Byrd, Aziz Ghuloum,  Ron Garcia, Roshan James, and Michael Adams,  who enthusiastically endured my often inept attempts at explaining this work before I really understood it.+I'd like to thank Amr Sabry and Olivier Danvy for particularly useful comments, Matt Hellige for a fun discussion that lead to the |unsafePerformIO| thought experiment, Matt Morrow for the insight that |mapCont| could not be implemented on |CpSt|,  Andres L\"oh for some assistance with LaTeX,  Stefan Ljungstrand for some criticism,  and others including Dan Friedman, Will Byrd, Aziz Ghuloum,  Ron Garcia, Roshan James, Michel Salim, and Michael Adams,  who enthusiastically endured my often inept attempts at explaining this work before I really understood it.  I'd also like to acknowledge the giants whose shoulders made this work possible,  including Richard Bird, Philip Wadler,  Daniel Friedman and David Wise,  the designers and implementors of Haskell and the Monad Template Library,  and of course,  Robin Milner and  J. Roger Hindley.