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

[Dan Doel]

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 <illissius at gmail.com> 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? 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130424/3f9ca836/attachment.htm>