Hackle's blog
between the abstractions we want and the abstractions we get.

# callCC in Haskell, and my ultimate Monad

I've long since promised myself to write about callCc in Haskell. Not because I have a crystal understanding of its intricacies, but because I think it's such a thing of beauty and by writing about it, I will better commit it to my sieve-like memory. So, here we go...

(Reference: this is where I first learned about callCC. There is no way I can make a better writing on `callCC` - again I am only trying to capture my journey in comprehending it.)

## The types

Let's start with the `Cont` type:

``````data Cont r a = Cont { unCont:: ((a -> r) -> r) }
``````

This wraps around a continuation, which basically says, if you give me a function `a->r`, you will get a `r` back.

What does this mean?

• first `a` must come from somewhere, and chances are, it will be encoded in `Cont`.
• secondly the type of `r` is completely up to the consumer

That's when `runCont` comes handy:

``````runCont :: Cont r a -> (a -> r) -> r
runCont k f = unCont k \$ f
``````

Let's see an example:

``````*Main> let c = Cont (\$ 1)
*Main> runCont c (+ 2)
3
*Main> runCont c show
"1"
*Main> runCont c (\x -> [x])

``````

So on and on, you get the idea. You'll notice it's pretty similar to call-backs.

## the `Cont` monad

Yes yes I hear you - everything has a chance to be a Monad until we prove otherwise. In fact let's go through the whole Functor - Applicative - Monad thing (manually), just to get used to the whole `Cont` idea.

### Functor

``````instance Functor (Cont r) where
a2b `fmap` m = Cont \$ \b2r -> runCont m \$ \a -> b2r (a2b a)
``````

I've named the functions to better illustrate their types so save us a bit of guessing.

With this we can do:

``````*Main> runCont ((* 2) <\$> Cont (\$ 3)) id
6
``````

### Applicative

``````instance Applicative (Cont r) where
pure a = Cont \$ \a2r -> a2r a
ma2b <*> m = Cont \$ \b2r -> runCont m \$ \a -> runCont ma2b \$ \a2b -> b2r (a2b a)
``````

Again I try to keep it verbose here. It may appear a bit overwhelming with the levels of nesting. I find understanding `runCont` is essential here, it takes a function with type `a -> r`, and the easiest way to get such function, is to make it by going `\a -> ...try to get an r`,

After `Applicative` hopefully `Monad` becomes straightforward here.

``````instance Monad (Cont r) where
return = pure
ma >>= a2mb = Cont \$ \b2r -> runCont ma \$ \a -> runCont (a2mb a) \$ \b -> b2r b
``````

Again I find explicit naming and verbosity really helpful here. Now we can do

``````*Main> let a2mb = \n -> Cont (\f -> f \$ n * 2)
*Main> let mb = Cont (\f -> f 3) >>= a2mb
*Main> runCont mb id
6
``````

## `CallCC`

Below it's an implementation of the ~~in~~famous `CallCC`:

``````myCallCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
myCallCC a2mb2ma =
Cont \$ \a2r -> let  a2mb = \a1 -> Cont \$ \b2r -> a2r a1
ma = a2mb2ma a2mb
in runCont ma \$ \a2 -> a2r a2
``````

I won't blame you if you find this a bit overwhelming... but in all honesty, I simply followed the types to complete the implementation... and by the time it type checks, I actually still couldn't fully comprehend what I have just written - but it works! Gotta love the type system. Well, let's try to analyse this! (Or skip to the next section if my analysis makes you dizzy).

• the name & type of `a2mb2ma :: (a -> Cont r b) -> Cont r a` is a strange one, to say the least. So there is this function `(a -> Cont r b)`, which is parameter to another function that somehow to return a `Cont r a`, and this as `yet` another function, is parameter to `myCallCC` that returns a `Cont r a`... but wait, what happens to `Cont r b`? Is it thrown away?

• now look at the implementation, `a2r` is applied twice, first time to satisfy the return types of `Cont r b`, as we don't have any ways to get a value of type `b`, so to satisfy `b -> r`, we apply `a2r a`. Which means `b2r` is actually thrown away!

• the second time a2r is applied, is to run `ma` which is the result of applying `a2mb2ma`, the difference is, now we do have a value of type `a`.

My gut feeling is - out these 2 applications, one of them is redundant.

Now I am not really one of these super smart people who can decode this, so I will need a dumb way to find out what's going on. In Haskell, luckily, thanks to purity, mostly of the time we can just use Equational Reasoning.

