Loops

Loops are really easy to implement using continuations in Scheme. In Haskell, they technically don't require continuations at all. They're nothing but tail-recursive functions. However, it may be instructive to figure out how to implement loops using the Cont monad.

Let's go completely wild. We want to built a 1-to-1 translation of the Scheme code

(define (print-thrice)
  (let* ((i 0)
         (repeat (call/cc (lambda (c) c))))
    (when (< i 3)
      (display "Hello world!")
      (newline)
      (set! i (+ i 1))
      (repeat repeat))))

This code

Prints "Hello world!", so the Haskell version needs the IO monad.
Has a mutable variable i that is used as a counter. To simulate this in Haskell, we need the State monad.
Uses continuations to build the loop. So we need the Cont monad.

In other words, we need a monad that supports I/O, state, and continuations. Easy peasy, we build a transformer stack:

type Prog a = ContT () (StateT Int IO) a

This equips IO with a state of type Int and then equips the resulting monad with continuations.

Here's the complete code:

PrintThrice.hs

import Control.Monad (void, when)
import Control.Monad.Cont (ContT, runContT, callCC)
import Control.Monad.IO.Class (liftIO)
import Control.Monad.State (StateT, evalStateT, get, put)

type Prog a = ContT () (StateT Int IO) a

main :: IO ()
main = evalStateT (runContT prog return) 0

prog :: Prog ()
prog = do
    repeat <- callCC $ let f yield = yield (void $ f yield)
                       in  f
    i <- get
    when (i < 3) $ do
        put (i + 1)
        liftIO $ putStrLn $ "Hello world!"
        repeat

The actual program is prog. main runs this program using runContT prog return to obtain a computation in the underlying monad, which is StateT Int IO. It then runs this computation using evalState, providing 0 as the initial state. That's the same as the initializition of i to 0 in the second line of the Scheme code.

prog builds the loop just as the Scheme version by calling callCC with a function as argument that returns an action we can call to make callCC return. It would be tempting to implement this function as \yield -> return yield, which is the equivalent of the Scheme version (lambda (c) c). The problem is that if you play with this a little, there is no way to make this code type-check. The value repeat returned by callCC would have to have an infinite type, something that is not allowed in Haskell.

So we need a slightly more complex solution. The function we're passing to to callCC is a function

f :: (Prog () -> Prog (Prog ())) -> Prog (Prog ())

So the argument yield of f needs to have type Prog (), that it, it is an action in the Prog monad. That's exactly what we want the value repeat returned by callCC to be. f must return a value of the same type, so the return type of f is Prog (Prog ()). Since the implementation of f only calls yield, the result type of yield must also be Prog (Prog ()). So that's the type of f. What does it do?

f yield calls yield with the argument void $ f yield. That is, the action repeat returned by callCC is the action that calls f yield again. Thus, by calling repeat again and againwe can makecallCC` return again and again. We got ourselves a mechanism to build a loop.

It would be tempting to to define f simply as f yield = yield (f yield). That's what we want repeat to be, an action that calls f yield again. Unfortunately, this would once again lead to an infinite type for f. Thus, we turn the action f yield, which has the type Prog (Prog ()) into an action that has the type Prog () by wrapping it in void.

With repeat in hand, the rest is easy. We read the current value of i using get. If this value is less than 3, we update our state using put (i + 1), print "Hello world!" once using liftIO $ putStrLn "Hello world!", and then start another iteration by invoking repeat.

This is one example where liftIO comes in handy. Without it, we would have had to write lift $ lift $ putStrLn "Hello world!" because the IO monad is wrapped in two monad transformers.

You can try out the code. It works as expected:

GHCi

>>> :l PrintThrice.hs
[1 of 1] Compiling Main             ( PrintThrice.hs, interpreted )
Ok, one module loaded.
>>> main
Hello world!
Hello world!
Hello world!