Notes on Iteratees

Note: Here’s a post, originally written in 2015, that I found while looking through my archive of drafts. It’s a bit dense, but I think it’s helpful as a companion to the Iteratees paper. Further, I think this is a good example of what people mean when they say they can understand something via its type, or that the types can aid in documentation. I don’t think the types could completely replace Oleg’s original write up, but when an abstraction is compositional, starting from a small set of primitives and building up to something greater, there’s a real sense in which an understanding of those primitives and their types can be used as a compass that guides you across the larger landscape.

These are notes I wrote while reading Oleg Kiselyov’s Iteratees.¹ They focus on trying to give the types meaning. When confronted with abstractions such as this (ones where many things follow from a very small core), I find it helpful to think carefully about what the types imply. Once I develop that intuition, using the library becomes much easier.

type Iteratee el m a

An Iteratee is a stream processor. It processes a stream of elements el using the abilities of some monad m and producing a result a. One way of viewing this is as a fold over some stream with elements el. Compare this to foldM:

foldM :: (Foldable t, Monad m) => (a -> el -> m a) -> a -> t el -> m a

The first two parameters, (a -> el -> m a) and a, describe how to process elements of type el in a monad m and produce a value a. This is similar to how Iteratee el m a is a processor of elements of type el in m producing a.

-- Counts the number of spaces in a stream of `Char`s.
countSpaces :: Iteratee Char Identity Int

The function above is what an Iteratee that counts spaces might look like. It folds over a stream of Char, needing no effects (thus the Identity monad) and producing as a result the number of spaces in the stream. Making the Iteratee polymorphic in m will be useful later on, when we look at Enumerator.

countSpacesPure :: Monad m => Iteratee Char m Int

The result of an Iteratee can be extracted with run.

run :: Monad m  => Iteratee el m a -> m a

We can extract the result of countSpaces with run. It will evaluate to 0 since no source of elements was supplied.

runIdentity (run countSpaces) -- returns 0

To supply it with elements we use an Enumerator.

type Enumerator el m a = Iteratee el m a -> m (Iteratee el m a)

An Enumerator is a producer. It produces a stream of elements of type el. It may make use of some effect m to produce these elements (perhaps it uses IO to read from a file). Finally, it produces a result of type a.

Unwrapping the type, we see that it needs to be supplied with an Iteratee el m a. This is the processor that the Enumerator produces elements for. The result, m (Iteratee el m a), describes a processor running in the Enumerator’s effect, m. Why is it running in m? Because the Enumerator makes use of m’s effect to produce elements for the processor.

Notice that the return type, m (Iteratee el m a), forces the fold and the producer to use the same effect. This is why m is made generic in countSpacesGeneric above, otherwise the producer would be restricted to the Identity effect (and could not, for example, read from a file). This sharing of m also means we can bind the result to run to extract the final value:

runEnum :: Monad m => m (Iteratee el m a) -> m a
runEnum = (>>= run)

What does it mean for a producer Enumerator el m a to have a result of type a? Why would a producer have a result at all? Notice that a is the type of the Iteratee’s result. So the result of an Enumerator is just the result of running the fold over the elements the Enumerator provides.

Flipping the arguments of foldM and partialy supplying a source of elements (in this case the List [1,2,3]) resembles an Enumerator:

(flip foldM) [1,2,3] :: a -> (a -> el -> m a) -> m a

Like an Enumerator, this supplies the stream [1,2,3] to some processor described by a and (a -> el -> m a) and produces a result of type a using effect m.

type Enumeratee elIn elOut m a =
  Iteratee elOut m a -> Iteratee elIn m (Iteratee elOut m a)

An Enumeratee is a transformer. It consumes elements elIn and produces elements elOut. This gives a result of type a and may make use of some effect m.

Like an Enumerator, it takes an Iteratee as an argument. This is the Iteratee that elOuts are supplied to. This results in a nested processor–a processor that produces another processor. The nested processor looks like this: Iteratee elIn m (Iteratee elOut m a). Examining this more closely, we see that it’s a processor that consumes elements of the input type, elIn, and whose inner result is of type a. Since only the supplied processor can produce a value of type a (the Iteratee that’s an argument to the Enumeratee), we can conclude that the supplied processor must be run to produce the a. So we have a transformer: something that folds over elements of type elIn, pipes those to a fold for elOut and produces the result a. It is both a producer for the given Iteratee elOut m a and a consumer for elements elIn.

Similar to how the return type of an Enumerator, m (Iteratee el m a), is a processor being supplied els with the help of m, an Iteratee elIn m (Iteratee elOut m a) is an Iteratee being supplied elements with the help of another Iteratee.

Finally, let’s examine the program-interpreter view of Iteratees: “Iteratee processes are modeled as a data type; enumerators become interpreters, thus defining the semantics of iteratees as parsers of an enumerator’s source.”²

Changing this slightly, an Iteratee el m a is a program that takes input el to evaluate to a result a. An Enumerator el m a then becomes an interpreter for these programs that can supply elements of type el. So, just as you can apply an interpreter to a program, you can apply an Iteratee to an Enumerator:

type Enumerator el m a = Iteratee el m a -> m (Iteratee el m a)

m (Iteratee el m a) is now a program supplied with input with the help of m. Notice, though, that the program is only partially interpreted. In order to finish interpretation, we need to terminate the inner Iteratee and extract the result. This is the role of run :: Iteratee el m a -> m a. Binding run to the program terminates it and gets the final result.

An Enumeratee then becomes an interpreter which produces another program in IO.

programWithInputFromIO :: IO (Iteratee el IO a)
programWithInputFromIO >>= run :: IO a