Re: Am I missing something about unfoldr?

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. On Sat, Jul 26, 2014 at 11:28 PM, Carter Schonwald < carter.schonwald@gmail.com> wrote:

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

On Sat, Jul 26, 2014 at 4:02 PM, David Feuer wrote:

...

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. On Jul 26, 2014 3:34 PM, "David Feuer" wrote:

...

The current definition:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a] unfoldr f b = case f b of Just (a,new_b) -> a : unfoldr f new_b Nothing -> []

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:

unfoldrB f b c n = go b where go b = case f b of Just (a,new_b) -> a `c` go new_b Nothing -> n

unfoldr f b = build (unfoldrB f b)

then we get some really nice fusion:

foldr c n (unfoldr f b) = foldr c n (build (unfoldrB f b)) = unfoldrB f b c n

The list is gone, and there are no new closures or data structures in its place.

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.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries