Various Patterns of Iteratee
Created at 2016-05-03T21:09:11.000Z

On the way of creating my first Haskell web app with snap, I came across with Iteratee. Since I have a background of studying Category Theory (especially Coalgebra Theory), it was easy to understand the definition of Iteratee in its simplest form explained in Haskell Wiki. But, at certain point, the real/practical definition of Iteratee overwhelmed me.

So, this post (and my implementations IterateeNonWaitable, IterateeWaitable) is:

  • to fill the gap between the simplest form and practical form, and,
  • to re-explain some notions of Iteratee with Category Theory.

Simplest Definition

Starting from the definition of "Simplest" Iteratee I've used in IterateeNonWaitable:

data Iteratee s a
  = Continue (s -> Iteratee s a)
  | Yield a

This algebraic data type satisfies the equation below (here Iteratee s = $T_{s}$):

$$ T_{S}(A) = T_{S}(A)^S + A. $$

So, this Monad can be written with $\mu$ notation:

$$ T_{S}(A) = \mu X. (X^S + A) $$

If you look at the page 3 in the paper Notions of computation and monads, Eugenio Moggi, you'll see this definition is exactly same to what's introduced as "interactive input monad", $T(A) = (\mu\gamma.A + \gamma^U)$.

Considering $X^S = \prod_{s \in S}X$, each element can be considered to be some kind of tree as below:

2016-05-04 14.17.36

"Waitable" Definition

I found the previous definition is too weak to accommodate "waiting-for-coming-input" state. So, I changed a definition from IterateeNonWaitable to IterateeWaitable

data Iteratee s a
  = Continue (Maybe s -> Iteratee s a)
  | Yield s

This Iteratee explicitly assumes input set includes "waiting instruction" which I represent by Nothing. (In the real defintion, empty chunk is used for the same purpose.)

Here is a tree representation for this pattern of definition:

2016-05-04 14.17.36

Summery

About My Implementation:

  • no monad transformation (so it cannot accommodate IO processing)
  • no Exception constructor
  • no Chunk or EOF
  • not leave stream (Yield only leaves result a)
  • "Waitable" has Nothing as waiting state
  • enumerator composition doesn't work for "NonWaitable" iteratee defintion
  • it's impossible to implement listFunction2Iteratee for "NonWaitable" since Nothing input did good ad-hocly

Original implementation

  • practical implementation of "interatcive input output monad"
    • Chunk-ed input
    • explicit EOF as input
    • explicit Exception state

About Enumerator:

  • Enumerator is not a theoretically solid notion as Iteratee. This is only for ad-hoc programatic notion.

Future Work

  • Define Iteratee via free monad:

  • Derive Monad definition via GHC "deriving" mechanism

  • Theoretical foudnation for Enumeratee:

    • it might be a practical ad-hoc notion similer to Enumerator, but it might be theoretically interesting.
  • Give deeper explanation using _Final Coalgebra_
    • I've ignored the fact that Haskell's algebraic data type accommodates infinite structure. So, technically/theoretically, the definition of Iteratee should be considered as Final Coalgebra:

2016-05-04 14.38.04

References