<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">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><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

<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 class="HOEnZb"><div class="h5">


<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>_______________________________________________<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>