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

[Duncan Coutts]

On Sun, 2013-04-21 at 18:07 -0700, Edward Z. Yang 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 address it briefly in my thesis [1], Section 4.8.2. I think it's a
fundamental limitation of stream fusion.

It looks like fold and unfold fusion systems have dual limitations:
fold-based fusion cannot handle zip style functions, while unfold-based
fusion cannot handle unzip style functions. That is fold-based cannot
consume multiple inputs, while unfold-based cannot produce multiple
outputs.

I'll be interested to see in more detail the approach that Ben is
talking about. As Ben says, intuitively the problem is that when you've
got multiple outputs so you need to make sure that someone is consuming
them and that that consumption is appropriately synchronised so that you
don't have to buffer (buffering would almost certainly eliminate the
gains from fusion). That might be possible if ultimately the multiple
outputs are combined again in some way, so that overall you still have a
single consumer, that can be turned into a single lazy or eager loop.

[1]: http://code.haskell.org/~duncan/thesis.pdf

Duncan