Fusion of list functions

[Simon Peyton Jones]

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#idp25099648
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 at 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 <carter.schonwald at gmail.com<mailto: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<mailto: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<mailto: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<mailto:Libraries at haskell.org>
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
Libraries at haskell.org<mailto: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/20140728/772e9a65/attachment-0001.html>