Personal tools

User:Benmachine/Cont

From HaskellWiki

< User:Benmachine(Difference between revisions)
Jump to: navigation, search
Line 1: Line 1:
When you do this: <hask>{-</hask>, terrible things happen.
+
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.
   
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 like
Cont
and
ContT
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:
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
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 a
Magic a = Cont r a
magic = Cont

Tada!

The thing with
Cont
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
Functor
without thinking about the types too much:
instance Functor (Cont r) where
  fmap f (Cont g) = -- ...
Well, we've got to build a
Cont
value, and those always start the same way:
  fmap f (Cont g) = Cont $ \rest -> -- ...
Now what? Well, remember what
g
is. 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 g) = Cont $ \rest -> g (\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
. The latter two might be easier.

What about ContT?

The thing with
ContT
is that it's literally exactly the same trick. In fact 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 make the kind compatible with things like
MonadTrans
.