GitLab

Marge Bot pushed to branch master at Glasgow Haskell Compiler / GHC

Commits:

003b715b

by meooow25 at 2025-09-02T23:48:51+02:00

Adjust the strictness of Data.List.iterate'

* Don't force the next element in advance when generating a (:).
* Force the first element to WHNF like every other element.

Now every element in the output list is forced to WHNF when the (:)
containing it is forced.

CLC proposal:
https://github.com/haskell/core-libraries-committee/issues/335

2 changed files:

libraries/base/changelog.md
libraries/ghc-internal/src/GHC/Internal/List.hs

Changes:

libraries/base/changelog.md

@@ -8,6 +8,7 @@
    * `GHC.Exts.IOPort#` and its related operations have been removed  ([CLC #213](https://github.com/haskell/core-libraries-committee/issues/213))
    * Fix bug where `naturalAndNot` was incorrectly truncating results ([CLC proposal #350](github.com/haskell/core-libraries-committee/issues/350))
    * Remove extra laziness from `Data.Bifunctor.Bifunctor` instances for all tuples to have the same laziness as their `Data.Functor.Functor` counterparts (i.e. they became more strict than before) ([CLC proposal #339](https://github.com/haskell/core-libraries-committee/issues/339))
 +  * Adjust the strictness of `Data.List.iterate'` to be more reasonable: every element of the output list is forced to WHNF when the `(:)` containing it is forced. ([CLC proposal #335)](https://github.com/haskell/core-libraries-committee/issues/335)
  ## 4.22.0.0 *TBA*
    * Shipped with GHC 9.14.1

libraries/ghc-internal/src/GHC/Internal/List.hs

@@ -854,11 +854,17 @@ minimum xs              =  foldl1' min xs
  -- ==== __Laziness__
  --
  -- Note that 'iterate' is lazy, potentially leading to thunk build-up if
 --- the consumer doesn't force each iterate. See 'iterate'' for a strict
 +-- the consumer doesn't force each element. See 'iterate'' for a strict
  -- variant of this function.
  --
 --- >>> take 1 $ iterate undefined 42
 --- [42]
 +-- >>> let xs = iterate (\x -> if x == 0 then undefined else x - 1) 2
 +-- >>> xs
 +-- [2,1,0,*** Exception: Prelude.undefined
 +-- >>> length (take 10 xs)
 +-- 10
 +--
 +-- In @xs@ every element following @0@ is bottom, but the list itself is
 +-- infinitely long because it is generated without forcing its elements.
  --
  -- ==== __Examples__
  --
@@ -889,24 +895,26 @@ iterateFB c f x0 = go x0
  -- | 'iterate'' is the strict version of 'iterate'.
  --
 --- It forces the result of each application of the function to weak head normal
 --- form (WHNF)
 --- before proceeding.
 +-- It forces each element to weak head normal form (WHNF) before proceeding.
  --
 --- >>> take 1 $ iterate' undefined 42
 +-- ==== __Laziness__
 +--
 +-- >>> let xs = iterate' (\x -> if x == 0 then undefined else x - 1) 2
 +-- >>> xs
 +-- [2,1,0*** Exception: Prelude.undefined
 +-- >>> length (take 10 xs)
  -- *** Exception: Prelude.undefined
 +--
 +-- The list @xs@ has 3 elements followed by a tail that is bottom.
 +--
  {-# NOINLINE [1] iterate' #-}
  iterate' :: (a -> a) -> a -> [a]
 -iterate' f x =
 -    let x' = f x
 -    in x' `seq` (x : iterate' f x')
 +iterate' f !x = x : iterate' f (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')
 +  where go !x = x `c` go (f x)
  {-# RULES
  "iterate'"    [~1] forall f x.   iterate' f x = build (\c _n -> iterate'FB c f x)