12
iterate :: (a -> a) -> a -> [a]

(As you probably know) iterate is a function that takes a function and starting value. Then it applies the function to the starting value, then it applies the same function to the last result, and so on. 

Prelude> take 5 $ iterate (^2) 2
[2,4,16,256,65536]
Prelude>

The result is an infinite list. (that's why I use take). My question how would you implement your own iterate' function in Haskell, using only the basics ((:) (++) lambdas, pattern mataching, guards, etc.) ?

(Haskell beginner here)

Don Stewart
  • 137,316
  • 36
  • 365
  • 468
Andrei Ciobanu
  • 12,500
  • 24
  • 85
  • 118

2 Answers2

29

Well, iterate constructs an infinite list of values a incremented by f. So I would start by writing a function that prepended some value a to the list constructed by recursively calling iterate with f a:

iterate :: (a -> a) -> a -> [a]
iterate f a = a : iterate f (f a)

Thanks to lazy evaluation, only that portion of the constructed list necessary to compute the value of my function will be evaluated.

emi
  • 5,380
  • 1
  • 27
  • 45
  • This looks like the a variation of the "fix" definition "fix f = f (fix f)" similar to ..."iterate f (f a)" you could use fix to define iterate: "iterate f a = fix (\r x -> x:r (f x) ) a" not that its any better, just thought id say :) – QuantumKarl Aug 21 '15 at 11:42
15

Also note that you can find concise definitions for the range of basic Haskell functions in the report's Standard Prelude.

Reading through this list of straightforward definitions that essentially bootstrap a rich library out of raw primitives can be very educational and eye-opening in terms of providing a window onto the "haskell way".

I remember a very early aha moment on reading: data Bool = False | True.

sclv
  • 38,665
  • 7
  • 99
  • 204