Ah, good point. On Thu, Apr 25, 2013 at 1:06 AM, Dan Doel <dan.d...@gmail.com> wrote:
> 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 >> >> > -- Your ship was destroyed in a monadic eruption.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
