Am I missing something about unfoldr?

[David Feuer]

I think this is probably what Hinze et al, "Theory and Practice of Fusion"
describes as the fold/unfold law, "a fold after an unfold is a hylo" but I
don't know enough to read that paper.
On Jul 26, 2014 4:35 PM, "David Feuer" <david.feuer at gmail.com> wrote:

> 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" <carter.schonwald at 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 <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/82264bd5/attachment-0001.html>