#9356: scanl does not participate in stream fusion -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: Runtime | Blocked By: performance bug | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by dfeuer): * version: 7.8.2 => 7.8.3 Old description:

nomeata came up with a fusing version of a strict `scanl'` in a comment on #9345. It's not entirely clear to me whether that's entirely safe, but a non-strict version of it for `scanl` would be, as both a good producer and good consumer, presumably made efficient using the same sorts of magic used in HEAD for `foldl`. The strict `scanl'` is obviously safe to write as a good consumer; only the production side remains to be proved.

New description: nomeata came up with a fusable version of a strict `scanl'` in a comment on #9345 that uses the same basic technique as the new `foldl`. I think we should use something like the following non-strict version to replace the current `scanl`: {{{#!haskell scanl :: (b -> a -> b) -> b -> [a] -> [b] scanl f a bs = build $ \c n -> a `c` foldr (\b g x -> let b' = f x b in (b' `c` g b')) (const n) bs a }}} While we're at it, we should make sure that `map g . scanl f a` and `scanl f a . map g` fuse properly. -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9356#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9356: scanl does not participate in stream fusion -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: Runtime | Blocked By: performance bug | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): It looks like strictness analysis can work its magic in nice cases and unbox the accumulator, erasing the let. I think this is probably good to go. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9356#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9356: scanl does not participate in list fusion -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: Runtime | Blocked By: performance bug | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): It looks like the `concat/inits` issue is probably not a `scanl` issue in principle, and it should be safe enough to merge this patch. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9356#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9356: scanl does not participate in list fusion -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: Runtime | Blocked By: performance bug | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by dfeuer): * status: infoneeded => patch Comment: I added an explanation, and simplified some things. Phab:D314 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9356#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9356: scanl does not participate in list fusion -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: fixed | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: Runtime | Blocked By: performance bug | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by nomeata): * status: patch => closed * resolution: => fixed -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9356#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler