Clojure Programming/Examples/Lazy Fibonacci
A function which lazily produces Fibonacci numbers:
(def fib-seq
((fn rfib [a b]
(lazy-seq (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)
Recursive Version
[edit | edit source]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)
A different recursive version, making use of the reductions function. ... Does this work? NO. Seems a fake. See discussion.
(def fib-seq
(cons 1 (reductions + (first fib-seq) fib-seq)))
user> (take 20 fib-seq)
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)
Properly Scoped Version
[edit | edit source]There might be a problem in the 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)
Using iterate
[edit | edit source]We can use iterate to generate pairs of [a b] and then take the first of each one.
(defn fib-step [[a b]]
[b (+ a b)])
(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)
This example also uses destructuring.
Recursive Fibonacci with any start point and the amount of numbers that you want
[edit | edit source];; note that your 'start' parameter must be a vector with at least two numbers (the two which are your starting points)
(defn fib [start range]
"Creates a vector of fibonnaci numbers"
(if (<= range 0)
start
(recur (let[subvector (subvec start (- (count start) 2))
x (nth subvector 0)
y (nth subvector 1)
z (+ x y)]
(conj start z))
(- range 1))))
Self-Referential Version
[edit | edit source]Computes the Fibonacci sequence by mapping the sequence with itself, offset by one element.
(def fib (cons 0 (cons 1 (lazy-seq (map + fib (rest fib))))))