Alex Rivera | Logout

Implement fibonacci in Clojure using map/reduce

Asked 2010-12-07T12:14:53.203
17

Is it possible to implement the fibonacci series in Clojure efficiently using reduce? What would the "accumulator" contain?

I imagine that it will have to be lazy. It's obvious how to do it using recursion or loop/recur.

clojure fibonacci reduce
Edit
Report

1 Answer

5

Not using map/reduce, but iterate can avoid recursion too.

(defn iter [[x y]]
  (vector y (+ x y)))

(nth (iterate iter [0 1]) 10000)

This takes 21ms on an Intel 2.4 Ghz

On the same machine, reduce takes 61msec. Not sure why iterate is faster.

   (time (reduce 
     (fn [[a b] _] [b (+ a b)])  ; function to calculate the next pair of values
     [0 1]                       ; initial pair of fibonnaci numbers
     (range 10000)))
answered 2011-09-24T05:20:52.223

Your Answer