Make mapAccumL a good consumer
authorDavid Feuer <David.Feuer@gmail.com>
Wed, 1 Oct 2014 13:42:27 +0000 (15:42 +0200)
committerJoachim Breitner <mail@joachim-breitner.de>
Wed, 1 Oct 2014 16:20:26 +0000 (18:20 +0200)
This fixes #9502.

libraries/base/Data/OldList.hs
libraries/base/changelog.md

index fe0f38e..9b6a431 100644 (file)
@@ -481,11 +481,28 @@ mapAccumL :: (acc -> x -> (acc, y)) -- Function of elt of input list
           -> acc            -- Initial accumulator
           -> [x]            -- Input list
           -> (acc, [y])     -- Final accumulator and result list
+{-# NOINLINE [1] mapAccumL #-}
 mapAccumL _ s []        =  (s, [])
 mapAccumL f s (x:xs)    =  (s'',y:ys)
                            where (s', y ) = f s x
                                  (s'',ys) = mapAccumL f s' xs
 
+{-# RULES
+"mapAccumL" [~1] forall f s xs . mapAccumL f s xs = foldr (mapAccumLF f) pairWithNil xs s
+"mapAccumLList" [1] forall f s xs . foldr (mapAccumLF f) pairWithNil xs s = mapAccumL f s xs
+ #-}
+
+pairWithNil :: acc -> (acc, [y])
+{-# INLINE [0] pairWithNil #-}
+pairWithNil x = (x, [])
+
+mapAccumLF :: (acc -> x -> (acc, y)) -> x -> (acc -> (acc, [y])) -> acc -> (acc, [y])
+{-# INLINE [0] mapAccumLF #-}
+mapAccumLF f = \x r s -> let (s', y)   = f s x
+                             (s'', ys) = r s'
+                         in (s'', y:ys)
+
+
 -- | The 'mapAccumR' function behaves like a combination of 'map' and
 -- 'foldr'; it applies a function to each element of a list, passing
 -- an accumulating parameter from right to left, and returning a final
index c594c2f..09b749a 100644 (file)
@@ -77,7 +77,7 @@
     second argument, so that the fusion RULES for it do not change the
     semantics. (#9596)
 
-  * `scanr` now takes part in list fusion (#9355)
+  * `scanr` and `mapAccumL` now take part in list fusion (#9355, #9502)
 
 ## 4.7.0.1  *Jul 2014*