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

[Gábor Lehel]

Ah, good point.

On Thu, Apr 25, 2013 at 1:06 AM, Dan Doel <dan.doel at 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 <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
>>
>>
>


-- 
Your ship was destroyed in a monadic eruption.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130425/7c5c2d80/attachment.htm>