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

Duncan Coutts duncan.coutts at googlemail.com
Wed Apr 24 20:00:32 CEST 2013


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




More information about the Haskell-Cafe mailing list