<div dir="ltr">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 class="gmail_extra">
<div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">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">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">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 style> To further this, note that in a total language, with the type:</div><div style><br></div><div style> codata Stream a = End | Yield a (Stream a)</div>
<div style><br></div><div style>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 style><br></div><div style>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>
</div><br></div><div class="gmail_extra" style>-- Dan</div></div>