Saturday, April 19, 2014

How the continuation monad works

I remember the first time I read the Monad instance for ContT I was so confused. I couldn't fathom how it worked because it was hard to discern the pattern.

However, I later discovered that renaming things makes the pattern much more clear:

import Control.Applicative

newtype ContT x m r = ContT { (>>-) :: (r -> m x) -> m x }

instance Functor (ContT x m) where
    fmap f m  = ContT $ \_return ->  -- fmap f m =
        m >>- \a ->                  --     m >>= \a ->
        _return (f a)                --     return (f a)

instance Applicative (ContT x m) where
    pure r    = ContT $ \_return ->  -- pure r =
        _return r                    --     return r

    mf <*> mx = ContT $ \_return ->  -- mf <*> mx =
        mf >>- \f ->                 --     mf >>= \f ->
        mx >>- \x ->                 --     mx >>= \x ->
        _return (f x)                --     return (f x)

instance Monad (ContT x m) where
    return r  = ContT $ \_return ->  -- return r =
        _return r                    --     return r

    m >>= f   = ContT $ \_return ->  -- m >>= f =
        m   >>- \a ->                --     m   >>= \a ->
        f a >>- \b ->                --     f a >>= \b ->
        _return b                    --     return b

7 comments:

  1. I remember that SPJ also showed that adding some omitted function parameters to the both ends of function definition makes lens code much more understandable.
    But right now I'm trying to understand the internals of pipe (yes - you've already provided great documentation and metaphors, but some time is needed digging source coded in order to get them).

    ReplyDelete
    Replies
    1. Thaddeus replied in a top level comment but I will copy his answer here. You can learn a great deal about how pipes works by reading the "Coroutine Pipelines" article of issue 19 of The Monad Reader:

      http://themonadreader.files.wordpress.com/2011/10/issue19.pdf

      Delete
    2. Thank you, Gabriel and Thaddeus.
      Frankly speaking, I thought about reading "How to read Pipes" by Tom Ellis first and looking into pipes 3.2 internals first with a quite simple ProxyF type. But, I'll definitely try to read "Coroutine Pipelines" also.

      Delete
  2. read this to understand pipes: http://themonadreader.files.wordpress.com/2011/10/issue19.pdf

    ReplyDelete
  3. I just wanted to say 'thank you' for this post. Thanks to your definition the continuation monad is crystal clear to me. This have been in one of tutorials. I can guarantee you that more people would be using the continuation monad if they had seen this definition from the start.

    ReplyDelete
  4. Fantastic. Thanks.
    Your statement "I remember the first time I read the Monad instance for ContT I was so confused ..." is the canonical expression for many issues with the Haskell libraries. It is so "confusing" and obfuscated. It does not seem to be an issue with the ones having a mathematical background but for us bare mortals ... Could be a reason for low acceptance in the wider IT community.
    It took me years to overcome this problem. And is still not solved completely. Your way of translating / demonstrating it is of immense help.

    ReplyDelete
  5. I got interested in continuations playing around with some more basic functions. What an interesting pattern. The intuition kind of "clicked" when experimenting with it.

    intCont :: (Int -> r) -> r
    intCont f = f 2

    strCont :: (String -> r) -> r
    strCont f = f "hello"

    p2Cont :: (Int -> Int -> r) -> r
    p2Cont f = f 2 8

    contCont :: ((Int, String) -> r) -> r
    contCont f =
    intCont $ \int ->
    strCont $ \str ->
    p2Cont $ \i1 i2 ->
    f (int + i1 + i2, str)

    eval :: (forall a r.(a -> r) -> r) -> a
    eval f = f id

    ReplyDelete