#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