Clojure Programming/Examples/Lazy Fibonacci
A function which lazily produces Fibonacci numbers:
(deffib-seq ((fnrfib[ab] (lazy-seq(consa(rfibb(+ab))))) 01)) user>(take20fib-seq) (01123581321345589144233377610987159725844181)
Recursive Version
[edit | edit source ]A version with recursion on data, not functions. see http://en.wikipedia.org/wiki/Corecursion :
(deffib-seq (lazy-cat[01](map+(restfib-seq)fib-seq))) user>(take20fib-seq) (01123581321345589144233377610987159725844181)
A different recursive version, making use of the reductions function. ... Does this work? NO. Seems a fake. See discussion.
(deffib-seq (cons1(reductions+(firstfib-seq)fib-seq))) user>(take20fib-seq) (11235813213455891442333776109871597258441816765)
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) :
(defnfib-seq[] ((fnrfib[ab] (consa(lazy-seq(rfibb(+ab))))) 01)) user>(take20(fib-seq)) (01123581321345589144233377610987159725844181)
Using iterate
[edit | edit source ]We can use iterate to generate pairs of [a b] and then take the first of each one.
(defnfib-step[[ab]] [b(+ab)]) (defnfib-seq[] (mapfirst(iteratefib-step[01]))) user>(take20(fib-seq)) (01123581321345589144233377610987159725844181)
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) (defnfib[startrange] "Creates a vector of fibonnaci numbers" (if(<=range0) start (recur(let[subvector(subvecstart(-(countstart)2)) x(nthsubvector0) y(nthsubvector1) z(+xy)] (conjstartz)) (-range1))))
Self-Referential Version
[edit | edit source ]Computes the Fibonacci sequence by mapping the sequence with itself, offset by one element.
(deffib(cons0(cons1(lazy-seq(map+fib(restfib))))))