This post picks up from where we left off here, in which I explained anamorphisms.  Here we look at another example of applying unfolds: iterate. 

Iterate

Iterate is one of the most common uses of unfold.  The definition of the iterate function is:

iterate f x = Cons (x, iterate f (f x))

E.g., let f x = 2x, the result of iterate f 1 is the following list:

1, Cons (f 1, iterate f (f 1))

-> 1, 2, Cons (f 2, iterate f (f2))

-> 1, 2, 4, Cons (f 4, iterate f (f 4))

-> 1, 2, 4, 8, …

To write this in terms of unfold, we have to determine the predicate (p) and the function (g) unfold requires.  Recall the definition of unfold:

Given

(1) a predicate p which returns a bool. I.e., p b = true or p b = false.

(2) a function g which returns a pair (a, b’).  I.e., g b = (a, b’).

A list-anamorphism h is

When p b = true, h b = Nil,

otherwise, h b = Cons (a, h b’).

For iterate, let p = false and g c = (c, f c), putting these in the definition of unfold:

h b  = Cons (b, h (f b)).  Because

• p b = false for all b, so h b = Nil never happens and can be omitted.
• g b = (b, f b), h b = Cons (b, h (f b) because
  
  • a  (in the definition) = b and
    
  • b’ (in the definition) = f b.

Therefore, h with p = false and g c = (c, f c) gives the iterate function!

Iterate in Haskell

In Haskell, iterate is already in Prelude.  As explained in Data.List, the iterate function is written using unfold:

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

To get the example list above, we pass the function f and the input to h (b) to iterate:

iterate (\x -> 2 * x) 1

In ghci, the list just goes on and on!  That’s because when the predicate is always false, we get an infinite list!  To see the first few elements of the list more easily, we can take the first 5 elements:

Prelude Data.List> take 5 (iterate (\x -> 2 * x) 1)
[1,2,4,8,16]

We can also write our own iterate with a predicate:

Prelude Data.List>  iterate_p f = unfoldr (\x -> if x > 20 then Nothing else Just (x, f x))
Prelude Data.List> iterate_p (\x -> 2* x) 1
[1,2,4,8,16]

Iterate in OCaml

In OCaml, we can use the unfold function we wrote in the last post and write iterate (with p = false) and iterate_p (with p = (x > 20)):

 Let’s pass the inputs to iterate to get the example list above:

utop # iterate (fun x -> 2 * x) 1;;
Stack overflow during evaluation (looping recursion?).

Oops!  We get a stack overflow error!  Because OCaml is eager by default, it tells us that there is a never ending loop as it runs out of stack.  If we give unfold a predicate, the list can end:

utop # iterate_p (fun x -> 2 * x) 1;;
- : int list = [1; 2; 4; 8; 16]

Unfolds abstract the recursion of building up a list from the input(s). Isn’t it cool?  We will see in a later post that unfolds can be combined with folds and create even more powerful functions.