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:

1. As discussed in Joachim Breitner's original paper, the current arity analysis is unable to infer arity correctly when facing certain forms of recursion.
2. 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 builds.

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