»
S
I
D
E
B
A
R
«
Co-routines in Haskell
July 21st, 2010 by blackh

It is easy to implement co-routines in Haskell… but only if you know how. No fewer than three people asked me to blog about it, so here’s a quick guide to rolling your own co-routines. To understand this blog, you will need to have a basic understanding of monad transformers.

There are co-routine packages on Hackage, but I have not had much luck with them. The point here, really, is to show you how it all works.

What’s a co-routine?

A co-routine (called a ‘generator’ in Python) is where you create two interleaved flows of control on a single thread. Unlike threads, co-routines switch co-operatively using a ‘yield’ operation. (This is quite a good trick in GUI programming for implementing complex workflow that spans multiple GUI events, since most GUI libraries require everything to be on one thread.)

The example I’m presenting here works in this way: A caller executes a CoroutineT monad transformer, which adds the ‘yield’ operation to the underlying monad (which can be anything). From the caller’s point of view, the ‘yield’ looks like the monad has returned, but with a continuation. In the callee, ‘yield’ appears to block until the caller executes the continuation. In addition, we add the ability to pass a value in both directions.

So we’ve inverted the flow of control in the callee. Continuation passing style (CPS) can also do this, but co-routines are better than CPS because 1. it’s a bit neater, and 2. it allows for recursion.

One application of co-routines is to separate I/O from logic. By way of example I am going to implement an expert system for identifying fruit. I try not to use contrived examples, and as you can see, this time I have completely failed.

In this example, the CoroutineT sits on top of the identity monad, so it’s pure, but the approach works just the same on top of IO or anything else. This example is not deeply nested, but this approach happily supports any level of recursion or nesting.

So here’s our expert system logic. We’ll define CoroutineT shortly. You can read ‘yield’ as ‘askUser’:

type Question = String
data Answer = Y | N deriving Eq
type Expert a = CoroutineT Answer Question Identity a
data Fruit
    = Apple
    | Kiwifruit
    | Banana
    | Orange
    | Lemon
    deriving Show
identifyFruit :: Expert Fruit
identifyFruit = do
    yellow <- yield "Is it yellow?"
    if yellow == Y then do
        long <- yield "Is it long?"
        if long == Y then
            return Banana
          else
            return Lemon
      else do
        orange <- yield "Is it orange?"
        if orange == Y then
           return Orange
         else do
           fuzzy <- yield "Is it fuzzy?"
           if fuzzy == Y then
               return Kiwifruit
             else
               return Apple

Our ‘Expert’ type above…

type Expert a = CoroutineT Answer Question Identity a

…specifies the type we are sending into our co-routine (Answer) and the type we are getting out of it (Question) as viewed from the caller.

Now we just need a main program to drive it. Because the I/O is separated out, we can later replace this with a nice touch-screen GUI for the seriously fruit-impaired.

main :: IO ()
main = do
    putStrLn $ "Expert system for identifying fruit"
    run identifyFruit
  where
    run :: Expert Fruit -> IO ()
    run exp = handle $ runIdentity $ runCoroutineT exp
    handle (Yield q cont) = do
        putStrLn q
        l <- getLine
        case map toLower l of
            "y"   -> run $ cont Y
            "yes" -> run $ cont Y
            "n"   -> run $ cont N
            "no"  -> run $ cont N
            _   -> putStrLn "Please answer 'yes' or 'no'" >> handle (Yield q cont)
    handle (Result fruit) = do
        putStrLn $ "The fruit you have is: "++show fruit

When we run our co-routine, it returns with one of these two events:

  • Yield, which happens when yield is executed. It gives us the output value (Question) and the continuation, which when passed the input value (Answer) gives us the same ‘Expert’ type we started with.
  • Result, which happens when the co-routine has finished executing.

So how does CoroutineT work?

We’ll start with the types:

data Result i o m a = Yield o (i -> CoroutineT i o m a) | Result a
-- | Co-routine monad transformer
--
--   * i = input value returned by yield
--
--   * o = output value, passed to yield
--
--   * m = next monad in stack
--
--   * a = monad return value
data CoroutineT i o m a = CoroutineT {
        runCoroutineT :: m (Result i o m a)
    }

Hopefully that’s pretty straightforward. ‘yield’ is defined like this:

-- | Suspend processing, returning a @o@ value and a continuation to the caller
yield :: Monad m => o -> CoroutineT i o m i
yield o = CoroutineT $ return $ Yield o (\i -> CoroutineT $ return $ Result i)

The key point here is that the continuation does nothing except return the value, which is what we want it to do when we run a monad that contains only a yield.

Most of the magic is in the definition of >>=, thus:

instance Monad m => Monad (CoroutineT i o m) where
    return a = CoroutineT $ return $ Result a
    f >>= g = CoroutineT $ do
        res1 <- runCoroutineT f
        case res1 of
            Yield o c -> return $ Yield o (\i -> c i >>= g)
            Result a  -> runCoroutineT (g a)
    -- Pass fail to next monad in the stack
    fail err = CoroutineT $ fail err

A typical monad would normally execute f then pass its result to g and execute that, and this is in fact exactly what we do in the Result case. Ho hum.

But there’s no law that says you have to execute g. This is Haskell so we can do whatever we like. g is just a plain old closure representing the continuation.

