[Haskell-cafe] Stream fusion and span/break/group/init/tails
illissius at gmail.com
Thu Apr 25 01:43:35 CEST 2013
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 , 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
Your ship was destroyed in a monadic eruption.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe