Add strict variant of iterate

This closes the nearly-eight-year-old #3474.

4 files changed, 29 insertions, 1 deletions

diff --git a/libraries/base/Data/List.hs b/libraries/base/Data/List.hs
index 693c0dd151..2ac04a9165 100644
--- a/libraries/base/Data/List.hs
+++ b/libraries/base/Data/List.hs
@@ -76,6 +76,7 @@ module Data.List
 
    -- ** Infinite lists
    , iterate
+   , iterate'
    , repeat
    , replicate
    , cycle
diff --git a/libraries/base/Data/OldList.hs b/libraries/base/Data/OldList.hs
index d03c0bcc96..c4c38d4029 100644
--- a/libraries/base/Data/OldList.hs
+++ b/libraries/base/Data/OldList.hs
@@ -77,6 +77,7 @@ module Data.OldList
 
    -- ** Infinite lists
    , iterate
+   , iterate'
    , repeat
    , replicate
    , cycle
diff --git a/libraries/base/GHC/List.hs b/libraries/base/GHC/List.hs
index 70bfbe4de0..ca95379226 100644
--- a/libraries/base/GHC/List.hs
+++ b/libraries/base/GHC/List.hs
@@ -23,7 +23,7 @@ module GHC.List (
    map, (++), filter, concat,
    head, last, tail, init, uncons, null, length, (!!),
    foldl, foldl', foldl1, foldl1', scanl, scanl1, scanl', foldr, foldr1,
-   scanr, scanr1, iterate, repeat, replicate, cycle,
+   scanr, scanr1, iterate, iterate', repeat, replicate, cycle,
    take, drop, sum, product, maximum, minimum, splitAt, takeWhile, dropWhile,
    span, break, reverse, and, or,
    any, all, elem, notElem, lookup,
@@ -458,6 +458,29 @@ iterateFB c f x0 = go x0
  #-}
 
 
+-- | 'iterate\'' is the strict version of 'iterate'.
+--
+-- It ensures that the result of each application of force to weak head normal
+-- form before proceeding.
+{-# NOINLINE [1] iterate' #-}
+iterate' :: (a -> a) -> a -> [a]
+iterate' f x =
+    let x' = f x
+    in x' `seq` (x : iterate' f x')
+
+{-# INLINE [0] iterate'FB #-} -- See Note [Inline FB functions]
+iterate'FB :: (a -> b -> b) -> (a -> a) -> a -> b
+iterate'FB c f x0 = go x0
+  where go x =
+            let x' = f x
+            in x' `seq` (x `c` go x')
+
+{-# RULES
+"iterate'"    [~1] forall f x.   iterate' f x = build (\c _n -> iterate'FB c f x)
+"iterate'FB"  [1]                iterate'FB (:) = iterate'
+ #-}
+
+
 -- | 'repeat' @x@ is an infinite list, with @x@ the value of every element.
 repeat :: a -> [a]
 {-# INLINE [0] repeat #-}
diff --git a/libraries/base/changelog.md b/libraries/base/changelog.md
index ab304a317f..a62b833920 100644
--- a/libraries/base/changelog.md
+++ b/libraries/base/changelog.md
@@ -16,6 +16,9 @@
 
   * Add instances `Semigroup` and `Monoid` for `Control.Monad.ST` (#14107).
 
+  * Add `iterate'`, a strict version of `iterate`, to `Data.List`
+    and `Data.OldList` (#3474)
+
 ## 4.10.0.0 *April 2017*
   * Bundled with GHC *TBA*