[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:              |          Version:  7.9
  libraries/base                     |         Keywords:
            Resolution:              |     Architecture:  Unknown/Multiple
      Operating System:              |       Difficulty:  Project (more
  Unknown/Multiple                   |  than a week)
       Type of failure:              |       Blocked By:
  None/Unknown                       |  Related Tickets:
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------

Comment (by dfeuer):

 === Progress ===

 Dan Doel has made a lot of progress implementing `foldrW/buildW` versions
 of major list-processing functions, with a drop of help from me. I've done
 some work on refactoring and rewrite rules. The `foldM` implementation
 seems to need the monadic right identity law, `m >>= return = m`, to be
 implemented in `RULES` in order to get clean Core for the general case
 (inlining may clean it up at some point for specific instances). I really
 hope no one is breaking this law.

 === Challenges ===

 The `buildWForgetful` thing is now fairly clearly the wrong way to go. It
 seems fine if a "static" producer is tied directly to a pure consumer, but
 if it's tied to a transformer, bugs go flying everywhere. It therefore
 seems likely to need some help from the compiler to clean up these static
 args.

 The current SAT criterion for what should be transformed is ''not''
 sufficient to clean up the static args `foldrW/buildW` sometimes produces.
 In particular, SAT currently will ''only'' touch functions with at least
 two static args, which these generally don't. It may be possible to find
 other criteria for SAT being likely to be good. One particularly obnoxious
 situation I've seen a couple times is a static argument whose value is
 actually known at compile time. For example, the "index too large or list
 empty" error message gets passed around through the recursion in `(!!)`. I
 don't think preserving that sort of static argument can ''ever'' be good.

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