But that doesn't look like it's actually a problem. Expand the foldr and unfoldr one step each, apply case-of-case, and it looks like everything comes together nicely.
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" <david.feuer@gmail.com> 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 -> nunfoldr 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 nThe 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.