Come si scrive questa funzione Clojure in modo che non esploda lo stack?

Question

Sono nuovo di Clojure e penso che il mio approccio alla scrittura del codice non sia in linea con la "Via del Clojure". Almeno, continuo a scrivere funzioni che continuano a portare a errori StackOverflow con valori elevati. Ho imparato a utilizzare Recur che è stato un buon passo avanti. Ma come far funzionare funzioni come quella sottostante per valori come 2500000?

(defn fib [i] 
    (if (>= 2 i) 
    1 
    (+ (fib (dec i)) 
     (fib (- i 2))))) 

La funzione è, ai miei occhi, l'implementazione "normale" di un generatore di Fibonacci. Ho visto altre implementazioni che sono molto più ottimizzate, ma meno ovvie in termini di ciò che fanno. Cioè quando leggi la definizione della funzione, non vai "oh, fibonacci".

Qualsiasi suggerimento sarebbe molto apprezzato!

Answer 1

È necessario disporre di un modello mentale di come funziona la funzione. Diciamo che esegui tu stesso la tua funzione, usando ritagli di carta per ogni invocazione. Per prima cosa, scrivi (fib 250000), poi vedi "oh, ho bisogno di calcolare (fib 249999) e (fib 249998) e finalmente li aggiungo", così lo noti e inizi due nuovi scrap. Non puoi buttare via il primo, perché ha ancora qualcosa da fare per te quando finisci gli altri calcoli. Potete immaginare che questo calcolo richiederà molti scrap.

Un altro modo non è quello di iniziare in alto, ma in basso. Come lo faresti a mano? Cominci con i primi numeri 1, 1, 2, 3, 5, 8 e hellip; e poi aggiungi sempre gli ultimi due, fino a quando non lo hai fatto i volte. Puoi persino eliminare tutti i numeri tranne gli ultimi due ad ogni passaggio, in modo da poter riutilizzare la maggior parte degli scrap.

(defn fib [i] 
    (loop [a 0 
     b 1 
     n 1] 
    (if (>= n i) 
     b 
     (recur b 
       (+ a b) 
       (inc n))))) 

Questa è anche un'implementazione abbastanza evidente, ma del come, non di ciò che il . Sembra sempre abbastanza elegante quando si può semplicemente scrivere una definizione e si trasforma automaticamente in un calcolo efficiente, ma la programmazione è quella trasformazione. Se qualcosa viene trasformato automaticamente, allora questo particolare problema è già stato risolto (spesso in un modo più generale).

Pensare "come farei questo passo dopo passo sulla carta" porta spesso a una buona implementazione.

Answer 2

Un generatore di Fibonacci implementato in modo "semplice", come nella definizione della sequenza, farà sempre esplodere il tuo stack. Nessuna delle due chiamate ricorsive a fib è ricorsiva in coda, tale definizione non può essere ottimizzata.

Sfortunatamente, se desideri scrivere un'implementazione efficiente che funzioni per grandi numeri, devi accettare il fatto che la notazione matematica non si traduce in codice in modo pulito come vorremmo.

Ad esempio, un'implementazione non ricorsiva può essere trovata in clojure.contrib.lazy-seqs. Un'intera gamma di vari approcci a questo problema può essere trovata su Haskell wiki. Non dovrebbe essere difficile da capire con la conoscenza delle basi della programmazione funzionale.

Answer 3

;;from "The Pragmatic Programmers Programming Clojure" 
(defn fib [] (map first (iterate (fn [[a b]][b (+ a b)])[0N 1N]))) 
(nth (fib) 2500000)