So what we do in the Yield case is take the continuation that executing f gave us, and bind that to the continuation g, then bail out of the monad (in the same way ErrorT does when it gets an error), handing our constructed continuation to the caller. So we end up with a closure that represents the entire execution state of the monad, and it doesn’t matter how deeply nested we are. It just puts the continuation together in the right way as we unravel everything on our way back to the caller.

Here’s the code in downloadable form:

This code is released in the public domain.

Stephen Blackheath, Manawatu, New Zealand


9 Responses  
  • sclv writes:
    July 22nd, 2010 at 1:34 AM

    Sigpfe’s formulation of coroutines in Haskell is particularly nifty as well (you get session types out of them!):

    http://blog.sigfpe.com/2009/11/programming-with-impossible-functions.html

  • Peter Hancock writes:
    July 22nd, 2010 at 5:10 AM

    Thanks – a very interesting post, ‘cos (1) I’m a long-time fan and putter-to-use of coroutines. (2) I’m now interested more in mathematical structures than code, and I’m (still) trying to see what your construction boils down to. (When the necessary but noisy Haskell hoo-hah is boiled away.)

    It looks to me (but I’m not sure yet) that your type Result i o m a is, more or less, the free monad over (Moore i o . m), where Moore i o is the functor that at x is (o,i->x) (as in Moore automata).

    It surprises me that you’ve a nice simple (though, as you admit, contrived) example, that doesn’t involve (as I would’ve expected) the dual functor Mealy i o = o->(i,x). But then, my expectations were probably wrong; coroutine interactions are much more “between equals”, than actor/reactor, client/server or something asymmetrical like that kind.

  • Bas van Dijk writes:
    July 22nd, 2010 at 7:52 AM

    Note the similarity between your co-routines and iteratees:

    newtype Iteratee el m a = Iteratee{runIter:: m (IterV el m a)}
    data IterV el m a = IE_done a (Stream el)
              | IE_cont (Stream el -> Iteratee el m a) (Maybe ErrMsg)

    from: http://okmij.org/ftp/Haskell/Iteratee/IterateeM.hs

  • Iteratees and a (very) Minimal Model of Shared-State Concurrency « Melding Monads writes:
    July 22nd, 2010 at 9:27 AM

    [...] The idea here is that an iterator is either done, and returns a final result (of type r), or it might want to produce more, so it returns an intermediate result (of type o) along with a continuation to be called if and when further computation is required. Interestingly, Stephen Blackheath also used an equivalent structure in today’s post, Co-routines in Haskell. [...]

  • Jean-Philippe Gariépy writes:
    July 22nd, 2010 at 12:55 PM

    Co-routines can be interesting in any kind of GUI but they are particularly interesting for Web GUI. HTTP is stateless but the co-routine can preserve the state of execution. This can be handful for complex control flows. For VoiceXML where the application flow is linear (no back button, no refresh, no frames) this is ideal!

  • Heinrich Apfelmus writes:
    July 22nd, 2010 at 10:46 PM

    Great post, simple and to the point.

    However, I think the viewpoint of operational semantics gives a more flexible and general implementation of coroutines, or in fact any monad, while being just as simple. I have written a few examples that complement my “Operational Monad Tutorial” which explains this approach in detail:

    • A demonstration of a web session, very much like Jean-Philippe Gariépy suggests.

    • A TicTacToe implementation that interleaves different players, very much like coroutines would allow us to do.

  • Bonus writes:
    July 23rd, 2010 at 12:37 AM

    This is awesome. I love these articles that make you go “Aghh, this makes so much sense, why didn’t I think of that?”. Got links to any papers about this?

  • Stephen Paul Weber writes:
    January 13th, 2013 at 12:09 PM

    I was playing around with simplifying some of this code a bit (ala http://pastie.org/5675896), and looking around hackage, and realised that nothing thing simple or directly useful exists for coroutines on hackage right now. This seems like a real shame, because it makes it seems like coroutines in Haskell are somehow complicated, when they are in fact super simple and generic.

    Have you thought about cabalizing something based on this?

  • Greg Reagle writes:
    January 24th, 2013 at 7:50 AM

    Coroutines are not needed, in this example, to separate I/O from logic, which can be accomplished using traditional functions.

    import Data.Char

    data Answer = Y | N deriving Eq data Fruit = Apple | Kiwifruit | Banana | Orange | Lemon deriving Show

    askYesNo :: String -> IO Answer askYesNo question = do putStrLn question answer return Y ‘n’ -> return N _ -> putStrLn “Please answer ‘yes’ or ‘no’” >> askYesNo question

    identifyFruit :: IO Fruit identifyFruit = do yellow <- askYesNo “Is it yellow?” if yellow == Y then do long <- askYesNo “Is it long?” if long == Y then return Banana else return Lemon else do orange <- askYesNo “Is it orange?” if orange == Y then return Orange else do fuzzy <- askYesNo “Is it fuzzy?” if fuzzy == Y then return Kiwifruit else return Apple

    main :: IO () main = do putStrLn $ “Expert system for identifying fruit” fruit <- identifyFruit putStrLn $ “The fruit you have is: ” ++ show fruit


Leave a Reply

»  Substance: WordPress   »  Style: Ahren Ahimsa
© Alex Mason (Axman6) 2009