Extending fold/build fusion

[Joachim Breitner]

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 at joachim-breitner.de • http://www.joachim-breitner.de/
  Jabber: nomeata at joachim-breitner.de  • GPG-Key: 0x4743206C
  Debian Developer: nomeata at debian.org
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 181 bytes
Desc: This is a digitally signed message part
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20140128/8989e566/attachment.sig>