Evaluate Takano Akio's foldrW/buildW fusion framework as a possible replacement for foldr/build
Takano Akio's worker-wrapper fusion modifies foldr/build
fairly conservatively to allow safe fusion of foldl
and friends without relying on arity analysis. This advantage is important for two reasons that I know of:
- As discussed in Joachim Breitner's original paper, the current arity analysis is unable to infer arity correctly when facing certain forms of recursion.
- The current arity analysis, and probably any practical arity analysis, depends on inlining to a degree that can sometimes be unhealthy. I would love to make functions like
hPutStr
fuse, but I suspect doing so safely at present would likely cause a code explosion—the function being folded is too large to want to inline to make it available for arity analysis following fusion.
I don't understand it completely yet, but it looks like foldrW/buildW
can eliminate a lot of this uncertainty. Furthermore, it appears that functions currently written using foldr
in a "right-handed" way can remain unchanged, using an implementation of foldr
in terms of foldrW
. Only "left-handed" folds will need to be rewritten to take advantage of this framework, along with all the build
s.
That said, foldrW/buildW
probably has its weaknesses too. The basic fusion rule looks like this.
{-# RULES
"foldrW/buildW" forall
f z
(i :: Wrap f b)
(g :: forall c g .
(Wrap g c)
-> (a -> c -> c)
-> c
-> c)
.
foldrW i f z (buildW g) = g i f z
#-}
If g
and i
are not inlined sufficiently to merge with each other, I imagine this could produce worse results than foldr/build
when the latter works properly. The only way to really get a feel for performance would be to carefully modify everything to work as well as it can with this framework and see how the results compare.
Trac metadata
Trac field | Value |
---|---|
Version | 7.9 |
Type | Task |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | libraries/base |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | ekmett, hvr |
Operating system | |
Architecture |