Understanding Haskell callCC examples

Question

I am having trouble understanding the answers to a previous question. I'm hoping that an explanation of the following will clarify things. The following example comes from fpcomplete

import Control.Monad.Trans.Class
import Control.Monad.Trans.Cont

main = flip runContT return $ do
    lift $ putStrLn "alpha"
    (k, num) <- callCC $ \k -> let f x = k (f, x)
                               in return (f, 0)
    lift $ putStrLn "beta"
    lift $ putStrLn "gamma"
    if num < 5
        then k (num + 1) >> return ()
        else lift $ print num

The output is

alpha
beta
gamma
beta
gamma
beta
gamma
beta
gamma
beta
gamma
beta
gamma
5

I think I understand how this example works, but why is it necessary to have a let expression in the callCC to "return" the continuation so that it can be used later on. So I tried to directly return the continuation by taking the following simpler example and modifying it.

import Control.Monad.Trans.Class
import Control.Monad.Trans.Cont

main = flip runContT return $ do
    lift $ putStrLn "alpha"
    callCC $ \k -> do
      k ()
      lift $ putStrLn "uh oh..."
    lift $ putStrLn "beta"
    lift $ putStrLn "gamma"

This prints

alpha
beta
gamma

And I modified it to the following

import Control.Monad.Trans.Class
import Control.Monad.Trans.Cont

main = flip runContT return $ do
    lift $ putStrLn "alpha"
    f <- callCC $ \k -> do
      lift $ putStrLn "uh oh..."
      return k
    lift $ putStrLn "beta"
    lift $ putStrLn "gamma"

The idea being that the continuation would get returned as f and be unused in this test example which I would expect to print

uh oh...
beta
gamma

But this example doesn't compile, why can't this be done?

Edit: Consider the analgous example in Scheme. As far as I know Scheme wouldn't have a problem, is that correct?, but why?.

Answer 1

Looking at your examples in reverse order.

The last example does not typecheck due to an infinite type. Looking at the type of callCC, it is ((a -> ContT r m b) -> ContT r m a) -> ContT r m a. If we try to return the continuation we return something of type ContT r m (a -> ContT r m b). This means we get the type equality constraint a ~ (a -> ContT r m b), which means a has to be an infinite type. Haskell does not allow these (in general, for good reason - as far as I can tell the infinite type here would be something along the lines of, supply it an infinite order function as an argument).

You don't mention whether there's anything you're confused about in the second example, but. The reason that it does not print "uh oh..." is because the ContT action produced by k (), unlike many ContT actions does not use the following computation. This is the difference between the continuations and just normal functions which return ContT actions (disclaimer, any function could return a ContT action like this, but in general). So, when you follow the k () up with a print, or anything else, it is irrelevant, because the k () just discards the following actions.

So, the first example. The let binding here is actually only used to mess around with the parameters to k. But by doing so we avoid an infinite type. Effectively, we do some recursion in the let binding which is related to the infinite type we got before. f is a little bit like a version of the continuation with the recursion already done.

The type of this lambda we pass to callCC is Num n => ((n -> ContT r m b, n) -> ContT r m b) -> ContT r m (n -> ContT r m b, n). This does not have the same infinite type problem that your last example has, because we messed around with the parameters. You can perform a similar trick without adding the extra parameter by using let bindings in other ways. For example:

recur :: Monad m => ContT r m (ContT r m ())
recur = callCC $ \k -> let r = k r in r >> return r

This probably wasn't a terribly well explained answer, but the basic idea is that returning the continuation directly will create an infinite type problem. By using a let binding to create some recursion inside the lambda you pass to callCC, you can avoid this.