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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe