Haskell Sequels

Continuation is a state of the program at a certain moment, which we can then use to return to that state.
With the help of continuations, you can implement exception handling, goto-like and many other things resembling imperative constructs.
Also, using continuations, you can improve program performance by removing unnecessary “wrappings” and pattern matching.

In this article, I’ll tell you how you can implement Haskell continuations and show you some interesting functions that work with them.

Continuation style programming

To begin with, let's see what continuation is and continuation programming.

Common features:
')
square :: Int -> Int
square x = x*x

incr :: Int -> Int
incr x = x+1

func :: Int -> Int
func x = square (incr x)

And now in the style of sequels:

 square_cps :: Int -> (Int -> r) -> r square_cps xk = k (x*x) incr_cps :: Int -> (Int -> r) -> r incr_cps xk = k (x+1) func_cps :: Int -> (Int -> r) -> r func_cps xk = incr_cps x $ \inc -> square_cps inc $ \sq -> k sq 

Now functions except the arguments themselves take as input the function that will be applied to the result. This is the continuation.
With the help of continuations we can connect functions, which is what happens in func_cps . At first, incr_cps is incr_cps , and its result is “caught” in the continuation (\inc -> ...) , then square_cps is square_cps whose result is passed to the continuation (\sq -> ...) , which is finally given to the outermost continuation k .

The extensions here are of type (Int -> r) since it is not necessary that the continuation returns an Int .
For example, to output the result to the console, we can pass print as a continuation:

main = func_cps 5 print

Monad cont

You may notice some patterns in the style of continuations.
For example, simple functions such as square_cps and incr_cps , we declared in a similar way:

function ... = \k -> k (...)

And we connected them like this:

 fun1 ... $ \r1 -> fun2 ... $ \r2 -> ... 

All this reminds us of monads, the first example is similar to return , and the second to >>= .

We introduce the Cont monad as:

newtype Cont ra = Cont { runCont :: (a -> r) -> r }

But why (a -> r) -> r ?
The fact is that when we wrote functions in the continuation style, each function took an additional parameter that continues the calculation.
If we “fill” a function in the style of continuations with arguments (up to the continuation), its type will be (a -> r) -> r , where a is the result type of the function, if we simply returned it, without passing it on to continuation, and r the type of result that the continuation returns:

> :t square_cps 5
square_cps :: (Int -> r) -> r

Let's try to make Cont monad.

 instance Monad (Cont r) where return n = Cont $ \k -> kn ... 

return n is Cont which immediately applies n to the continuation it received.

  m >>= f = Cont $ \k -> runCont m (\a -> runCont (fa) k) 

m >>= f is a Cont that runs ( runCont just “unpacks” Cont, freeing the function) m with a continuation (\a -> runCont (fa) k) , which can be received the result of the calculation, and assign it to a (or and will not receive, because the function can ignore the sequel). Then, a will be applied to f to get another Cont, which, in turn, will be launched with the outermost continuation k .

Rewrite our program using the Cont monad:

 square_Cont :: Int -> Cont r Int 
 square_Cont x = return (x*x) 
 
 incr_Cont :: Int -> Cont r Int 
 incr_Cont x = return (x+1) 
 
 func_Cont :: Int -> Cont r Int func_Cont x = do inc <- incr_Cont x sq <- square_Cont inc return sq 

main = runCont (func_Cont 5) print

Now everything looks much clearer.

Let's move on to the functions that work with Cont.

callCC

Let's start with a simple example:

square :: Int -> Cont r Int
square n = callCC $ \k -> k (n*n)

What a useless feature? More like it's just a synonym for the Cont constructor.
But everything is not so simple. Let's look at the callCC type:

callCC :: ((a -> Cont rb) -> Cont ra) -> Cont ra

callCC , callCC takes a function that takes another function, such as (a -> Cont rb) , and returns Cont ra . That is, k (n*n) in our example is of the type Cont r Int .
What can callCC be used callCC ? For example, to quickly exit a function:

 import Control.Monad (when) hehe :: Int -> Cont r String hehe n = callCC $ \exit -> do let fac = product [1..n] when (n > 7) $ exit "OVER 9000" return $ show fac main = do n <- fmap read getLine runCont (hehe n) putStrLn 

Let's test our program:

> main
3
6
> main
10
OVER 9000

This program calculates the factorial, and if it turns out to be more than 9000, it returns the message “OVER 9000”, and if not, then just its value.
Here we used exit as a return in imperative languages ​​- he interrupted the calculation and derived a different result.

It is also possible to use nested callCC blocks:

 bar :: String -> Cont r String bar s = do callCC $ \exit1 -> do let ws = words s names = foldl (\ac -> a ++ ", " ++ c) (head ws) (tail ws) r' <- callCC $ \exit2 -> do when (null ws) $ exit1 "No people" when (length ws == 1) $ exit2 "There is " return "There are: " return $ r' ++ names main = do ns <- getLine runCont (bar ns) putStrLn 

Let's try:

> main

No people
> main
Bob
There is Bob
> main
Bob Alice
There are: Bob, Alice

