[GHC] #9545: Evaluate Takano Akio's foldrW/buildW fusion framework as a possible replacement for foldr/build

[GHC]

#9545: Evaluate Takano Akio's foldrW/buildW fusion framework as a possible
replacement for foldr/build
-------------------------------------+-------------------------------------
       Reporter:  dfeuer             |                   Owner:
           Type:  task               |                  Status:  new
       Priority:  normal             |               Milestone:
      Component:  libraries/base     |                 Version:  7.9
       Keywords:                     |        Operating System:
   Architecture:  Unknown/Multiple   |  Unknown/Multiple
     Difficulty:  Project (more      |         Type of failure:
  than a week)                       |  None/Unknown
     Blocked By:                     |               Test Case:
Related Tickets:                     |                Blocking:
                                     |  Differential Revisions:
-------------------------------------+-------------------------------------
 Takano Akio's [https://github.com/takano-akio/ww-fusion 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 `build`s.

 That said, `foldrW/buildW` probably has its weaknesses too. The basic
 fusion rule looks like this.

 {{{#!hs
 {-# 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.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9545>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler