Revision as of 00:23, 20 January 2012
1 A practical Cont tutorial
It seems to me like
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.
contstuff :: Magic a
contstuff = do
-- 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.
thing3 -- these might get done once, several times,
thing4 -- or not at all.
The question is, what type should
have? Well, let's say the whole do-block results in a thing of type
(without thinking too hard about what this means). Then certainly the function we give
should result in type
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
, right? Well, more or less, with one caveat: we might bind the result of
x <- magic $ \rest -> -- ...
so the rest of the do-block has an
in it that we need to supply (as well as other variables, but
already has access to those). So the rest of the do-block can be thought of as a bit like
. Given access to the rest of that do-block, we need to produce something of type
. So our lambda has type
magic :: (a -> r) -> r -> Magic a
... oh but this
type Magic a = Cont r a
magic = Cont
The thing with
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
without thinking about the types too much:
instance Functor (Cont r) where
fmap f (Cont g) = -- ...
Well, we've got to build a
value, and those always start the same way:
fmap f (Cont g) = Cont $ \rest -> -- ...
Now what? Well, remember what
is. It looks like
\rest -> stuffWith (rest val)
is the 'value' of the computation (what would be bound with
). So we want to give it a
, but we don't want it to be called with the 'value' of the computation - we want
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
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 -> -- ...
This is a little trickier, but if we look at how we did
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)))
is a harder challenge, but the same basic tactic applies. Hint: remember to unwrap the newtype with
1.1 So what's callCC?
"Call with current continuation". I don't really get the name. Basically, you use
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
throws stuff away, and remember to use
or similar, as before.
1.2 What about ContT?
The thing to understand with
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 make the kind compatible with things like
1.3 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:
-- 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
statement is run with
: if it succeeds then we subtract 10 from the result and return it. If it fails we try again, but with
: note that if this succeeds, we don't subtract 10.
As an exercise, work out how to make the function return (a)
I think it was the legendary sigfpe who made this click for me, after thinking about how this works:
and there's also this:
which is more-or-less the above trick but in a bit more detail.
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 –
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
type class instances before, and the types ensure that you pretty much 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
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.