Hi Joachim, On Wed, Jan 29, 2014 at 3:06 AM, Joachim Breitner <[email protected]> wrote: > Dear Akio, > > Am Freitag, den 03.01.2014, 23:20 +0900 schrieb Akio Takano: >> I have been thinking about how foldl' can be turned into a good >> consumer, and I came up with something that I thought would work. So >> I'd like to ask for opinions from the ghc devs: if this idea looks >> good, if it is a known bad idea, if there is a better way to do it, >> etc. > > I'd like to evaluate your approach, but let me first note that I had > been working on #7994 (make foldl a good consumer), and with my patches > the compiler is smart enough to eta-expand go in all cases covered by > nofib, using the existing foldr/build-fusion.
Nice. > > That said, I do like your idea of making the worker/wrapper a bit more > explicit, instead of relying on the compiler to do the transformation > for us. So let's see in what ways your proposal surpasses a smarter GHC. > > > The Tree example is a good one, because there any form of eta expansion, > just as you write, will not help. And I find that that Simons's solution > of using a foldr-based sum for Trees unsatisfying: We should indeed aim > for "sum $ toList tree" to produce good results. Given that Data.Map is > a tree, and that is a common data structure and it's toList a good > producer, this is relevant. I agree. In fact, my original motivation was that I wanted to efficiently serialize a IntMap into a ByteString. > > > Can you implement build via buildW, so that existing code like > "map" [~1] forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs) > can be used unmodified? But probably not... but that would mean a > noticeable incompatibility and a burden on library authors using list > fusion. You can implement build in terms of buildW. However any list producer defined using that definition of build would produce good code if the final consumer is a left fold. The resulting code will be in CPS. On the other hand, I imagine that if we also annotate foldl with oneShot, this problem may become less severe. > > > In any case, I suggest you just dig in, create a branch of > libraries/base and replace everything related to foldr/builder with your > approach. First, do not actually change the definition of foldl. Then > compare the nofib testruns (probably best with two separate working repo > clones, starting from "make distclean"): Do the results differ? A lot of > work went into foldr/build-fusion, so we want to be sure that we are not > losing anything anywhere (or if we are, we want to know why). > > Then make foldl and foldl' a good consumer, as in the patch at the > beginning of #7994. How large are the gains? How do they compare with > the gains from the smarter GHC (numbers also in the ticket). > > If by then we have not found any regression, things look promising. Thank you for the advice, I'll have a try. - Akio > > Greetings, and I hope the delayed responses do not lesen your > motivation, > Joachim > > PS: I'm subscribed to the mailinglist, no need to CC me explicitly. > > -- > Joachim "nomeata" Breitner > [email protected] * http://www.joachim-breitner.de/ > Jabber: [email protected] * GPG-Key: 0x4743206C > Debian Developer: [email protected] _______________________________________________ ghc-devs mailing list [email protected] http://www.haskell.org/mailman/listinfo/ghc-devs
