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

John Millikin jmillikin at gmail.com
Tue Sep 7 14:21:28 EDT 2010

On Mon, Sep 6, 2010 at 22:49, Ben <midfield at gmail.com> wrote:
> Sorry to be late coming into this conversation.....
> Something that has bothered me (which I have mentioned to John Lato
> privately) is that it is very easy to write non-compositional code due
> to the chunking.  For example, there is a standard function
> map :: (a -> b) -> Enumeratee a b c
> whose meaning I hope is clear : use the function to transform the type
> of a stream and pass it to an iteratee.  However last I checked the
> versions provided in both the iteratee and enumerator packages fail to
> satisfy the equation
> map f (it1 >> it2) == (map f it1) >> (map f it 2)
> because of chunking, essentially.  You can check this with f == id and
> it1 and it2 are head:
> let r = runIdentity . runIteratee
> runIdentity $ run $ enumList 10 [1..100] $ r $ joinI $ map id $ r (head >> head)
> --> Right (Just 2)
> runIdentity $ run $ enumList 10 [1..100] $ r $ joinI $ (map id $ r
> head) >> (map id $ r head)
> --> Right (Just 11)
> It is possible to fix this behavior, but it complicates the "obvious"
> definitions a lot.

Chunking doesn't have anything to do with this, and an iteratee
encoding without input chunking would exhibit the same problem. You're
running into an (annoying? dangerous?) subtlety in enumeratees. In the
particular case of map/head, it's possible to construct an iteratee
with the expected behavior by altering the definition of 'map'.
However, if the composition is more complicated (like map/parse-json),
this alteration becomes impossible.

Remember than an enumeratee's return value contains two levels of
"extra" input. The outer layer is from the enumeratee (map), while the
inner is from the iteratee (head). The iteratee is allowed to consume
an arbitrary amount of input before yielding, and depending on its
purpose it might yield "extra" input from a previous stream.

Perhaps the problem is that 'map' is the wrong name? It might make
users expect that it composes "horizontally" rather than "vertically".
Normally this incorrect interpretation would be caught by the type
checker, but using (>>) allows the code to compile.

Anyway, the correct way to encode @(map f it1) >> (map f it 2)@, using
above style is:

    (map id (r head) >>= returnI) >> (map id (r head) >>= returnI)

so the full expression becomes:

    runIdentity $ run $ enumList 10 [1..100] $ r $ (map id (r head)
>>= returnI) >> (map id (r head) >>= returnI)

which ought to return the correct value (untested; I have no Haskell
compiler on this computer).

More information about the Haskell-Cafe mailing list