Re: Am I missing something about unfoldr?

Foldr/build fusion can't remove bottoms; it *can* add them. That's why we have to be very careful. I *think* we're safe in this case, though. On Jul 26, 2014 4:28 PM, "Carter Schonwald" 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