Pulizia funzione Clojure

Question

Provenendo da linguaggi di programmazione imperativi, sto cercando di avvolgere la mia mente attorno a Clojure nella speranza di usarlo per le sue funzionalità di multi-threading.
Uno dei problemi da 4Clojure è scrivere una funzione che genera un elenco di numeri di Fibonacci di lunghezza N, per N> 1. Ho scritto una funzione, ma dato il mio background limitato, vorrei qualche input sul fatto se questo è il miglior modo Clojure di fare le cose. Il codice è il seguente:

(fn fib [x] (cond 
       (= x 2) '(1 1) 
      :else (reverse (conj (reverse (fib (dec x))) (+ (last (fib (dec x))) (-> (fib (dec x)) reverse rest first)))) 
     )) 

Answer 1

Ecco un modo di farlo che ti dà un po 'di esposizione a sequenze pigri, anche se non è certamente in realtà un modo ottimale di calcolare la sequenza di Fibonacci.

Data la definizione della sequenza di Fibonacci, possiamo vedere che è costruita applicando ripetutamente la stessa regola al caso base di '(1 1). La funzione Clojure iterate suona come sarebbe bene per questo:

user> (doc iterate) 
------------------------- 
clojure.core/iterate 
([f x]) 
    Returns a lazy sequence of x, (f x), (f (f x)) etc. f must be free of side-effects 

Quindi per la nostra funzione vorremmo qualcosa che richiede i valori che abbiamo calcolata finora, riassume i due più recenti, e restituisce una lista del nuovo valore e tutti i vecchi valori.

(fn [[x y & _ :as all]] (cons (+ x y) all)) 

L'elenco degli argomenti qui significa semplicemente che x e y saranno vincolati ai primi due valori della lista passata come argomento della funzione, una lista contenente tutti gli argomenti dopo i primi due verrà associato al _, e l'elenco originale passato come argomento alla funzione può essere riferito a all.

Ora, iterate restituirà una sequenza infinita di valori intermedi, quindi per il nostro caso vorremmo racchiuderlo in qualcosa che restituisca solo il valore a cui siamo interessati; la valutazione lazy interromperà l'intera sequenza infinita valutata.

(defn fib [n] 
    (nth (iterate (fn [[x y & _ :as all]] (cons (+ x y) all)) '(1 1)) (- n 2))) 

Si noti inoltre che questo restituisce il risultato nell'ordine opposto all'implementazione; è semplice risolvere il problema con reverse ovviamente.

Edit: o addirittura, come amalloy dice, utilizzando vettori:

(defn fib [n] 
    (nth (iterate (fn [all] 
        (conj all (->> all (take-last 2) (apply +)))) [1 1]) 
     (- n 2))) 

Answer 2

Ecco una versione di Fibonacci che mi piace molto (ho preso l'attuazione del wikibook clojure: http://en.wikibooks.org/wiki/Clojure_Programming)

(def fib-seq (lazy-cat [0 1] (map + (rest fib-seq) fib-seq))) 

Funziona così: Immagina di avere già la sequenza infinita di numeri di Fibonacci. Se si prende la coda della sequenza e aggiungerlo elemento-saggio alla sequenza originale si ottiene la (coda della coda del) Fibonacci

0 1 1 2 3 5 8 ... 
1 1 2 3 5 8 ... 
----------------- 
1 2 3 5 8 13 ... 

quindi è possibile utilizzare questo per calcolare la sequenza. Sono necessari due elementi iniziali [0 1] (o [1 1] a seconda di dove si avvia la sequenza) e quindi si esegue la mappatura sulle due sequenze aggiungendo gli elementi. Nota che hai bisogno di sequenze pigre qui.

Penso che questa sia l'implementazione di stretching mentale più elegante e (almeno per me).

Edit: La funzione fib è

(defn fib [n] (nth fib-seq n)) 

Answer 3

Il modo più idiomatica "funzionale" sarebbe probabilmente per creare una sequenza pigro infinita di numeri di Fibonacci e quindi estrarre i primi n valori, vale a dire:

(take n some-infinite-fibonacci-sequence) 

La seguente Link ha alcuni modi molto interessanti per generare sequenze di Fibonacci lungo queste linee:

http://en.wikibooks.org/wiki/Clojure_Programming/Examples/Lazy_Fibonacci

Infine ecco un altro divertente applicazione da considerare:

(defn fib [n] 
    (let [next-fib-pair (fn [[a b]] [b (+ a b)]) 
     fib-pairs (iterate next-fib-pair [1 1]) 
     all-fibs (map first fib-pairs)] 
    (take n all-fibs))) 


(fib 6) 
=> (1 1 2 3 5 8) 

Non è così conciso come potrebbe essere, ma dimostra molto bene l'uso di destrutturazione di Clojure, sequenze pigri e funzioni di ordine superiore per risolvere il problema.

Answer 4

Vedere la soluzione Fibonacci di Christophe Grand in Programmazione Clojure di Stu Halloway. È la soluzione più elegante che abbia mai visto.

(defn fibo [] (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1]))) 
(take 10 (fibo)) 

vedere anche

How can I generate the Fibonacci sequence using Clojure?