<div dir="ltr"><div><div><div><div>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.<br>
<br></div> concat [[1,2,3],[4,5],[],[6,7]]<br><br></div>probably looks something like:<br><br></div> Yield 1, Yield 2, Yield 3, Skip, Yield 4, Yield 5, Skip, Skip, Yield 6, Yield 7, Skip, Done<br><br></div>-- Dan<br>
<div><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Apr 24, 2013 at 6:52 PM, Gábor Lehel <span dir="ltr"><<a href="mailto:illissius@gmail.com" target="_blank">illissius@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 class="HOEnZb"><div class="h5"><br><br><div class="gmail_quote">On Wed, Apr 24, 2013 at 7:56 PM, Bryan O'Sullivan <span dir="ltr"><<a href="mailto:bos@serpentine.com" target="_blank">bos@serpentine.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="gmail_extra"><div>On Wed, Apr 24, 2013 at 10:47 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_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div>I address it briefly in my thesis [1], Section 4.8.2. I think it's a<br>
fundamental limitation of stream fusion.<br></div></blockquote></div><br></div>See also concat, where the naive fusion-based implementation has quadratic performance:</div><div class="gmail_extra"><br></div><div class="gmail_extra">
concat :: [Text] -> Text</div><div class="gmail_extra">concat txts = unstream (Stream.concat (List.map stream txts))<br></div><div class="gmail_extra"><br></div><div class="gmail_extra">I've never figured out how to implement this with sensible characteristics within the fusion framework.</div>
</div></blockquote></div><div><br></div></div></div><div>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.)</div>
<span class="HOEnZb"><font color="#888888">
<div><br></div>-- <br>Your ship was destroyed in a monadic eruption.
</font></span><br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div>