User:Benmachine/Cont

From HaskellWiki

< User:Benmachine(Difference between revisions)

Current revision

1 A practical Cont tutorial

1 A practical Cont tutorial

It seems to me like

Cont

and

ContT

is way simpler than people make it. I think it's just a way to give a name to the "tail" of a do-block.

Warning: I'm going to use some metaphors here, like the Magic type, that probably shouldn't be interpreted perfectly literally. Try to understand the gist, rather than worrying about the details.

contstuff :: Magic
contstuff = do
  thing1
  thing2
  -- Now I want to manipulate the rest of the computation.
  -- So I want a magic function that will give me the future to
  -- play with.
  magic $ \rest ->
    -- 'rest' is the rest of the computation. Now I can just do it,
    -- or do it twice and combine the results, or discard it entirely,
    -- or do it and then use the result to do it again... it's easy to
    -- imagine why this might be useful.
    messAboutWith rest
 
  thing3 -- these might get done once, several times,
  thing4 -- or not at all.

The question is, what type should

magic

have? Well, let's say the whole do-block results in a thing of type

r

(without thinking too hard about what this means). Then certainly the function we give

magic

should result in type

r

as well, since it can run that do-block. The function should also accept a single parameter, referring to the tail of the computation. That's the rest of the do-block, which has type

r

, right? Well, more or less, with one caveat: we might bind the result of

magic

x <- magic $ \rest -> -- ...
  thingInvolving x

so the rest of the do-block has an

x

in it that we need to supply (as well as other variables, but

magic

already has access to those). So the rest of the do-block can be thought of as a bit like

a -> r

. Given access to the rest of that do-block, we need to produce something of type

r

. So our lambda has type

(a -> r) -> r

and hence

magic :: (a -> r) -> r -> Magic

... oh but this looks familiar...

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

Tada! The moral of the story is, if you got up one morning and said to yourself "I want to stop in the middle of a do-block and play about with the last half of it", then Cont is the type you would have come up with.

Now you know what the Cont type is, you can implement pretty much all of its type class instances just from there, since the types force you to apply this to that and compose that with this. But that doesn't really help you to understand what's going on: here's a way of using the intuition introduced above to implement `Functor` without thinking about the types too much:

instance Functor (Cont r) where
  fmap f (Cont x) = -- ...

Well, we've got to build a

Cont

value, and those always start the same way:

fmap f (Cont x) = Cont $ \rest -> -- ...

Now what? Well, remember what

x

is. It comes from inside a

Cont

, so it looks like

\rest -> stuffWith (rest val)

, where

val

is the 'value' of the computation (what would be bound with

<-

). So we want to give it a

rest

, but we don't want it to be called with the 'value' of the computation - we want

f

to be applied to it first. Well, that's easy:

fmap f (Cont x) = Cont $ \rest -> x (\val -> rest (f val))

Load it in `ghci` and the types check. Amazing! Emboldened, let's try

Applicative

instance Applicative (Cont r) where
  pure x = Cont $ \rest -> -- ...

We don't want to do anything special here. The rest of the computation wants a value, let's just give it one:

pure x = Cont $ \rest -> rest x

What about

<*>

Cont f <*> Cont x = Cont $ \rest -> -- ...

This is a little trickier, but if we look at how we did

fmap

we can guess at how we get the function and the value out to apply one to the other:

Cont f <*> Cont x = Cont $ \rest -> f (\fn -> x (\val -> rest (fn val)))

Monad

is a harder challenge, but the same basic tactic applies. Hint: remember to unwrap the newtype with

runCont

case

, or

let

when necessary.

1.1 So what's callCC?

"Call with current continuation". Basically, you use

callCC

like this:

ret <- callCC $ \exit -> do
    -- A mini Cont block.
    -- You can bind things to ret in one of two ways: either return
    -- something at the end as usual, or call exit with something of
    -- the appropriate type, and the rest of the block will be ignored.
    when (n < 10) $ exit "small!"
    when (n > 100) $ exit "big!"
    return "somewhere in between!"

See if you can work out the type (not too hard: work out the type of exit first, then the do block) then the implementation. Try not to follow the types too much: they will tell you what to write, but not why. Think instead about the strategies we used above, and what each bit means. Hints: remember that

exit

throws stuff away, and remember to use

runCont

or similar, as before.

1.2 What about ContT?

The thing to understand with

ContT

is that it's exactly the same trick. Literally. To the point where I think the following definition works fine:

newtype ContT r m a = ContT (Cont (m r) a)
  deriving (Functor, Applicative, Monad)
 
runContT :: ContT r m a -> (a -> m r) -> m r
runContT (ContT m) = runCont m

The only reason the newtype exists at all is to shuffle the type parameters around a bit, so that instances of things like

MonadTrans

can be defined.

