#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