[GHC] #9434: GHC.List.reverse does not fuse

[GHC]

#9434: GHC.List.reverse does not fuse
-------------------------------------+-------------------------------------
              Reporter:  dfeuer      |            Owner:
                  Type:  bug         |           Status:  new
              Priority:  normal      |        Milestone:
             Component:              |          Version:  7.9
  libraries/base                     |         Keywords:
            Resolution:              |     Architecture:  Unknown/Multiple
      Operating System:              |       Difficulty:  Easy (less than 1
  Unknown/Multiple                   |  hour)
       Type of failure:  Runtime     |       Blocked By:
  performance bug                    |  Related Tickets:
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------
Changes (by dfeuer):

 * status:  patch => new


Comment:

 Letting `reverse` fuse with `foldr` generally seems to be causing more
 than its fair share of problems, including issues relating to arity
 analysis. I've been working today on different implementations of
 `dropWhileEnd`. One I think seems particularly pleasant looks like this:

 {{{#!hs
 dropWhileEnd p xs = build (\c n -> foldr (dweFB p c) (const n) xs [])
 {-# INLINE dropWhileEnd #-}

 dweFB p c =
   \x r trues ->
     if p x
     then r (x : trues)
     else foldr c (x `c` r []) (reverse trues)
 }}}

 I tested this like so:

 {{{#!hs
 testDWE = foldl (*) 1 $ dropWhileEnd (>10) [1::Int .. 1000]
 }}}

 If `reverse` is prevented from fusing with `foldr`, this generates what
 looks to me like very good code (note: if you're looking at the Core, that
 inner `letrec` becomes a let-no-escape), generating far fewer conses and
 boxes than the current implementation, even if that one is made `INLINE`.
 If they're allowed to fuse, however, Call Arity fails to work its magic,
 and the result is a higher-order mess. So I think for now the answer is
 probably to just use something like the Report Prelude version that fuses
 with a `build` but not a `foldr`, and add a rule to exchange `map` with
 `reverse` in some fashion. I'll come up with a patch to do that shortly.
 Of course, if Joachim or someone can figure out a better solution or a
 better characterization of the problem, that'd be great.

 Side note: for reasons I can't begin to figure out, if the `foldl` above
 is replaced with `foldl'`, then it doesn't fuse at all.

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