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 (

*) unfold requires. Recall the definition of unfold:*

**g**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

*putting these in the definition of unfold:*

**g c = (c, f c)**,*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 (**to

*b)**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

*(with*

**iterate_p***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.

## Leave a Reply