[Haskell-cafe] Stream fusion and span/break/group/init/tails

[Ben Lippmeier]

On 22/04/2013, at 11:07 , Edward Z. Yang <ezyang at mit.edu> wrote:

> Hello all, (cc'd stream fusion paper authors)
> 
> I noticed that the current implementation of stream fusion does
> not support "multiple-return" stream combinators, e.g.
> break :: (a -> Bool) -> [a] -> ([a], [a]).  I thought a little
> bit about how might one go about implement this, but the problem
> seems nontrivial. (One possibility is to extend the definition
> of Step to support multiple return, but the details are a mess!)
> Nor, as far as I can tell, does the paper give any treatment of
> the subject.  Has anyone thought about this subject in some detail?


I've spent the last few months fighting this exact problem.

The example you state is one instance of a more general limitation. Stream fusion (and most other short-cut fusion approaches) cannot fuse a producer into multiple consumers. The fusion systems don't support any "unzip-like" function, where elements from the input stream end up in multiple output streams. For example:

unzip :: [(a, b)] -> ([a], [b])

dup   :: [a] -> ([a], [a])

The general problem is that if elements of one output stream are demanded before the other, then the stream combinator must buffer elements until they are demanded by both outputs.

John Hughes described this problem in his thesis, and gave an informal proof that it cannot be solved without some form of "concurrency" -- meaning the evaluation of the two consumers must be interleaved.

I've got a solution for this problem and it will form the basis of Repa 4, which I'm hoping to finish a paper about for  the upcoming Haskell Symposium.

Ben.