Clojure Programming/Examples/Lazy Fibonacci

From Wikibooks, the open-content textbooks collection

Jump to: navigation, search

A function which lazily produces Fibonacci numbers:

(defn fib
  ([] (concat [0 1] (fib 0 1)))
  ([a b] (lazy-cons (+ a b) (fib b (+ a b)))))
 
user> (take 20 (fib))
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

Rich gives a better solution. Name a sequence that is seeded with [0 1] and forego the function so that instead of starting over with each call, you get a "cached infinite seq, lazily extended."

(def fib-seq
  (concat
   [0 1]
   ((fn rfib [a b]
        (lazy-cons (+ a b) (rfib b (+ a b)))) 0 1)))
 
user> (take 20 fib-seq)
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

Slight variant on Rich's that gets rid of the initial concat, while being (I think) clearer to understand :

(def fib-seq 
  ((fn rfib [a b] 
       (lazy-cons a (rfib b (+ a b)))) 
    0 1))
 
user> (take 20 fib-seq)
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)


[edit] Recursive Version

A version with recursion on data, not functions. see http://en.wikipedia.org/wiki/Corecursion :

(def fib-seq
     (lazy-cat [0 1] (map + (rest fib-seq) fib-seq)))
 
 
user> (take 20 fib-seq)
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)


[edit] Properly Scoped Version

Finally, there might be a problem in the 4 precedent versions : they create fibonacci lazy-sequences that are bound to top level vars. And as such they are not garbage collected, and if used to compute a very long sequence, will consume a lot of heap. It could be smarter to define fib-seq as a no-arg function that will return a lazy-seq on demand. Then the lazy seq could be put by the caller in the appropriate scope (hopefully not the top level scope) :

(defn fib-seq []
  ((fn rfib [a b] 
       (cons a (lazy-seq (rfib b (+ a b)))))
    0 1))
 
user> (take 20 (fib-seq))
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

[edit] Using iterate

We can use iterate to generate pairs of [a b] and then take the first of each one.

(defn fib-step [ab]
  [(last ab) (+ (first ab) (last ab))])
 
(defn fib-seq []
  (map first (iterate fib-step [0 1])))
 
user> (take 20 (fib-seq))
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)
Retrieved from "http://en.wikibooks.org/wiki/Clojure_Programming/Examples/Lazy_Fibonacci"