# MonadCont under the hood

### From HaskellWiki

(Initial import and edits from StackOverflow.) |
m |
||

Line 7: | Line 7: | ||

Continuations are functions that represent "the remaining computation to do." Their representation here is <hask>a -> r</hask>, which is simply a function that takes some value produced by the current computation, of some type <hask>a</hask>, and returns the final result of type <hask>r</hask> from it. | Continuations are functions that represent "the remaining computation to do." Their representation here is <hask>a -> r</hask>, which is simply a function that takes some value produced by the current computation, of some type <hask>a</hask>, and returns the final result of type <hask>r</hask> from it. | ||

− | The type <hask>Cont r a</hask> (instances of which I will, in this tutorial, refer to as '' | + | The type <hask>Cont r a</hask> (instances of which I will, in this tutorial, refer to as <tt>Cont</tt>'' 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: |

1. takes a continuation as an argument | 1. takes a continuation as an argument | ||

Line 17: | Line 17: | ||

=Sequencing Continuation-Style Computations= | =Sequencing Continuation-Style Computations= | ||

==Applicative Sequencing== | ==Applicative Sequencing== | ||

− | <hask>Cont</hask> objects can be chained together, so that the continuation you pass in threads through the guts of all the <hask>Cont</hask> objects in the chain before it's finally invoked. The way they chain is the way <hask>Cont</hask> works: each object in the chain invokes a continuation that ''has the next object's computation prepended to the final continuation''. Let's say we have a chain of <hask>Cont</hask> objects <hask>F1 -> F2 ->F3</hask>, and let's say you had a continuation <hask>C3</hask> that you want to pass to the chain. Then: | + | <hask>Cont</hask> objects can be chained together, so that the continuation you pass in threads through the guts of all the <hask>Cont</hask> objects in the chain before it's finally invoked. The way they chain is the way <hask>Cont</hask> works: each object in the chain invokes a continuation that ''has the next object's computation prepended to the final continuation''. Let's say we have a chain of <hask>Cont</hask> objects <hask>F1 -> F2 -> F3</hask>, and let's say you had a continuation <hask>C3</hask> that you want to pass to the chain. Then: |

* <hask>F3</hask> needs to invoke <hask>C3</hask>when it's done | * <hask>F3</hask> needs to invoke <hask>C3</hask>when it's done | ||

Line 188: | Line 188: | ||

[[Category:Monad]] | [[Category:Monad]] | ||

− | [[Category: | + | [[Category:Tutorials]] |

## Revision as of 02:38, 24 July 2010

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

This tutorial assumes a working knowledge of Haskell, though of course it doesn't assume that you understood the implementation of## Contents |

# 1 Continuations and the Cont monad

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:

1. takes a continuation as an argument 2. does whatever it needs to do

3. produces a value of type# 2 Sequencing Continuation-Style Computations

## 2.1 Applicative 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 doneC3
- needs to invoke a continuationF2that will invokeC2F3
- needs to invoke a continuationF1that will invokeC1, thenF2, thenF3.C3

## 2.2 Extending to Monad

With the*which*

- takes a value and produces areturnobject that just passes that value to its continuation.Cont
- takes abindobject, 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

# 3 Understanding the Monad

## 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

## 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)

# 4 Applying the Monad

Here's a simple example I've cooked up 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:*

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!

# 5 Understanding MonadCont and callCC

One final extension to this which is frequently used is the*second*continuation to that function 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