The purpose of this text is to guide a reader through the first step towards grokking continuations as presented in Haskell (callCC not covered). The reader is assumed to have basic knowledge of Haskell including some understanding of monads.
Suppose we are given a list of lists of integers and we want to compute the sum of squares of products of those lists. This task naturally breaks down into three steps:
- Take product of each list of integers and thus form a new list of integers.
- In that list, square every integer, again forming a new list of integers.
- Summate the resulting list.
But to produce this algorithm we need to parse the whole problem and revert it (i. e. start with the last step): the problem's descriptions starts with "sum" and the corresponding algorithm starts with "product". Does it really need to be like this?
Let's attempt writing the code directly:
sumSqProd :: [[Int]] -> Int
sumSqProd xss = sum $ map ...Are you tired yet? Do you really want to summate squares of product or do you want to summate absolute values of maximums? Would you like to make a decision later or to make someone else do all the work besides taking the sum? Probably not, but you can! You just need to abstract everything else away:
sumWhatever :: [[Int]] -> ([Int] -> Int) -> Int
sumWhatever xss = \f -> sum $ map f xssThat's neat. If we are certain about squares and product (and not too lazy), we could finish immediately by providing a function [Int] -> Int that does the rest of computation:
sqProd :: [Int] -> Int
sqProd xs = square $ product xs
where square x = x * x
sumSqProd :: [[Int]] -> Int
sumSqProd xss = sumWhatever xss sqProd> sumSqProd [[1,2],[3,4]]
=> 148
Fine, but what if we are only certain about squares (or not that eager)? We could abstract taking products too:
sqWhatever :: [Int] -> ([Int] -> Int) -> Int
sqWhatever xs = \f -> square $ f xs
where square x = x * xNow that's a pattern. In fact, this pattern is exactly what we call a continuation.
At this point you are probably wondering whether it is easier to write an eager explicit definition of our function than to abstract away all the stuff. Because, after all, it is more lines now and in the end we need to glue everything together which looks like pointless additional headache. Well, first of all, Haskell's fine machinery lets us give a gluing mechanism for once and use it later in every instance, so the overhead is not that bad. Secondly, using continuations is a fine approach to modular and asynchronous programming (consider user interfaces).
Let's get to business already:
newtype Cont r a = Cont ((a -> r) -> r)
runCont :: Cont r a -> (a -> r) -> r
runCont (Cont f) = f
sumCont :: [[Int]] -> Cont Int [Int]
sumCont xss = Cont $ \f -> sum $ map f xss
sqCont :: [Int] -> Cont Int [Int]
sqCont xs = Cont $ \f -> square $ f xs
where square x = x * x
sqProd :: [Int] -> Int
sqProd xs = (runCont $ sqCont xs) product
sumSqProd :: [[Int]] -> Int
sumSqProd xss = (runCont $ sumCont xss) sqProd> sumSqProd [[1,2],[3,4]]
=> 148
In practice, you'd want to use continuations defined in some library from Hackage but for now we will write everything in our own fashion.
So now our functions with abstracted computations have a type a -> Cont r b for some types a, b and r. What we need now is a general way of gluing those functions together, yielding again a similar function.
You've probably heard about categories before; categories are all about composition. And when we talk about composing funny-valued functions (which is exactly our case now), we probably mean Kleisli categories. Kleisli category is built over some predefined category C equiped with a monad m and arrows in the Kleisli category are exactly the arrows from category C of the form a -> m b where a and b are objects of C; composition of said arrows is defined in terms of C composition and monadic operations. Our Cont type constructor indeed yields a monad (with its first type parameter fixed). So essentially giving an appropriate instance of Monad typeclass would give us the desired gluing mechanism for free. But for the sake of clarity, let's take the opposite route: first we will define the composition of funny-valued functions for Cont and then we will define monadic operations in that terms.
Our task now amounts to writing a function of type (a -> Cont r b) -> (b -> Cont r c) -> (a -> Cont r c). You should get some insight from inspecting that type already: to construct a function from a to Cont r c while given functions f :: a -> Cont r b and g :: b -> Cont r c, we need to apply f to our a value and somehow stick the resulting value of Cont r b together with g.
compK :: (a -> Cont r b)
-> (b -> Cont r c)
-> (a -> Cont r c)
compK f g = \x -> -- take x :: a
Cont $ \h -> -- return a Cont which takes h :: c -> r
(runCont $ f x) $ \y -> (runCont $ g y) h
(<==) = compK -- fun notationConstructing a Cont value here is just wraping a function (c -> r) -> r in Cont constructor; so, given h :: c -> r we must return r value, which can be constructed in the following way:
runCont $ f x gives us a function (b -> r) -> r, and our goal is r value;
so we need a function b -> r. Now \y -> (runCont $ g y) h is exactly such function since runCont $ g y gives a vaule of (c -> r) -> r and h :: c -> r.
I know that's lengthy! It might help to write an explicit composition of sumCont and sqCont in the same manner:
sumSqCont :: [[Int]] -> Cont Int [Int]
-- takes sum of squares of somehow folded Int lists
sumSqCont = \xss ->
Cont $ \h ->
(runCont $ sumCont xss) $ \y -> (runCont $ sqCont y) hNow let's see if it actually works:
sumSqProd :: [[Int]] -> Int
sumSqProd xss = (runCont $ sumSqCont xss) product
where sumSqCont = (sumCont <== sqCont)> sumSqProd [[1,2],[3,4]]
=> 148
Yay!
This can be made even cooler: if we had some procedure to turn product into a function [Int] -> Cont Int Int, which basically takes a product of a list and then applies some function to resulting value, we could represent sumSqProd like this:
sumSqProd = (runCont $ sumCont <== sqCont <== (??? product)) idwhere id is a function which returns its argument untouched.
That function ??? (let's call it liftCont) has the type (a -> b) -> a -> Cont r b, so given some function f :: a -> b and an a value it yields a Cont value; and that Cont value essentialy takes a function b -> r and yields r value. Well, we can apply f to a value and send the result into b -> r function - and we are done!
liftCont :: (a -> b) -> a -> Cont r b
liftCont f = \x -> Cont $ \g -> g $ f x> (runCont $ liftCont product [1,2,3]) id
=> 6
Nice.
Now, to make Cont into a monad, we need to supply a return :: a -> Cont r a function and a (>>=) :: Cont r a -> (a -> Cont r b) -> Cont r b operator.
The return function trivially takes a value and returns a continuation, so we don't have much choice about what to do with that value - we can only apply an abstracted computation to it:
retCont :: a -> Cont r a
retCont x = Cont $ \f -> f xThen, the definition of >>= requires us to somehow turn a Cont r a with a -> Cont r b into Cont r b. Turns out, the composition law in associated Kleisli category can do the actual job, provided that we decorate our values appropriately. To do that, it suffices to turn Cont r a into ? -> Cont r a, take composition and then apply the result to some value of type ?. We actually don't care about ? type and its values, so the type () will fill this hole just fine:
fishCont :: Cont r a -> (a -> Cont r b) -> Cont r b
fishCont c f = (\_ -> c) <== f $ ()Boom! Now Cont is a monad.