Continuations in Haskell

The purpose of this text is to guide a reader through the first step towards [grokking](http://www.dictionary.com/browse/grokking) continuations as presented in Haskell (`callCC` not covered). The reader is assumed to have basic knowledge of Haskell including some understanding of monads.

### Abstracting away computations
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:
1. Take product of each list of integers and thus form a new list of integers.
2. In that list, square every integer, again forming a new list of integers.
3. 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:
```haskell
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:

```haskell
sumWhatever :: [[Int]] -> ([Int] -> Int) -> Int
sumWhatever xss = \f -> sum $ map f xss
```

That'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:

```haskell
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:
```haskell
sqWhatever :: [Int] -> ([Int] -> Int) -> Int
sqWhatever xs = \f -> square $ f xs
                where square x = x * x
```

Now that's a pattern. In fact, this pattern is exactly what we call a continuation.

### Continuations defined

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:
```haskell
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.

### Continuations composed

You've probably heard about [categories](https://en.wikipedia.org/wiki/Category_theory) 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`.

```haskell
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 notation
```

Constructing 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:

```haskell
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) h
```

Now let's see if it actually works:

```haskell
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:
```haskell
sumSqProd = (runCont $ sumCont <== sqCont <== (??? product)) id
```
where `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!

```haskell
liftCont :: (a -> b) -> a -> Cont r b
liftCont f = \x -> Cont $ \g -> g $ f x
```

> > (runCont $ liftCont product [1,2,3]) id
> => 6

Nice.


### Continuation monad

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:
```haskell
retCont :: a -> Cont r a
retCont x = Cont $ \f -> f x
```

Then, 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:

```haskell
fishCont :: Cont r a -> (a -> Cont r b) -> Cont r b
fishCont c f = (\_ -> c) <== f $ ()
```

Boom! Now `Cont` is a monad.