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. 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. 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. 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. 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 mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0x4743206C Debian Developer: nomeata@debian.org