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)

Grille

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.

Rauscher

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 :) – Scatterbrain

Answer 2

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.

Desiderate

Answer 3

You've already been given the simplest possible implementation of it; however, there are other ways.

One way is to use a higher order function, like so:

import Data.List (unfoldr)

iterate f x = unfoldr (\x -> Just (x, f x)) x

The function unfoldr is a higher-order function meant for creating lists. Here's the most straightforward implementation of it:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr step b = case step b of 
  Nothing -> []
  Just (a, b') -> a : unfoldr step b'

In the same way that foldr abstracts of the direct recursion of reducing lists, unfoldr abstracts over the direct recursion of creating them.

Hanker