Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Fibonacci numbers in Clojure

I'm learning Clojure. Quite basic task is to generate Fibonacci sequence. I end up with pretty much copy of the imperative solution (and list is reversed, huh):

(defn n-fib [n]
  (if (= n 1) '(1)
  (loop [i 2 l '(1 1)]
    (if (= i n)
        l
        (recur (inc i) (cons (+ (fst l) (snd l)) l))))))

What is the better way, more functional, concise? Lazy sequences? How to use them? For example, in Haskell using laziness I can write one liner:

fib = 1 : 1 : zipWith + (tail fib) 

Note that Haskell solution offers infinite sequence (laziness...). If Clojure both eager and lazy solutions can be (even like get n-length list) I would like to know both.

Update: Another solution I got yields not reversed list, but it uses stack to generate it:

(defn n-fib [n]
  (defn gen [i a b]
    (if (= i 0)
        ()
        (cons (+ a b) (gen (dec i) b (+ a b)))))
  (gen n 0 1))
like image 810
demi Avatar asked Jul 08 '13 02:07

demi


1 Answers

You might want to look at http://en.wikibooks.org/wiki/Clojure_Programming/Examples/Lazy_Fibonacci

The equivalent to your lazy Haskell solution is this

 (def fib (lazy-cat [1 1] (map + (rest fib) fib)))
like image 149
Joe Lehmann Avatar answered Oct 08 '22 14:10

Joe Lehmann