<div dir="ltr">One I saw not too long ago was where someone created an infinite Vector and then consumed it immediately. With optimizations turned on, the intermediate Vector was fused away. With optimizations turned off, it wasn't fused away, and the program eventually crashed when it ran out of memory for holding the infinite Vector.<br>

</div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Jul 26, 2014 at 11:28 PM, Carter Schonwald <span dir="ltr"><<a href="mailto:carter.schonwald@gmail.com" target="_blank">carter.schonwald@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">its worth point out that many uses of fusion in haskell libs punt on preserving bottoms, that is, fusion can make *more* programs terminate. I don't have a good example off  hand  mind you</div>

<div class="gmail_extra">

<br><br><div class="gmail_quote"><div><div class="h5">On Sat, Jul 26, 2014 at 4:02 PM, David Feuer <span dir="ltr"><<a href="mailto:david.feuer@gmail.com" target="_blank">david.feuer@gmail.com</a>></span> wrote:<br>

</div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div class="h5">

<p dir="ltr">Hmm... I found something I missed. I need to prove that this doesn't break when the arguments to unfold use seq (if in fact it doesn't). I will have to look into it later.</p><div><div>


<div class="gmail_quote">On Jul 26, 2014 3:34 PM, "David Feuer" <<a href="mailto:david.feuer@gmail.com" target="_blank">david.feuer@gmail.com</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">




<p dir="ltr">The current definition:</p>
<p dir="ltr">unfoldr :: (b -> Maybe (a, b)) -> b -> [a]<br>
unfoldr f b = case f b of<br>
  Just (a,new_b) -> a : unfoldr f new_b<br>
  Nothing -> []</p>
<p dir="ltr">I haven't yet looked over the Core to see if GHC is able to do a worker/wrapper transformation to inline it, but we definitely want to inline it (in some appropriate phase), because doing so has the potential to erase the Maybes. It also isn't a good producer for foldr/build. However, if we (re)write it like this:</p>






<p dir="ltr">unfoldrB f b c n = go b<br>
  where<br>
    go b = case f b of<br>
             Just (a,new_b) -> a `c` go new_b<br>
             Nothing -> n</p>
<p dir="ltr">unfoldr f b = build (unfoldrB f b)</p>
<p dir="ltr">then we get some really nice fusion:</p>
<p dir="ltr">foldr c n (unfoldr f b)<br>
= foldr c n (build (unfoldrB f b))<br>
= unfoldrB f b c n</p>
<p dir="ltr">The list is gone, and there are no new closures or data structures in its place.</p>
<p dir="ltr">As a side benefit, we could write groupBy as an unfoldr, and make it a somewhat better producer, especially when the groups are small. I don't *think* there's any way to make groupBy a good consumer for foldr/build, unfortunately.</p>






</blockquote></div>
</div></div><br></div></div>_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank">Libraries@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/libraries" target="_blank">http://www.haskell.org/mailman/listinfo/libraries</a><br>
<br></blockquote></div><br></div>
<br>_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org">Libraries@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/libraries" target="_blank">http://www.haskell.org/mailman/listinfo/libraries</a><br>
<br></blockquote></div><br></div>