[Haskell-cafe] Fwd: Semantics of iteratees, enumerators, enumeratees?

[C. McCann]

On Tue, Aug 24, 2010 at 11:44 AM, John Lato <jwlato at gmail.com> wrote:
>> Aren't they closer - in implementation and by supported operations -
>> to resumptions monads?
>>
>> See many papers by William Harrison here:
>> http://www.cs.missouri.edu/~harrisonwl/abstracts.html
>
> I'm not familiar with resumption monads.  I'll have to read some of the
> papers and get back to you.

>From glancing at the papers myself, the concept seems quite simple.
The "cheap threads" paper defines a minimal resumption monad as:

    data Res a = Done a | Pause (Res a)

...which is just a single value nested in a bunch of superfluous
constructors. It then parameterizes this by an arbitrary monad to
create a resumption "monad transformer":

    data ResT m a = Done a | Pause (m (ResT m a))

>From which we can obtain an automaton with a halt state using the
reader monad, or an (Iteratee m) using (ReaderT chunk m). But this is
in fact somewhat misleading, because ResT is not actually a monad
transformer except in a trivial sense! (>>=) is defined for (ResT m)
as:

    (Done v) >>= f = f v
    (Pause r) >>= f = Pause (r >>= \k -> return (k >>= f))

Which is equivalent to:

    (Done v) >>= f = f v
    (Pause r) >>= f = Pause (fmap (>>= f) r)

In other words, ResT constructs a Monad from any Functor, not just
another Monad. If memory serves me, this is actually nothing more than
the free monad of the functor.

In fact, this makes a lot more sense than my earlier reduction in
terms of an Automaton arrow: Given a chunk type "c" and some Functor
"f", the functor composition of ((->) c) and f gives another functor,
the free monad of which is roughly an Iteratee for "c" and "f", modulo
some details regarding error handling and returning unused input that
I don't think change the essential structure significantly.

The obvious question of what the dual of a resumption monad (and, by
extension, an Iteratee) looks like is simple enough. The minimal
resumption monad is the free monad of Identity; the cofree comonad of
Identity is an infinite stream of values. An Iteratee is an automaton
built from functor composition with Reader; the cofree comonad of the
same also gives an automaton, but one with no halting state that
produces an output immediately at each step based on the current
state, akin to a Moore-style machine instead of the Mealy-style
Automaton arrow. Being a source of data, either form of "co-resumption
comonad" would probably make a serviceable Enumerator type, given some
recursive driver function that pulls data from the stream and stuffs
it into the Iteratee.

All of which leads me to suspect that any implementation of Iteratees
could probably be replaced by category-extras and about eleven lines
of zygohistomorphic prepromorphisms or whatever.

- C.