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

7 Aug 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 dfeuer):

 Replying to [comment:2 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?
Sorry, I've been a tad confused, as usual. The problem, I now see, is the
 bunch of thunks we produce. I don't think it's possible to make `scanr` a
 good producer, and I'm not even sure we can make it a significantly better
 one (though I'd have to profile to be sure). What we ''can'' do, in an
 apparently incompatible fashion, is make it a good consumer. Start with
 the current tail-eating implementation:

 {{{#!hs
 scanr _ q0 [] = [q0]
 scanr f qo (x:xs) = f x q : qs
   where
     qs@(q:_) = scanr f q0 xs
 }}}

 Rewriting that pattern match thing more explicitly:

 {{{#!hs
 scanr f q0 (x:xs) = let qs = scanr f q0 xs
                     in f x (head qs) : qs
 }}}

 This, then is a plain old fold:

 {{{#!hs
 scanr f q0 = foldr go [q0] xs
   where
     go x qs = f x (head qs) : qs
 }}}

 If we apply it to a `build`, we get

 {{{#!hs
 scanr f q0 (build g) = g go [q0]
   where go x qs = f x (head qs):qs
 }}}

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