[prev in list] [next in list] [prev in thread] [next in thread]
List: haskell-cafe
Subject: Re: [Haskell-cafe] Stream fusion and span/break/group/init/tails
From: Gábor_Lehel <illissius () gmail ! com>
Date: 2013-05-07 16:43:50
Message-ID: CAPNUp0_Kd1mVgAagDaUQCDb8X-3diwTLHaADwTrFiMQRsM=3yQ () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
On Mon, Apr 29, 2013 at 8:40 PM, Dan Doel <dan.doel@gmail.com> wrote:
> On Mon, Apr 29, 2013 at 10:05 AM, Duncan Coutts <
> duncan.coutts@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@serpentine.com
>> >wrote:
>> >
>> > > On Wed, Apr 24, 2013 at 10:47 AM, Duncan Coutts <
>> > > duncan.coutts@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.
[Attachment #5 (text/html)]
<br><br><div class="gmail_quote">On Mon, Apr 29, 2013 at 8:40 PM, Dan Doel <span \
dir="ltr"><<a href="mailto:dan.doel@gmail.com" \
target="_blank">dan.doel@gmail.com</a>></span> wrote:<br><blockquote \
class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc \
solid;padding-left:1ex"> <div dir="ltr"><div class="im">On Mon, Apr 29, 2013 at 10:05 \
AM, Duncan Coutts <span dir="ltr"><<a href="mailto:duncan.coutts@googlemail.com" \
target="_blank">duncan.coutts@googlemail.com</a>></span> wrote:<br></div> <div \
class="gmail_extra"> <div class="gmail_quote"><div class="im"><blockquote \
class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc \
solid;padding-left:1ex"><div>On Thu, 2013-04-25 at 00:52 +0200, Gábor Lehel \
wrote:<br> > On Wed, Apr 24, 2013 at 7:56 PM, Bryan O'Sullivan <<a \
href="mailto:bos@serpentine.com" target="_blank">bos@serpentine.com</a>>wrote:<br> \
><br> > > On Wed, Apr 24, 2013 at 10:47 AM, Duncan Coutts <<br>
> > <a href="mailto:duncan.coutts@googlemail.com" \
target="_blank">duncan.coutts@googlemail.com</a>> wrote:<br> > ><br>
> >> I address it briefly in my thesis [1], Section 4.8.2. I think it's \
a<br> > >> fundamental limitation of stream fusion.<br>
> >><br>
> ><br>
> > See also concat, where the naive fusion-based implementation has \
quadratic<br> > > performance:<br>
> ><br>
> > concat :: [Text] -> Text<br>
> > concat txts = unstream (Stream.concat (List.map stream txts))<br>
> ><br>
> > I've never figured out how to implement this with sensible \
characteristics<br> > > within the fusion framework.<br>
> ><br>
><br>
> If you could "solve" concat, might that also lead to be being able to \
do<br> > without the Skip constructor?<br>
<br>
</div>Dan is right, we still need Skip. My suggested "solution" to the<br>
concatmap problem is also mostly independent of the skip issue.<br>
<br>
You shouldn't think of skip as being a hack. It's not. It's how we<br>
express a more general class of producers in a way that is \
productive.</blockquote><div><br></div></div><div> To further this, note that in a \
total language, with the type:</div><div><br></div><div> codata Stream a = End | \
Yield a (Stream a)</div>
<div><br></div><div>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.</div> <div><br></div><div>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.</div> <span \
class="HOEnZb"><font color="#888888"> </font></span></div><span class="HOEnZb"><font \
color="#888888"><br></font></span></div><span class="HOEnZb"><font \
color="#888888"><div class="gmail_extra">-- Dan</div></font></span></div> \
</blockquote></div><br>Very interesting (and makes sense), thank you.<br \
clear="all"><br>-- <br>Your ship was destroyed in a monadic eruption.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic