Implementare Fibonacci in Clojure usando la mappa / ridurre

Question

E 'possibile per attuare le serie di Fibonacci in Clojure in modo efficiente utilizzando reduce? Quale sarebbe il "accumulatore" contenere?

I immaginare che dovrà essere pigro. E 'ovvio come farlo utilizzando la ricorsione o loop / ripresentarsi.

Answer 1

Si potrebbe utilizzare una coppia di valori di Fibonacci successivi come l'accumulatore, nel seguente modo:

(reduce 
  (fn [[a b] _] [b (+ a b)])  ; function to calculate the next pair of values
  [0 1]                       ; initial pair of fibonnaci numbers
  (range 10))                 ; a seq to specify how many iterations you want

=> [55 89]

Questo non è particolarmente efficiente grazie alla creazione di un sacco di coppie intermedi e uso della sequenza gamma superfluo guidare il giusto numero di iterazioni, ma è O (n) dal punto di vista algoritmico (cioè lo stesso del efficiente soluzione iterativa, e molto migliore di quella ricorsiva ingenuo).

Answer 2

Non usando la mappa / ridurre, ma iterazione può evitare la ricorsione troppo.

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

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

Questa operazione richiede 21 ms su un 2,4 Ghz Intel

Sulla stessa macchina, ridurre prende 61msec. Non capisco perché iterare è più veloce.

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

Answer 3

Questo darà un vettore di primi 1000 numeri di Fibonacci (dimensione range + 2), la manipolazione del secondo argomento della funzione (range) come contatore:

(reduce 
  (fn [a b] (conj a (+' (last a) (last (butlast a)))))  
  [0 1]                      
  (range 998))