If the list of names is empty, then call exit1 "No people" , "jumping over" through the internal block.
If there is one person, we use “There is”, if there are a lot of them, then “There are:”.
Notice that when the calculation reaches return in the callCC block, the result is returned as usual.

So how is the callCC function callCC ? Let's get a look:

callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> ka)) k

It begins in the usual way, with wrapping the function in the style of continuations in Cont. Then (f (\a -> Cont $ \_ -> ka)) starts with the continuation k .
(\a -> Cont $ \_ -> ka) is a function that takes something and returns Cont, ignoring its continuation and using k instead.

Let us see how it works:

square n = callCC $ \k -> k (n*n)
= Cont $ \k' -> runCont ((\k -> k (n*n)) (\a -> Cont $ \_ -> k' a)) k'
= Cont $ \k' -> runCont ((\a -> Cont $ \_ -> k' a) (n*n)) k'
= Cont $ \k' -> runCont (Cont $ \_ -> k' (n*n)) k'
= Cont $ \k' -> (\_ -> k' (n*n)) k'
= Cont $ \k' -> k' (n*n)

All as we expected. Consider the case more complicated:

 hehe :: Int -> Cont r String hehe n = callCC $ \exit -> do let fac = product [1..n] when (n > 7) $ exit "OVER 9000" return $ show fac = callCC $ \exit -> (when (n > 7) $ exit "OVER 9000") >> (return $ show (product [1..n])) --    let   = Cont $ \k -> runCont ((\exit -> (when (n > 7) $ exit "OVER 9000") >> (return $ show (product [1..n]))) (\a -> Cont $ \_ -> ka)) k = Cont $ \k -> runCont ((when (n > 7) $ (\a -> Cont $ \_ -> ka) "OVER 9000") >> (return $ show (product [1..n]))) k = Cont $ \k -> runCont ((when (n > 7) $ (Cont $ \_ -> k "OVER 9000")) >> (return $ show (product [1..n]))) k 

When when it works, it will return (Cont $ \_ -> k "OVER 9000") . This Cont does not use its continuation, so the rest of the code will not be executed.

getCC

The getCC and getCC' functions allow us to “get” the current continuation and use it to return to the previous state of the program.
For example:

 foo :: Int -> Cont r String foo s = do (i, back) <- getCC' s when (i < 20) $ back (i*2) return $ show i 

foo doubles its argument until it becomes greater than or equal to 20.

> runCont (foo 5) id
"20"
> runCont (foo 3) id
"24"
> runCont (foo 2) id
"32"

(i, back) <- getCC' s - assigns i value of s and creates a “link” to this place.
back (i*2) - returns to the past state, but with i equal to i*2 .

All this strongly resembles goto, although here we can only move to the past states.

The getCC' function is declared like this:

 getCC' :: t -> Cont r (t, t -> Cont ra) getCC' x0 = callCC (\c -> let fx = c (x, f) in return (x0, f)) 

Let's try to figure it out. Let's start to simplify it:

getCC' x0 = Cont $ \k -> runCont ((\c -> let fx = c (x, f) in return (x0, f)) (\a -> Cont $ \_ -> ka)) k
= Cont $ \k -> runCont (let fx = (\a -> Cont $ \_ -> ka) (x, f) in return (x0, f)) k
= Cont $ \k -> runCont (let fx = Cont $ \_ -> k (x, f) in return (x0, f)) k
= Cont $ \k -> runCont (let fx = Cont $ \_ -> k (x, f) in Cont $ \k' -> k' (x0, f)) k
= Cont $ \k -> let fx = Cont $ \_ -> k (x, f) in k (x0, f)

The f function applies a pair of its argument and itself to the external (getCC'-shnomu) continuation, and wraps it in Cont.
And k (x0, f) - applies a pair from the getCC' argument and f to the external continuation.
When we call f elsewhere, it returns Cont, using not the current continuation, but the one that was current for getCC' . Thus, we somehow return to the past state.

Also, getCC' has a “little brother” - getCC , but it is only useful with ContT (transformer for Cont):

 import Control.Monad (when) import Control.Monad.Cont getCC :: MonadCont m => m (ma) getCC = callCC (\c -> let x = cx in return x) foo :: ContT () IO () foo = do back <- getCC liftIO $ putStr "Do you want to coninue? [y/n] " a <- liftIO $ getLine when (a == "y" || a == "Y") $ back main = runContT foo return 

> main
Do you want to coninue? [y/n] y
Do you want to coninue? [y/n] y
Do you want to coninue? [y/n] n
>

The program will ask the user for permission to continue until he answers “n”.
This shows that getCC only allows you to return to the past state, but does not give the opportunity to pass arguments.

Where do i use cont?

With the help of continuations, you can flexibly control the course of the program, return from a function before its completion, create an exception system.
It is also possible to “pause” the computation by returning to it at another time (for example, Hugs uses continuations to implement parallelism).

Basically, Cont is used along with other monads as a transformer. This makes it easier to create complex control structures and / or make calculations faster.

List of materials used

Continuation passing style
Goto in haskell
Making Haskell programs faster and smaller