On Thu, 2013-04-25 at 00:52 +0200, Gábor Lehel wrote: > On Wed, Apr 24, 2013 at 7:56 PM, Bryan O'Sullivan <b...@serpentine.com>wrote: > > > On Wed, Apr 24, 2013 at 10:47 AM, Duncan Coutts < > > duncan.cou...@googlemail.com> wrote: > > > >> I address it briefly in my thesis [1], Section 4.8.2. I think it's a > >> fundamental limitation of stream fusion. > >> > > > > See also concat, where the naive fusion-based implementation has quadratic > > performance: > > > > concat :: [Text] -> Text > > concat txts = unstream (Stream.concat (List.map stream txts)) > > > > I've never figured out how to implement this with sensible characteristics > > within the fusion framework. > > > > If you could "solve" concat, might that also lead to be being able to do > without the Skip constructor?
Dan is right, we still need Skip. My suggested "solution" to the concatmap problem is also mostly independent of the skip issue. You shouldn't think of skip as being a hack. It's not. It's how we express a more general class of producers in a way that is productive. You can think of a stream as being a little state machine and sometimes the state machine needs to be able to make transitions without producing any output. One solution to that is to hide those transitions (by running the state machine until it does produce something, ie using recursion/loops) and the other is to expose the transition as a skip. The skip approach where we don't use recursion/loops allows us to do the various transformations we need to be able to effectively optimise the whole thing. If you're interested in this stuff, you can look at the section of my thesis that goes on about this state machine perspective on things. I think it's quite a useful way to understand it (and understand how we optimise stream functions by composing these state machines). More generally, that chapter explains why stream fusion should actually be an optimisation. As for step and the list base functor. Yes, absolutely. And adding skip does make things harder to prove, because it adds more "junk" values. The other major chapter of my thesis explains why it's all still true, even when we have skip, or rather how we have to do things carefully so that it does still remain valid. Duncan _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe