Am I missing something about unfoldr?

[Michael Snoyman]

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 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
>>
>>
>
> _______________________________________________
> 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/20140727/8f818460/attachment.html>