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

[Gábor Lehel]

On Mon, Apr 29, 2013 at 8:40 PM, Dan Doel <dan.doel at gmail.com> wrote:

> On Mon, Apr 29, 2013 at 10:05 AM, Duncan Coutts <
> duncan.coutts at googlemail.com> wrote:
>
>> On Thu, 2013-04-25 at 00:52 +0200, Gábor Lehel 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?
>>
>> Dan is right, we still need Skip. My suggested "solution" to the
>> concatmap problem is also mostly independent of the skip issue.
>>
>> You shouldn't think of skip as being a hack. It's not. It's how we
>> express a more general class of producers in a way that is productive.
>
>
>  To further this, note that in a total language, with the type:
>
>     codata Stream a = End | Yield a (Stream a)
>
> filter is not definable; it is not a total function. At least, barring an
> extra proof of some sort that the predicate will yield true after a finite
> amount of time. concat is similar.
>
> Also, adding Skip (Stream a) is a relatively standard way of explicitly
> representing lazy, partial values. (This is opposed to the partiality
> monad, which is like an encoding of strict general recursion). That is, if
> νF is the type of total values, then ν(F + Id) is the type of partial
> values. I don't know how easy it is to delete from a more complex tree
> using just that extension, but in theory you could productively represent
> arbitrary manipulations with just that, I believe.
>
> -- Dan
>

Very interesting (and makes sense), thank you.

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