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)

 

No comments:

Post a Comment