David, and other Haskell library folk
You’ve been doing lots of work on making more Prelude functions fusible – thank you!
This is really a library question, so I have not been following the details of the discussion, but I hope Edward and the Core Libraries Committee have been doing so; I’m cc’ing them.
I’m more than happy to help with any questions if you all get stuck.
Don’t forget to update the user manual
http://www.haskell.org/ghc/docs/latest/html/users_guide/rewrite-rules.html#i...
to say which functions are good producers/consumers. Actually, it might be better instead to state this in their Haddock comments, and remove or shrink this section of the user manual instead. It’s very hard to keep it up to date. I think it pre-dates Haddock.
Many thanks.
Simon
From: Libraries [mailto:libraries-bounces@haskell.org] On Behalf Of Michael Snoyman
Sent: 27 July 2014 06:08
To: Carter Schonwald
Cc: Haskell Libraries
Subject: Re: Am I missing something about unfoldr?
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 mailto:carter.schonwald@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 mailto:david.feuer@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" mailto: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 -> 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.orgmailto:Libraries@haskell.org
http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
Libraries@haskell.orgmailto:Libraries@haskell.org
http://www.haskell.org/mailman/listinfo/libraries
