# User:Benmachine/Cont

### From HaskellWiki

< User:Benmachine(Difference between revisions)

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

Line 1: | Line 1: | ||

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

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

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

+ | </haskell> | ||

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

− | + | ||

+ | <haskell> | ||

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

+ | thingInvolving x | ||

</haskell> | </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> | |

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

− | |||

<haskell> | <haskell> | ||

− | + | instance Functor (Cont r) where | |

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