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’:

typeQuestion = StringdataAnswer = Y | NderivingEq

typeExpert a = CoroutineT Answer Question Identity a

dataFruit = Apple | Kiwifruit | Banana | Orange | LemonderivingShow

identifyFruit :: Expert Fruit identifyFruit =doyellow <- yield "Is it yellow?"ifyellow == Ythendolong <- yield "Is it long?"iflong == Ythenreturn Bananaelsereturn Lemonelsedoorange <- yield "Is it orange?"iforange == Ythenreturn Orangeelsedofuzzy <- yield "Is it fuzzy?"iffuzzy == Ythenreturn Kiwifruitelsereturn Apple

Our ‘Expert’ type above…

typeExpert 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 =doputStrLn $ "Expert system for identifying fruit" run identifyFruitwhererun :: Expert Fruit -> IO () run exp = handle $ runIdentity $ runCoroutineT exp

handle (Yield q cont) =doputStrLn q l <- getLinecasemap toLower lof"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) =doputStrLn $ "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:

dataResult 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 valuedataCoroutineT 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 calleryield :: 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:

instanceMonad m => Monad (CoroutineT i o m)wherereturn a = CoroutineT $ return $ Result a f >>= g = CoroutineT $dores1 <- runCoroutineT fcaseres1ofYield o c -> return $ Yield o (\i -> c i >>= g) Result a -> runCoroutineT (g a)-- Pass fail to next monad in the stackfail 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*

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