Am I missing something about unfoldr?

[Carter Schonwald]

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 <david.feuer at gmail.com> 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" <david.feuer at 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 -> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20140726/9923941b/attachment.html>