## Wednesday, 2 May 2012

### Home grown iterate function

The next exercise is to duplicate the function iterate, which takes a function f and a starting value x and returns a lazy list of x, (f x), (f (f x)), (f (f (f x))) etc. For example:-

`user=> (take 10 (iterate inc 99)) `
`(99 100 101 102 103 104 105 106 107 108)`

The un-lazy version would look like this:-

```(defn my-iterate-1 [f x] (cons x (my-iterate-1 f (f x))))```

This will not work, or, rather, it works too well and does not know how to stop:-

```user=> (take 10 (my-iterate-1 inc 99)) StackOverflowError   clojure.lang.Numbers\$LongOps.inc (Numbers.java:510)```

What we really want is this:-

```(defn my-iterate-2 [f x] (lazy-seq (cons x (my-iterate-2 f (f x)))))```

```user=> (take 10 (my-iterate-2 inc 99)) (99 100 101 102 103 104 105 106 107 108)```

To create a recursive anonymous version of the function we write it like this:-

```(fn this [f x]   (lazy-seq     (cons x (this f (f x)))))```

Then it can be slotted into the examples on 4Clojure.

The other obvious possible solution is not lazy:-

```(defn my-iterate-3 [f x] (lazy-seq (conj (my-iterate-3 f (f x)) x)))```

```user=> (take 10 (my-iterate-3 inc 99)) StackOverflowError   user/my-iterate-3/fn--90 (myiterate.clj:11)```