Composability of Iteratees.

For this post, we'll consider composition within the same stream as vertical composition, and transforming one stream to another as horizontal composition. Think of streams flowing down the page. For category theorists, these aren't the standard horizontal vertical, but they work here.

The composability of the three main types in the enumerator package can be summarized as follows:

	Enumerator	Enumeratee	Iteratee
Enumerator	Monoid (Vertical)
Enumeratee	Enumerator (Horizontal)	Category (Horizontal)
Iteratee	Iteratee (Vertical)	Iteratee (Horizontal)	Monad (Vertical)

Let's start with the diagonals.

Enumerators form a Monoid.

Enumerators form a Monoid, via concatenation, similar to lists. The instance declaration is straightforward:

instance (Monad m) => Monoid (Enumerator a m b) where

  mempty = returnI

  mappend = (>==>)

>==> is defined in the standard enumerator package:

(>==>) e1 e2 s = e1 s >>== e2

Simply, given the two enumerators to join, and a step, feed the first one to the step, and then the second one. This is a horizontal composition.

Enumeratees form the arrows of a Category.

Don't get scared, that simply means that

a) there is an identity Enumeratee

b) Enumeratees can be composed like functions.

The identity Enumeratee:

idEnumeratee :: (Monad m) => Enumeratee a a m b

idEnumeratee = checkDone (continue . step) where

  step k EOF = yield (Continue k) EOF

  step k (Chunks xs) = k (Chunks xs) >>== checkDone (continue . step)

That was the simple part. Now the composition of Enumeratees:

(.=) :: forall m ao am ai. (Monad m) =>

  (forall b. Enumeratee am ai m b)

  -> (forall b. Enumeratee ao am m b)

  -> (forall b. Enumeratee ao ai m b)

en_mi .= en_om = \step_i -> joinI $ en_om $$ en_mi step_i

Here, i is the inner type (stream data goes from out to in) m is the middle type, and o is the outer type. The type signature is slightly complex because the eventual result of the consumer is independent of composing the streams.

Now to go through the definition. The types of various pieces explain what's going on.

en_mi step_i :: Iteratee am m (Step ai m b)

en_om $$ en_mi step_i :: Iteratee ao (Step am (Step ai m b))

joinI :: Iteratee ao (Step am m z) -> Iteratee ao m z

joinI $ en_om $$ en_mi step_i :: Iteratee ao (Step ai m b)

-- replace z with (Step ai m b)

joinI simply sends EOF to the inner iteratee when the outer one yields, removing the chance for feeding it anything else. We use it here to remove the chance to feed any more am's to the stream, because the result type doesn't have any reference to am.

Iteratees form a Monad.

This is covered in the code, and in a previous post

Now for the off diagonal entries.

For all the joining operators, = represents an Enumeratee (think of = as looking like a pipe), and $ represents a consumer or producer.

Enumeratee + Iteratee == Iteratee.

Thinking of it like pipes sources and sinks, a pipe connected to a sink is still a sink. The operator defined in the enumerator package is =$. Thinking of data flowing from left to right, that looks like a pipe hooked up to a right end. This is a horizontal composition.

Enumerator + Enumeratee == Enumerator.

This is symmetrical to the above case, as is the operator $=. Here the end is on the left, and the pipe is on the right. This is also a horizontal composition

Enumerator + Iteratee == Iteratee.

This returns the partially completed Iteratee. More data can be fed to the result iteratee as kind of concatenation after the fact. The operator matches the mnemonic above $$ matches both ends of the pipe. This is a vertical composition.

Example concatenation:

enum2 $$ enum1 $$ iter == (enum1 `mappend` enum2) $$ iter

-- note the order reversal.