How would you (re)implement iterate in Haskell ?

Question

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)

Answer 1

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.

Answer 2

Also note that you can find concisedefinitions 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.