Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How would you (re)implement iterate in Haskell?

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)

like image 248
Andrei Ciobanu Avatar asked Sep 22 '10 13:09

Andrei Ciobanu


2 Answers

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.

like image 124
emi Avatar answered Nov 16 '22 03:11

emi


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.

like image 41
sclv Avatar answered Nov 16 '22 03:11

sclv