Re: [GHC] #9355: scanr does not participate in stream fusion

25 Jul 2014

      #9355: scanr does not participate in stream fusion
-------------------------------------+-------------------------------------
              Reporter:  dfeuer      |            Owner:
                  Type:  bug         |           Status:  new
              Priority:  normal      |        Milestone:  7.8.4
             Component:              |          Version:  7.8.3
  libraries/base                     |         Keywords:
            Resolution:              |     Architecture:  Unknown/Multiple
      Operating System:              |       Difficulty:  Moderate (less
  Unknown/Multiple                   |  than a day)
       Type of failure:  Runtime     |       Blocked By:
  performance bug                    |  Related Tickets:
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------

Comment (by nomeata):
...
(because the argument to build isn't allowed to inspect its own result
 as the implementation in Data.List does),
I wouldn’t be surprised that returning `(# x, x:xs #)` is faster than
 returning `x:xs` and pattern matching on it. OTOH, the CPR optimization
 should change the code returning `x:xs` into (# x,  xs #) and move the
 consing to the caller.

 Can’t  you do that by hand, i.e.:

 {{{
 scanrB :: forall a b . (a -> b -> b) -> b -> [a] -> [b]
 scanrB f q0 ls = build scr
   where
    scr :: forall c . (b -> c -> c) -> c -> c
    scr c n = case foldr go (q0, n) ls of (r, esult) -> c r esult
      where
        go x (r,est) = (f x r, r `c` est)
 }}}

 The Core looks a bit nicer:

 {{{
 Scanr.scanrA :: forall a b. (a -> b -> b) -> b -> [a] -> [b]
 Scanr.scanrA =
   \ (@ a) (@ b) (f :: a -> b -> b) (q0 :: b) (ls :: [a]) ->
     let {
       a :: [b]
       a = GHC.Types.: q0 (GHC.Types.[]) } in
     letrec {
       $wgo :: [a] -> (# b, [b] #)
       $wgo =
         \ (w :: [a]) ->
           case w of _ {
             [] -> (# q0, a #);
             : y ys ->
               case $wgo ys of _ { (# ww1, ww2 #) ->
               let {
                 fxr :: b
                 fxr = f y ww1 } in
               (# fxr, GHC.Types.: fxr ww2 #)
               }
           }; } in
     case $wgo ls of _ { (# _, ww2 #) -> ww2 }

 Scanr.scanrB :: forall a b. (a -> b -> b) -> b -> [a] -> [b]
 Scanr.scanrB =
   \ (@ a) (@ b) (f :: a -> b -> b) (q0 :: b) (ls :: [a]) ->
     letrec {
       $wgo :: [a] -> (# b, [b] #)
       $wgo =
         \ (w :: [a]) ->
           case w of _ {
             [] -> (# q0, GHC.Types.[] #);
             : y ys ->
               case $wgo ys of _ { (# ww1, ww2 #) ->
               (# f y ww1, GHC.Types.: ww1 ww2 #)
               }
           }; } in
     case $wgo ls of _ { (# ww1, ww2 #) -> GHC.Types.: ww1 ww2 }
 }}}

 But I don’t expect there to be a measurable difference (and I didn’t
 check):
...
Some extra rules may be needed for map, et al.
not sure what you mean by that?

--
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9355#comment:2
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler