Presumably concat also has to use skip, for the same reason as filter. Otherwise it has to recursively process the outer stream until it gets to a non-empty inner stream, which breaks the rule that only the final consumer is recursive.
concat [[1,2,3],[4,5],[],[6,7]] probably looks something like: Yield 1, Yield 2, Yield 3, Skip, Yield 4, Yield 5, Skip, Skip, Yield 6, Yield 7, Skip, Done -- Dan On Wed, Apr 24, 2013 at 6:52 PM, Gábor Lehel <illiss...@gmail.com> 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? Skip was added explicitly to be able to > efficiently handle things like filter (without it the Step datatype is > exactly the base functor for lists), but if concat "works", then filter p > can be expressed as concat . map (\x -> if (p x) then [x] else []). Of > course, presumably filter isn't the only function that requires Skip, I > don't know what the others are. (Also of course "solve" and "works" are > intentionally fuzzy, with the point being that I don't know if "solving" > concat implies that the desirable properties would survive composition in > the suggested manner.) > > -- > Your ship was destroyed in a monadic eruption. > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe