iteratee roll gives incorrect results

[Akio Takano]

Hi,

I've found that `roll' from Data.Iteratee.ListLike does not work as
expected. The following program demonstrates the problem. it prints
"[[1,2]] [2,3]" while it should print "[[1,2,3]] [2,3]".

import qualified Data.Iteratee.ListLike as I
import Data.Iteratee.Iteratee

main = I.enumPureNChunk [1, 2, 3] 2 iter >>= run >>= putStrLn
    where
        iter = do
            xs <- I.roll 4 1
            ys <- I.stream2list
            return $ show (xs::[[Int]]) ++ " " ++ show  (ys::[Int])

I tried to fix it, but it turned out to be not easy.  I try to explain
the situation:

1. When an iteratee moves to the Done state, it must return the
unconsumed part of the stream. Perhaps this means it must return a
stream that is a subsequence of the given stream. Though I'm not sure
how strictly this rule is enforced, at least (>>=) expects its LHS to
return EOF when it sends EOF to the LHS. Otherwise the EOF in the
stream gets lost and the resulting iteratee of (>>=) does not
terminate on EOF.

2. An iteratee can return some elements or an EOF marker as the
unconsumed part, but not both at the same time.

Suppose you are evaluating (enumPure1Chunk [1] (roll 2 0) >>= run).
The iteratee first receives (Chunk [1]) and continues because it has
not seen enough number of stream elements to return a result. Next it
receives (EOF Nothing). It should move to the Done state now, but it's
not clear what stream it should return. If it returns (Chunk [1]) it
violates "1." above and will not be able to be used with (>>=). If it
returns (EOF Nothing), that means it consumed the whole stream, which
is an incorrect result because roll is called with d=0.

In general there seems to be no way for an iteratee to safely look
ahead to an element beyond the next one, without consuming any
elements.

I can think of two options to solve or work around the problem.

- Modify (>>=) so that it will allow its LHS to return some elements
on EOF. In that case it will explicitly feed EOF to its RHS. I
attached code showing the approach. I'm not sure this is a correct
thing, especially regarding the smantics and the performance of (>>=).
Also I haven't confirmed that (>>=) is the only function that depends
on the EOF->EOF assumption.

- Change the definition of Stream so that they can contain some
elements and an EOF marker at the same time.  Then an iteratee will be
able to "put back" any number of elements onto the stream. This will
require a global rewrite of the library.

Any ideas?

Takano Akio
-------------- next part --------------
A non-text attachment was scrubbed...
Name: roll.hs
Type: text/x-haskell
Size: 2408 bytes
Desc: not available
URL: <http://projects.haskell.org/pipermail/iteratee/attachments/20110314/25e82853/attachment.hs>