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

[Duncan Coutts]

On Wed, 2013-04-24 at 10:56 -0700, Bryan O'Sullivan 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.

Well of course concatMap is another issue. I address that in section
4.8.3 :-)

Summary there is that I don't think it is a fundamental limitation, but
certainly we don't do it properly in practice now. I have a suggestion
in that section for how we might do it.

Duncan