Why is the Empty input case needed in Scala Iteratees?

Question

The 3 descriptions of the Iteratee pattern in Scala that I've seen all include 3 cases for input. For example, from James:

sealed trait Input[+E]
object Input {
  case object EOF extends Input[Nothing]
  case object Empty extends Input[Nothing]
  case class El[+E](e: E) extends Input[E]
}

More details see blogs by James, Runar, Josh.

My question is simply: why precisely is the Empty input case needed?

The iteratee pattern defines a relationship between a producer and a consumer of a stream of values. Intuitively, it seems that if any input is empty, the producer that "runs" the iteratee should simply collapse that empty item away, and not call the iteratee until non-empty input is available.

I note the pull-based analog of iteratees, the much more familiar iterators, do not define an empty case, although it's possible that elements have been filtered away "inside" the iterator.

trait Iterator[E] {
    next: E        // like El
    hasNext: Boolean  //like EOF
}

While all the above blogs mention the need for an Empty input in passing, but they don't discuss explicitly why it cannot be eliminated altogether. I notice the example iterators shown treat Empty input as a no-op.

I'd really like an example, with code, of a plausible "real-world-ish" problem that requires the Empty input message to solve.

Answer 1

Let's say you connect an enumerator that feeds some elements to the peek iteratee that looks at the first element and returns it but does not consume it, leaving it to be used by possibly another iteratee that will be composed with peek. Then you would want to provide a mechanism for peek to put back the element. From what I can tell from both Play and Scalaz iteratee, the done iteratee takes an argument just for this purpose. So you can do something like in pseudo code: done(Some(result), El(result)). See this implementation of peek.

Now if you implement something like head which will actually consume the element, then it feels like one way to do it is to return done(Some(result), emptyInput) to indicate that the input was consumed.

See also this comment in the playframework source code showing the second argument of Done(_, _) is for unused input and initialized as an empty default. So empty is not something seldom used for which it's hard to find real-world example. It is really key to the implementation of the iteratees. In fact it may be interesting to see which iteratee frameworks do not have empty and how they managed to implement peek and head.

Answer 2

James Roper gave a useful response here, including this snippet I found interesting:

I guess another way it could be implemented is to have Option[Input] as the left over input for Done. This would make implementing iteratees simpler since they wouldn't need to handle empty.