The ContT Monad: Putting the pieces together

Question

Preamble

I am trying to wrap my head around how to actually use ContT and callCC for something useful. I'm having trouble following information and control flows around the the code. (but, isn't that the point of a continuation?)

There are a lot of different ways to move pieces around with this monad and a small handful of not very straight forward combinators. I will confess that I'm still uncomfortable with my understanding of how ContT works, but I will point to what I have read so far:

• Haskell/Continuation passing style
• How and why does the Haskell Cont monad work?
• Understanding Haskell callCC examples
• Goto in Haskell: Can anyone explain this seemingly insane effect of continuation monad usage?
• How to interpret callCC in Haskell?
• Parsec Generally (the article that started me down this path)

What I would like to do is post a psudo-code example then ask some questions about it. This represents the typical look of code using ContT

Psudo-Code

type MyMonad r = ContT r (State SomeState)

main = do
  runState s_init $ runContT block print

block :: MyMonad r a0
block = do
  before_callcc
  output <- callCC $ \k -> do
    rval <- inner_block
    return rval
  after_callcc

Questions

1. What determines the value and type of output?
2. What does the b mean in the type of k?
3. Where does the value given to k go?
4. When is inner_block run? What version of the state does it see?
5. Where does rval go and what its type?
6. What is the relationship between k and rval?
7. What happens when I apply k a) in inner_block, b) in after_callcc, c) outside of block?
8. What is the version of the state in each of the above?
9. What do I need to do to get k out of block?
10. Can I put k into the state?

---

Color Coded for easier reading

Answer 1

1. What determines the value and type of output?

It will be of the same type as rval. The value will also be the same, unless inner_block uses k someValue to escape the rest of the block. In that case, output will be someValue.

2. What does the b mean in the type of k?

Roughly, b can be understood as "anything at all". That is, if inner_block is

...
v <- k someValue
use v

then v :: b. However, k someValue will never run the rest of the block since it will exit the callCC immediately. So, no concrete value for v will be ever returned. Because of this v can have any type: it does not matter if use requires a String or an Int -- it's not being executed anyway.

3. Where does the value given to k go?

As soon as the inner block runs k someValue the value is returned by the callCC as output, and the rest of the block is skipped.

4. When is inner_block run? What version of the state does it see?

It is run as callCC is called, and sees the same state as we had at that point.

5. Where does rval go and what its type?

Into output. Same type.

6. What is the relationship between k and rval?

rval has the same type as the argument of k.

7. What happens when I apply k a) in inner_block, b) in after_callcc, c) outside of block?

a) See above. b) k is out of scope in after_callcc. c) Also out of scope.

8. What is the version of the state in each of the above?

The state is the "current" one. (I am not sure what you exactly are asking for here)

9. What do I need to do to get k out of block?

A recursive type is needed here, I guess. Here's an attempt:

import Control.Monad.Cont
import Control.Monad.State
import Control.Monad.Trans

type SomeState = String
type MyMonad r = ContT r (State SomeState)

newtype K a b r = K ((K a b r, a) -> MyMonad r b)

main = do
  print $ flip runState "init" $ runContT block return

block :: MyMonad r Int
block = do
  lift $ modify (++ ":start")
  (K myK, output) <- callCC $ \k -> do
    s <- lift $ get
    lift $ modify (++ ":inner(" ++ show (length s) ++")")
    return (K k, 10)
  lift $ modify (++ ":output=" ++ show output)
  s <- lift $ get
  when (length s <50) $ myK (K myK, output+1)
  return 5

This prints

(5,"init:start:inner(10):output=10:output=11:output=12")

10. Can I put k into the state?

I believe you need a recursive type for that, too.