#3474: Add a strict variant of iterate to Data.List
-----------------------------+----------------------------------------------
Reporter: mux | Owner:
Type: proposal | Status: new
Priority: normal | Component: libraries/base
Version: 6.10.4 | Severity: normal
Keywords: | Testcase:
Os: Unknown/Multiple | Architecture: Unknown/Multiple
-----------------------------+----------------------------------------------
I suggest adding a strict variant of the iterate function to the Data.List
module, as others seem to have had a need for it too. It is useful when
you want to repeatedly apply a function a large number of times and get
the final result. Using the standard iterate function in this way results
in the whole list being held in memory, as exemplified in the following
GHCi session (code compiled with -O2 behaves similarly):
> let f = (+1) in iterate f 0 !! 10000000
*** Exception: stack overflow
Using a strict variant of iterate seems to be sufficient for this code to
run in O(1) memory:
> let iterate' f x = x `seq` x : iterate' f (f x)
> let f = (+1) in iterate' f 0 !! 10000000
10000000
I have no idea if this is something that could/should be detected by the
strictness analyzer; that would obviously be preferable if it is indeed
possible.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3474>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
