Search code examples
haskellmonadsabstraction

Continuation abstraction

In a general exercise about concurrency based on this article.

We have:

-- a is the result type on which after we continue
type Continuation a = a-> Action

type ContinuationPseudoMonad a = Continuation a -> Action
-- pseudoMonad because it will need Concurrent wrapper Monad:
-- so as to define bind operation and return operation on it

data Concurrent a = Concurrent (ContinuationPseudoMonad a)

so Concurrent a is a monad we have to implement with its two mandatory laws, return and bind.

Unfortunatly, I find no adequate words for defining more precisely the ContinuationPseudoMonad thing... and if I lack words, I lack abstraction in my mind.

How would you call it ?

Is there a word meaning Continuation a -> Action instead of my awkward meaningless ContinuationPseudoMonad ?

Action being:

data Action = Atom (IO Action)
            | Fork Action Action
            | Stop
Solution

  • It is evident Concurrent a is the same as Cont Action a where Cont is the continuation monad. Here's a simple explanation for continuations:

    1. Consider the function f :: a -> b for some arbitrary types a and b. We want to convert this function into continuation passing style. How do we do so?
    2. Let's say we have a continuation k :: b -> r which takes the return value of f as an input and itself returns a value of an arbitrary type r. Following this, we can convert f to CPS.
    3. Let g :: a -> (b -> r) -> r be the CPS version function of f. Note that it takes an additional argument (i.e. the continuation k) and returns the result of k applied to its output b.

    Let's take a practical example where f is the predicate function odd :: Int -> Bool:

    odd :: Int -> Bool
odd n = n `mod` 2 == 1

    Here's the same function written in continuation passing style:

    odd' :: Int -> (Bool -> r) -> r
odd' n k = k (n `mod` 2 == 1)

    The (Bool -> r) -> r part can be abstracted out as the continuation monad:

    data Cont r a = Cont { runCont :: (a -> r) -> r }

odd' :: Int -> Cont r Bool
odd' n = return (n `mod` 2 == 1)

instance Monad (Cont r) where
    return a = Cont (\k -> k a)
    m  >>= f = Cont (\k -> runCont m (\a -> runCont (f a) k))

    Notice that the type of the continuation k is Bool -> r for some arbitrary type r. Hence, the continuation k could be any function which takes a Bool as an argument. For example:

    cont :: Bool -> IO ()
cont = print

main :: IO ()
main = odd' 21 cont

    However, in the case of Concurrent this r is not arbitrary. It has been specialized to Action. In fact, we can define Concurrent as a type synonym for Cont Action as follows:

    type Concurrent = Cont Action

    Now, we don't need to implement the Monad instance for Concurrent because it's the same as the Monad instance for Cont r as defined above.

    runConcurrent :: Concurrent a -> ContinuationPseudoMonad a
runConcurrent (Concurrent g) = g

instance Monad Concurrent where
    return a = Concurrent (\k -> k a)
    m  >>= f = Concurrent (\k -> runConcurrent m (\a -> runConcurrent (f a) k))

    Note that nowhere in the definition of instance Monad Concurrent have we made use of Action. That's because Concurrent = Cont Action and the monad instance of Cont r uses r transparently.