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

[Gábor Lehel]

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130425/cc385084/attachment.htm>