On Tue, 12 Mar 2013 12:53:37 +0100 Ertugrul Söylemez wrote:

...

Dmitriy Matrosov 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 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 quickly.

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 wrapper): 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" 8 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: | v 3 'f-1' 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: 3 'f-1' 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 return 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 :-) -- Dmitriy Matrosov