1.3 Some real examples

I find he examples in the mtl doc unconvincing. They don't do anything genuinely daring, and some of them don't use the features of Cont at all – they work in any monad! Here's a more complex example:

-- This tends to be useful.
runC :: Cont a a -> a
runC c = runCont c id
 
faff :: Integer -> Maybe Integer
faff n = runC $ do
  test <- Cont $ \try -> case try n of 
    Nothing -> try (2*n) 
    res -> fmap (subtract 10) res
  return $ if test < 10 then Nothing else Just test

faff

, the

return

statement is run with

test = n

: if it succeeds then we subtract 10 from the result and return it. If it fails we try again, but with

(2*n)

: note that if this succeeds, we don't subtract 10.

As an exercise, see if you can work out, without using ghci, how to make the function return: (a) Nothing, (b) Just 12, (c) Just 0.

1.4 Acknowledgements

I think it was the legendary sigfpe who made this click for me, after thinking about how this works:

Quick and dirty reinversion of control

and there's also this:

The Mother of all Monads

which is more-or-less the above trick but in a bit more detail.

1.5 Disclaimer

I'm currently unsure if I've fallen victim to Brent's (in)famous monad tutorial fallacy. I know that there was more in my learning process than I've been able to reproduce above, but I do think I'm doing this in a genuinely new style –

Cont

always seems to be presented in such vague terms, and people don't provide actual examples of the way it works.

1.6 A moderately heretical conclusion

Sometimes looking at types isn't the best way to understand things! I've implemented the

Cont

type class instances before, and the types ensure that you pretty much can't help but do it the right way. But that doesn't tell you what you're doing, or why you did it that way. I never understood

Cont

until I came across the natural interpretation of its content. It's a bit like fitting the pieces of a puzzle together without looking at the picture.

Retrieved from "http://www.haskell.org/haskellwiki/User:Benmachine/Cont"

@@ Line 1: / Line 1: @@
-I found a [[User:benmachine/hasktag_bug|bug with the &lt;hask&gt; tag]]. I put it on its own page so it doesn't ruin my user page.
 == A practical Cont tutorial ==
 It seems to me like <hask>Cont</hask> and <hask>ContT</hask> is way simpler than people make it. I think it's just a way to give a name to the "tail" of a do-block.
+'''Warning:''' I'm going to use some metaphors here, like the <tt>Magic</tt> type, that probably shouldn't be interpreted perfectly literally. Try to understand the gist, rather than worrying about the details.
 <haskell>
-contstuff :: Magic a
+contstuff :: Magic
 contstuff = do
   thing1
@@ Line 31: / Line 31: @@
 </haskell>
-so the rest of the do-block has an <hask>x</hask> in it that we need to supply (as well as other variables, but <hask>magic</hask> already has access to those). So the rest of the do-block can be thought of as a bit like <hask>a -> r</hask>. Given access to the rest of that do-block, we need to produce something of type <hask>r</hask>. So our lambda has type <hask>(a -> r) -> r</hask> and hence <hask>magic :: (a -> r) -> r -> Magic a</hask>
+so the rest of the do-block has an <hask>x</hask> in it that we need to supply (as well as other variables, but <hask>magic</hask> already has access to those). So the rest of the do-block can be thought of as a bit like <hask>a -> r</hask>. Given access to the rest of that do-block, we need to produce something of type <hask>r</hask>. So our lambda has type <hask>(a -> r) -> r</hask> and hence <hask>magic :: (a -> r) -> r -> Magic</hask>... oh but ''this'' looks familiar...
 <haskell>
-Magic a = Cont r a
+newtype Cont r a = Cont { runCont :: (a -> r) -> r }
+-- Magic = Cont r a
 magic = Cont
 </haskell>
+Tada! The moral of the story is, if you got up one morning and said to yourself "I want to stop in the middle of a do-block and play about with the last half of it", then <tt>Cont</tt> is the type you would have come up with.
-Tada!
+----
-The thing with <hask>Cont</hask> is I could implement it way before I understood it, because the types have really only one implementation, but here's a way of using the intuition above to implement <hask>Functor</hask> without thinking about the types too much:
+Now you know what the <tt>Cont</tt> type is, you can implement pretty much all of its type class instances just from there, since the types force you to apply this to that and compose that with this. But that doesn't really help you to understand what's going on: here's a way of using the intuition introduced above to implement `Functor` without thinking about the types too much:
 <haskell>
 instance Functor (Cont r) where
-  fmap f (Cont g) = -- ...
+  fmap f (Cont x) = -- ...
 </haskell>
 Well, we've got to build a <hask>Cont</hask> value, and those always start the same way:
 <haskell>
-  fmap f (Cont g) = Cont $ \rest -> -- ...
+  fmap f (Cont x) = Cont $ \rest -> -- ...
 </haskell>
