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

[Gábor Lehel]

On Mon, Apr 29, 2013 at 4:05 PM, Duncan Coutts <duncan.coutts at googlemail.com
> wrote:

> 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
>
>
Thanks for the explanation. I looked at your thesis previously, but only
read through a couple of sections (including the one about concatMap). I
might go through the state machine parts as well now that I know the
significance/relevance.

The thing in particular that was motivating me is that if it weren't for
Skip, it seems that to some extent (I haven't had time to investigate
precisely what extent) you could write a stream fusion framework in a
datatype-generic way, parameterized over the base functor. But it wasn't
obvious to me how (or whether) you would translate Skip. But maybe the
state machine perspective will provide some insight into that. I'll think
about it.

-- 
Your ship was destroyed in a monadic eruption.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130429/d2ac5785/attachment-0001.htm>