[Haskell-beginners] Suspend/resume computation using Cont monad and callCC
sgf.dma at gmail.com
Tue Mar 12 21:16:05 CET 2013
> On Tue, 12 Mar 2013 12:53:37 +0100
> Ertugrul Söylemez <es at ertes.de> wrote:
> > Dmitriy Matrosov <sgf.dma at gmail.com> wrote:
> > I have two functions f and g, and i want them to execute in
> > following order: first function f runs, then suspends and passes
> > control to function g. Function g runs, then suspends and
> > "unpauses" function f. Function f finishes and passes control to
> > function g, which also finishes. Here is illustration ('o' means
> > start of function, dot means suspend and pass control to other
> > function, 'x' means end of function):
> > [...]
> > I want to implement this using Cont monad and callCC.
> Not directly answering your question, but what you need is called
> coroutines, and there are better monads for that purpose. This is how
> the Cont monads are defined:
> newtype Cont r a = Cont ((a -> r) -> r)
> But what you really need here is called a Coroutine monad:
> newtype Coroutine f a = Coroutine (Either (f (Coroutine f a)) a)
> Don't worry about that scary type, because if you look closely you
> will find that this is just Free as defined in the 'free' package:
> data Free f a
> = Free (f (Free f a))
> | Pure a
> On Tue, 12 Mar 2013 17:54:16 +0000
> Stephen Tetley <stephen.tetley at gmail.com> wrote:
> The resumption monad is even simpler, unfortunately I'm not aware of
> any beginner level tutorials.
> William Harrison at the University of Missouri has some papers
> introducing resumption monads but the presentations then move very
Thanks for suggestions! I'll try them (though, i suppose, to understand Free i
should read at least something about category theory first).
Anyway, i think, that i understand why my implementation works so and
can explain it.
First, i want to remind the implementation of callCC (omiting Cont
callCC f = \k -> let g x = \_ -> k x
in (f g) k
So, actually, callCC provides to function f continuation to monad
following callCC itself. This will be the key in my explanation.
Let's start with first question and explain how fT/gT pair works. Here
is the code from my previous mail with line-numbers:
type T r = ContT r (Writer String)
1 fT :: T r ()
2 fT = do
3 lift $ tell "I'm in f-1\n"
4 k' <- callCC gT
5 lift $ tell "I'm in f-2\n"
6 k' undefined
7 lift $ tell "I'm in f-3\n"
9 gT :: ((() -> T r ()) -> T r ()) -> T r (() -> T r ())
10 gT k = do
11 lift $ tell "I'm in g-1\n"
12 callCC k
13 lift $ tell "I'm in g-2\n"
14 return (\_ -> return ())
And here is illustrations of first part of execution:
4 k' <- callCC gT <--------------------------------
-------> 11 'g-1' |
12 callCC k |
5 'f-2' <-------- |
6 k' -------------> 13 'g-2' |
14 return (\_ -> return ()) ---
I.e. after point 'f-1' function gT is called with continuation k to
line 5. Then after point 'g-1' function gT calls this continuation k
and execution jumps back to line 5 in function f. But because
continuation k have been called in callCC, callCC throws continuation
k' to line 13 (in function g) into continuation k. Then after point
'f-2' function f calls continuation k' to line 13. Function g resumes
execution and finishes. But what is the next continuation now? The one
supplied by (callCC gT) ! And this is again continuation to line 5 in
function f. Here i proceed to second illustration:
4 k' <- callCC gT <---------------------------------
5 'f-2' |
6 k' 13 'g-2' |
7 'f-3' 14 return (\_ -> return ()) ---
So, function f executes again from point 'f-2'. And meet continuation
k' again, but now k' is continuation returned by function gT at line
14. I.e. it is just (\_ -> return ()). Thus, it does nothing and i
proceed to point 'f-3'.
This explains track produced by Writer monad. But there is one more
question: why track produced using monad result differs?
Here is the code from my previous mail:
type M r = Cont r
fM :: M r [String]
fM = do
let xs' = "I'm in f-1" : 
(ys, k') <- callCC (gM xs')
let ys' = "I'm in f-2" : ys
zs <- k' ys'
let zs' = "I'm in f-3" : zs
gM :: [String]
-> (([String], [String] -> M r [String]) -> M r [String])
-> M r ([String], [String] -> M r [String])
gM xs k = do
let xs' = "I'm in g-1" : xs
ys <- callCC (curry k xs')
let ys' = "I'm in g-2" : ys
return (ys', \_ -> return ys')
And if you "trace" its execution in the same manner, you'll notice the
answer: result of monad fM actually determined by call of continuation
k', which occurs during "second" function fM run. And during this
"second" run continuation k' will be (\_ -> return ys'), where ys' is
from function gM. But when ys' had been evaluated in function gM,
second pass through 'f-2' not yet happen! That's why it is missed from
the result as well.
Ugh, well.. that was useless, but still so fascinating :-)
More information about the Beginners