# User:Benmachine/Cont

### From HaskellWiki

< User:Benmachine(Difference between revisions)

Benmachine (Talk | contribs) |
Benmachine (Talk | contribs) |
||

Line 1: | Line 1: | ||

− | When you do this: <hask>{-</hask>, terrible things happen. |
+ | I found a [[User:benmachine/hasktag_bug|bug with the <hask> tag]]. I put it on its own page so it doesn't ruin my user page. |

− | Here's some nicely-formatted code: |
+ | It seems to me like <hask>Cont</hask> and <hask>ContT</hask> is way simpler than people make it. Essentially what it seems to be is the ability to give a name to the tail of a do-block. Consider this: |

<haskell> |
<haskell> |
||

− | id :: a -> a |
+ | contstuff :: Magic a |

− | id x = const x x |
+ | contstuff = do |

+ | thing1 |
||

+ | thing2 |
||

+ | -- Here I want to manipulate the rest of the computation. |
||

+ | -- So I want a magic function that will give me the rest of it to |
||

+ | -- play with. |
||

+ | magic $ \rest -> |
||

+ | -- Now I can just do it (tm), or do it twice, or discard it, or |
||

+ | -- do it and then use the result to do it again... it's easy to |
||

+ | -- imagine why this might be useful. |
||

+ | thing3 |
||

+ | </haskell> |
||

− | const :: a -> b -> a |
+ | The question is, what type should <hask>magic</hask> have? Well, let's say the whole do-block results in a thing of type <hask>r</hask> (without thinking too hard about what this means). Then certainly the function we give <hask>magic</hask> should result in type <hask>r</hask> 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 <hask>r</hask>, right? Well, more or less, with one caveat: we might bind the result of <hask>magic</hask>: |

− | const x _ = id x |
+ | |

+ | <haskell> |
||

+ | x <- magic $ \rest -> -- ... |
||

+ | thingInvolving x |
||

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

− | which is now ruined. <hask>-}</hask> does that fix it? It doesn't seem to. |
+ | 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> |

− | == The problem == |
+ | <haskell> |

+ | Magic a = Cont r a |
||

+ | magic = Cont |
||

+ | </haskell> |
||

+ | |||

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

− | doesn't even stop at section boundaries: |
||

<haskell> |
<haskell> |
||

− | error :: String -> a |
+ | instance Functor (Cont r) where |

− | error str = error (error str) |
+ | fmap f (Cont g) = -- ... |

+ | </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 -> -- ... |
||

+ | </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: |
||

+ | <haskell> |
||

+ | fmap f (Cont g) = Cont $ \rest -> g (\val -> rest (f val)) |
||

+ | </haskell> |
||

+ | |||

+ | Load it in `ghci` and the types check. Amazing! Emboldened, let's try <hask>Applicative</hask> |
||

+ | |||

+ | <haskell> |
||

+ | instance Applicative (Cont r) where |
||

+ | pure x = Cont $ \rest -> -- ... |
||

+ | </haskell> |
||

+ | |||

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

+ | |||

+ | <haskell> |
||

+ | pure x = Cont $ \rest -> rest x |
||

+ | </haskell> |
||

+ | |||

+ | What about <hask><*></hask>? |
||

+ | |||

+ | <haskell> |
||

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

+ | </haskell> |
||

+ | |||

+ | This is a little trickier, but if we look at how we did <hask>fmap</hask> we can guess at how we get the function and the value out to apply one to the other: |
||

+ | |||

+ | <haskell> |
||

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

+ | </haskell> |
||

+ | |||

+ | <hask>Monad</hask> is a harder challenge, but the same basic tactic applies. Hint: remember to unwrap the newtype with <hask>runCont</hask>, <hask>case</hask>, or <hask>let</hask>. The latter two might be easier. |
||

+ | |||

+ | === 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: |
||

+ | |||

+ | <haskell> |
||

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

+ | </haskell> |
||

+ | |||

+ | The only reason the newtype exists at all is to make the kind compatible with things like <hask>MonadTrans</hask>. |

## Revision as of 22:23, 19 January 2012

I found a bug with the <hask> tag. I put it on its own page so it doesn't ruin my user page.

It seems to me likeCont

ContT

contstuff :: Magic a contstuff = do thing1 thing2 -- Here I want to manipulate the rest of the computation. -- So I want a magic function that will give me the rest of it to -- play with. magic $ \rest -> -- Now I can just do it (tm), or do it twice, or discard it, or -- do it and then use the result to do it again... it's easy to -- imagine why this might be useful. thing3

magic

r

magic

r

r

magic

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

x

magic

a -> r

r

(a -> r) -> r

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

Magic a = Cont r a magic = Cont

Tada!

The thing withCont

Functor

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

Cont

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

g

\rest -> stuffWith (rest val)

val

<-

rest

f

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

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

<*>

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

fmap

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

Monad

runCont

case

let

### What about ContT?

The thing withContT

*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

MonadTrans