# MonadCont under the hood

### From HaskellWiki

m (→Return) |
|||

(2 intermediate revisions by one user not shown) | |||

Line 52: | Line 52: | ||

Thus, <hask>return</hask> in the <hask>Cont</hask> monad passes the result of its computation directly to the continuation it's given. | Thus, <hask>return</hask> in the <hask>Cont</hask> monad passes the result of its computation directly to the continuation it's given. | ||

+ | |||

+ | A mathematical analogon that may help is the "insert a" functional: it takes a function f, and the result is the value f(a) of that function at x=a. Call it "insert(a)", then | ||

+ | <haskell> | ||

+ | insert(a) <---> return a | ||

+ | insert(a)(f(x) = x^2) <---> runCont (return a) (\x -> x^2) | ||

+ | == f(a) == (\x -> x^2) a | ||

+ | == a^2 == a^2 | ||

+ | </haskell> | ||

==Bind== | ==Bind== | ||

Line 63: | Line 71: | ||

<haskell> | <haskell> | ||

− | + | m >>= k = let s c = runCont m c | |

− | + | t c = \a -> runCont (k a) c | |

− | + | in Cont $ \c -> s (t c) | |

</haskell> | </haskell> | ||

## Latest revision as of 23:02, 4 December 2012

This tutorial is a response to the following Stack Overflow question. There's a short but useful description of `Cont` and `MonadCont` operations in the Control.Monad.Cont documentation, but it doesn't really describe how the continuation monad does its thing. This is an attempt at much more detailed explanation of what Cont and MonadCont are doing under the hood.

## Contents |

# [edit] 1 Introducing Continuations and the Cont type

Continuations are functions that represent "the remaining computation to do." Their representation here is`Cont`

*objects*) represents a

*continuation-passing-style function that takes a single continuation as its only input*. In other words, its guts are a function that:

- takes a continuation as an argument
- does whatever it needs to do
- produces a value of type at the end, presumably by invoking the continuation.r

# [edit] 2 Sequencing Continuation-Style Computations

## [edit] 2.1 Basic Sequencing

*has the next object's computation prepended to the final continuation*. Let's say we have a chain of

- needs to invokef3when it's done.c3
- needs to invoke a continuationf2that will invokec2, which will invokef3.c3
- needs to invoke a continuationf1,c1

which will invoke,f2

which will invoke,c2

which will invoke,f3

which will finally invoke.c3

## [edit] 2.2 Extending to Monad

Extending this idea to the*which*

- takes a value and produces areturnobject that just passes that value to its continuation.Cont
- The bind operator takes a(>>=)object, and aCont
*function that produces another*, and chains them together into oneobject given a value from the firstContobject. That object, when invoked, is going to:Cont- take a single continuation object ,C
- produce an intermediate value,
- use that intermediate value to select/create the next object to invoke,Cont
- invoke that object withContC

- take a single continuation object

# [edit] 3 Understanding the Monad

## [edit] 3.1 Return

The code:

return a = Cont ($ a)

is equivalent to the following code:

return a = Cont $ \c -> c a

*slice*of the operator

A mathematical analogon that may help is the "insert a" functional: it takes a function f, and the result is the value f(a) of that function at x=a. Call it "insert(a)", then

insert(a) <---> return a insert(a)(f(x) = x^2) <---> runCont (return a) (\x -> x^2) == f(a) == (\x -> x^2) a == a^2 == a^2

## [edit] 3.2 Bind

The code:

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

is a terse way of saying the following:

m >>= k = let s c = runCont m c t c = \a -> runCont (k a) c in Cont $ \c -> s (t c)

# [edit] 4 Exploring the Monad

Here's a simple example that should help illustrate the monad in action:

f :: Int -> Cont r Int f x = Cont $ \c -> c (x * 3) g :: Int -> Cont r Int g x = Cont $ \c -> c (x - 2)

BTW, they can be equivalently written as:

f x = return (x * 3) g x = return (x - 2)

where they look very similar to normal functions. I'm writing them longhand to show you explicitly what the functions are doing.

h :: Int -> Cont r Int h x | x == 5 = f x | otherwise = g x

doC :: Cont r Int doC = return 5 >>= h

And we'll invoke it like this:

finalC :: Show a => a -> String finalC x = "Done: " ++ show(x) runCont doC finalC

Let's see if you're right:

*Lemma:*The sequence of terms

doC = let s c = c 5 t c = \a -> runCont (h a) c in Cont $ \c -> s (t c)

runCont doC finalC => runCont (Cont $ \c -> s (t c)) finalC -- unfold doC => s (t finalC) -- simplify with lemma and apply to finalC => (t finalC) 5 -- unfold s => (\a -> runCont (h a) finalC) 5 -- unfold t => runCont (h 5) finalC -- apply \a... to 5 => runCont (f 5) finalC -- unfold h => runCont (Cont $ \c -> c (5*3)) finalC -- unfold f => (\c -> c (5*3)) finalC -- simplify with lemma => finalC (5*3) -- apply \c... to finalC => "Done: 15" -- apply *; apply finalC to final value!If you changed doC to

# [edit] 5 MonadCont and callCC

One final extension to this monad, which can be extremely useful in practice, is the*alternate*continuation that can be invoked to "break out" of the computation and simply pass a value to the continuation that was active when

h :: Int -> (Int -> Cont r Int) -> Cont r Int h x abort | x == 5 = f x | otherwise = abort (-1) doC n = return n >>= \x -> callCC (\abort -> h x abort) >>= \y -> g y

doC n = return n >>= \x -> callCC (\abort -> h x abort >>= \y -> g y)

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

can be written as

callCC f = let backtrack a = Cont $ \_ -> c a in Cont $ \c -> runCont (f backtrack) c