Limpiar la función Clojure

Question

Viniendo de los lenguajes de programación imperativos, estoy tratando de abarcar Clojure con la esperanza de usarlo para su capacidad de multi-threading.
Uno de los problemas de 4Clojure es escribir una función que genera una lista de números de Fibonacci de longitud N, para N> 1. Escribí una función, pero dado mi limitado historial, me gustaría obtener alguna información sobre si esto o no es la mejor forma de hacer las cosas en Clojure. El código es el siguiente:

(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

Ésta es una forma de hacerlo que le da un poco de la exposición a las secuencias perezosos, aunque ciertamente no es realmente una manera óptima de cálculo de la sucesión de Fibonacci.

Dada la definición de la secuencia de Fibonacci, podemos ver que se ha creado aplicando repetidamente la misma regla al caso base de '(1 1). La función Clojure iterate suena como que sería bueno para esto:

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 

Así que para nuestra función nos gustaría algo que toma los valores que hemos computa hasta ahora, suma los dos más recientes, y devuelve una lista del nuevo valor y todos los valores anteriores.

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

La lista de argumentos aquí sólo significa que x y y estará atado a los dos primeros valores de la lista se pasa como argumento de la función, una lista que contiene todos los argumentos después de los dos primeros estará obligado a _, y la lista original aprobada como argumento para la función se puede consultar a través del all.

Ahora, iterate devolverá una secuencia infinita de valores intermedios, por lo que para nuestro caso, querremos envolverlo en algo que simplemente devuelva el valor que nos interesa; la evaluación diferida detendrá la secuencia infinita completa que se evalúa.

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

Tenga en cuenta también que esto devuelve el resultado en el orden opuesto a su implementación; es una cuestión simple arreglar esto con reverse, por supuesto.

Editar: o, de hecho, como dice amalloy, mediante el uso de vectores:

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

Answer 2

que aquí hay una versión de Fibonacci que me gusta mucho (Tomé la aplicación de la wikilibro clojure: http://en.wikibooks.org/wiki/Clojure_Programming)

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

Funciona así: imagine que ya tiene la secuencia infinita de números de Fibonacci. Si se toma la cola de la secuencia y la agrega elemento a elemento de la secuencia original se obtiene el (cola de la cola de la) Secuencia de Fibonacci

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

por lo tanto se puede usar esto para calcular la secuencia. Necesitas dos elementos iniciales [0 1] (o [1 1] dependiendo de dónde comiences la secuencia) y luego trazas las dos secuencias que suman los elementos. Tenga en cuenta que necesita secuencias perezosas aquí.

Creo que esta es la implementación más elegante y (al menos para mí) de estiramiento mental.

Editar: La función fib es

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

Answer 3

La forma más idiomática "funcional" sería probablemente para crear una secuencia de perezoso infinito de números de Fibonacci y luego extraer los primeros valores de n, es decir:

(take n some-infinite-fibonacci-sequence) 

El siguiente enlace tiene algunas maneras muy interesantes de la generación de Fibonnaci secuencias a lo largo de esas líneas:

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

Finalmente aquí es otra implementación diversión a tener en cuenta:

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

No es tan concisa como podría ser, pero demuestra bastante bien el uso de desestructuración de Clojure, secuencias perezosos y funciones de orden superior para resolver el problema.

Answer 4

solución de Fibonacci Ver Christophe Grand de Programación Clojure por Stu Halloway. Es la solución más elegante que he visto.

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

ver también

How can I generate the Fibonacci sequence using Clojure?