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