-Now what? Well, remember what <hask>g</hask> is. It looks like <hask>\rest -> stuffWith (rest val)</hask>, where <hask>val</hask> is the 'value' of the computation (what would be bound with <hask><-</hask>). So we want to give it a <hask>rest</hask>, but we don't want it to be called with the 'value' of the computation - we want <hask>f</hask> to be applied to it first. Well, that's easy:
+Now what? Well, remember what <hask>x</hask> is. It comes from inside a <hask>Cont</hask>, so it looks like <hask>\rest -> stuffWith (rest val)</hask>, where <hask>val</hask> is the 'value' of the computation (what would be bound with <hask><-</hask>). So we want to give it a <hask>rest</hask>, but we don't want it to be called with the 'value' of the computation - we want <hask>f</hask> to be applied to it first. Well, that's easy:
 <haskell>
   fmap f (Cont x) = Cont $ \rest -> x (\val -> rest (f val))
@@ Line 84: / Line 86: @@
 === So what's callCC? ===
-"Call with current continuation". I don't really get the name. Basically, you use <hask>callCC</hask> like this:
+"Call with current continuation". Basically, you use <hask>callCC</hask> like this:
 <haskell>
@@ Line 101: / Line 103: @@
 === What about ContT? ===
-The thing with <hask>ContT</hask> is that it's literally exactly the same trick. In fact I ''think'' the following definition works fine:
+The thing to understand with <hask>ContT</hask> is that it's exactly the same trick. Literally. To the point where I ''think'' the following definition works fine:
 <haskell>
@@ Line 111: / Line 113: @@
 </haskell>
-The only reason the newtype exists at all is to make the kind compatible with things like <hask>MonadTrans</hask>.
+The only reason the newtype exists at all is to shuffle the type parameters around a bit, so that instances of things like <hask>MonadTrans</hask> can be defined.
 === Some real examples ===
-The examples in the mtl doc are unconvincing. They don't do anything genuinely daring. Some of them work in any monad! Here's a more complex example:
+I find he examples in the mtl doc unconvincing. They don't do anything genuinely daring, and some of them don't use the features of <tt>Cont</tt> at all – they work in any monad! Here's a more complex example:
 <haskell>
@@ Line 130: / Line 132: @@
 </haskell>
-The <hask>return</hask> statement is run with <hask>test = n</hask>: if it succeeds then we subtract 10 from the result and return it. If it fails we try again, but with <hask>(2*n)</hask>: note that if this succeeds, we don't subtract 10.
+In <hask>faff</hask>, the <hask>return</hask> statement is run with <hask>test = n</hask>: if it succeeds then we subtract 10 from the result and return it. If it fails we try again, but with <hask>(2*n)</hask>: note that if this succeeds, we don't subtract 10.
-As an exercise, work out how to make the function return (a) <hask>Nothing</hask>, (b) <hask>Just 12</hask>, (c) <hask>Just 0</hask>.
+As an exercise, see if you can work out, without using <tt>ghci</tt>, how to make the function return: (a) <tt>Nothing</tt>, (b) <tt>Just 12</tt>, (c) <tt>Just 0</tt>.
 === Acknowledgements ===
-I think it was sigfpe who made this click for me, after thinking about how this works: [http://blog.sigfpe.com/2011/10/quick-and-dirty-reinversion-of-control.html Quick and dirty reinversion of control]
+I think it was [http://blog.sigfpe.com/ the legendary sigfpe] who made this click for me, after thinking about how this works:
-and there's also this: [http://blog.sigfpe.com/2008/12/mother-of-all-monads.html The Mother of all Monads] which is more-or-less the above trick but in a bit more detail.
+* [http://blog.sigfpe.com/2011/10/quick-and-dirty-reinversion-of-control.html Quick and dirty reinversion of control]
+and there's also this:
+* [http://blog.sigfpe.com/2008/12/mother-of-all-monads.html The Mother of all Monads]
+which is more-or-less the above trick but in a bit more detail.
+=== Disclaimer ===
+I'm currently unsure if I've fallen victim to Brent's (in)famous [http://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/ monad tutorial fallacy]. I know that there was more in my learning process than I've been able to reproduce above, but I do think I'm doing this in a genuinely new style – <hask>Cont</hask> always seems to be presented in such vague terms, and people don't provide actual examples of the way it works.
+=== A moderately heretical conclusion ===
+Sometimes looking at types isn't the best way to understand things! I've implemented the <hask>Cont</hask> type class instances before, and the types ensure that you pretty much can't help but do it the right way. But that doesn't tell you what you're doing, or why you did it that way. I never understood <hask>Cont</hask> until I came across the natural interpretation of its content. It's a bit like fitting the pieces of a puzzle together without looking at the picture.

Personal tools

Views