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

[Duncan Coutts]

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 <bos at serpentine.com>wrote:
> 
> > On Wed, Apr 24, 2013 at 10:47 AM, Duncan Coutts <
> > duncan.coutts at 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