## Equational Reasoning

Now first let's see `myCallCC` in action. Copied from the Reference page.

``````quux = myCallCC \$ \k -> do
k 5
return 25
``````

And here comes the magic bit, if you run the result continuation...

``````*Main> let quux = myCallCC \$ \k -> do { k 5; return 25 }
*Main> runCont quux id
5
``````

So the Monad block `do { k 5; return 25 }` has been transformed by `myCallCC` to not execute `return 25`. In fact, anything after invocation of `k` will be ignored. Isn't that the weirdest thing?! Oh well, let's find out why.

To get on with equational reasoning, first we expand the above call to `myCallCC` with the argument. It'll be lengthy but bear with me.

``````quux =
Cont \$ \a2r -> let  a2mb = \a1 -> Cont \$ \b2r -> a2r a1
ma = (\k -> do { k 5; return 25 }) a2mb
in runCont ma \$ \a2 -> a2r a2
``````

Try apply `a2mb` to `\k...`

``````quux =
Cont \$ \a2r -> let  a2mb = \a1 -> Cont \$ \b2r -> a2r a1
ma = do { a2mb 5; return 25 }
in runCont ma \$ \a2 -> a2r a2
``````

And expand a2mb

``````quux =
Cont \$ \a2r -> let  ma = do { (\a1 -> Cont \$ \b2r -> a2r a1) 5; return 25 }
in runCont ma \$ \a2 -> a2r a2
``````

And apply `5` to `\a1 ...`

``````quux =
Cont \$ \a2r -> let  ma = do { Cont \$ \b2r -> a2r 5; return 25 }
in runCont ma \$ \a2 -> a2r a2
``````

And expand `ma`,

``````quux =
Cont \$ \a2r -> runCont (do { Cont \$ \b2r -> a2r 5; return 25 }) \$ \a2 -> a2r a2
``````

Now if we try to put `\a2 -> a2r a2` in place of `b2r`, we'll find it's never used! So the above expression can be simplified as

``````quux = Cont \$ \a2r -> runCont (do { Cont \$ \_ -> a2r 5; return 25 }) undefined
``````

Now if we go one level up and try to expand `runCont quux id`:

``````runCont quux id = runCont (do { Cont \$ \_ -> id 5; return 25 }) undefined
``````

And let's bring it to the REPL:

``````*Main> runCont (do { Cont \$ \_ -> id 5; return 25 }) undefined
5
``````

Aha! That is it - the trick is in the `do` block, or, in the `Cont` Monad! For record's sake, let's desugar the whole `do` block:

``````runCont \$ (Cont \_ -> id 5) >>= (\_ -> return 25) ...
-- and according to
-- ma >>= a2mb = Cont \$ \b2r -> runCont ma \$ \a -> runCont (a2mb a) \$ \b -> b2r b

runCont \$ Cont \$ \b2r -> runCont (Cont \_ -> id 5) \$ \a -> runCont (\_ -> return 25) \$ \b -> b2r b ...

-- remember runCont k f = unCont k \$ f
runCont \$ Cont \$ \b2r -> runCont (Cont \_ -> id 5) \$ \a -> return 25 ...
-- again
runCont \$ (Cont \$ \b2r -> id 5) undefined

-- eventually
id 5
``````

There we are! `myCallCC` demystified!

To recap:

• `a2mb`/`k` captures an argument (`5` in our example) and turns that into a `Cont`, which is special in that it will ignore any code after it in the do block.
• `a2r` is applied to the argument to `a2mb`/`k`, in our example, value `5`, but not to the seeming result - the last `Cont` in the `do` block - which is ignored in our example!

## Simplify

With the above finding, we can now simplify `myCallCC` to

``````myCallCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
myCallCC a2mb2ma =
Cont \$ \a2r -> let  a2mb = \a1 -> Cont \$ \_ -> a2r a1
ma = a2mb2ma a2mb
in runCont ma undefined
``````

It may seem a bit ungainly to leave an `undefined` at the end, but since it clearly shows the intent of ignoring any input in its place, I personally think it's fine.

## Summary

At first look, `callCC` might not be for the faint-hearted, but as we look closer and closer, there is no magic (although almost indistinguishable from it!) but a clever usage of `Monad`.

In trying to comprehend it, Equational Reasoning proves a powerful tool to me. Unfortunately this is not the case for non-pure functions / languages. What that means to me - all the more reason for us to use pure languages like Haskell, or if that's not immediately possible, try to write as much pure code as we can!

You can find all the source code for this article here