Czyszczenie funkcji Clojure

Question

Wychodząc z imperatywnych języków programowania, staram się owijać głowę wokół Clojure w nadziei, że użyję go do wielowątkowości.
Jednym z problemów z 4Clojure jest napisanie funkcji, która generuje listę liczb Fibonacciego o długości N, dla N> 1. Napisałem funkcję, ale biorąc pod uwagę moje ograniczone tło, chciałbym trochę informacji na temat tego, czy to nie jest jest najlepszym sposobem działania Clojure. Kod jest w następujący sposób:

(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

Oto jeden sposób z tym, że daje trochę ekspozycji na leniwe sekwencji, chociaż nie jest to na pewno bardzo optymalny sposób obliczania ciągu Fibonacciego.

Biorąc pod uwagę definicję sekwencji Fibonacciego, widzimy, że jest ona tworzona przez wielokrotne stosowanie tej samej reguły do ​​podstawowego przypadku '(1 1). Funkcja Clojure iterate brzmi jak byłoby to dobre dla:

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 

Więc dla naszej funkcji którą chcemy coś, co wyraża wartości obliczonych mamy tak daleko, kwoty dwóch ostatnich, i zwraca listę nowej wartości i wszystkich starych wartości.

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

Lista argumentów tutaj po prostu oznacza, że ​​x i y będzie związany z pierwszymi dwoma wartościami z listy przekazanej jako argument danej funkcji, wykaz zawierający wszystkie argumenty po pierwszych dwóch będzie zobowiązany do _ oraz oryginalna lista przekazana jako argument do funkcji może być określona przez all.

Teraz, iterate zwróci nieskończoną sekwencję wartości pośrednich, więc dla naszego przypadku będziemy chcieli zawinąć ją w coś, co po prostu zwróci wartość, która nas interesuje; leniwy ewaluacja zatrzyma całą nieskończoną sekwencję podlegającą ocenie.

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

Należy również zwrócić uwagę, że to zwraca wynik w odwrotnej kolejności do implementacji; Naprawdę łatwo to naprawić z reverse.

Edycja: czy rzeczywiście, jak mówi amalloy, za pomocą wektorów:

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

Answer 2

Oto wersja Fibonacciego, że bardzo mi się podoba (wziąłem realizację z Wikibook Clojure: http://en.wikibooks.org/wiki/Clojure_Programming)

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

Działa to tak: Wyobraź sobie, że masz już nieskończoną sekwencję liczb Fibonacciego. Jeśli wziąć ogon sekwencji i dodać element mądry do oryginalnej sekwencji można dostać się (ogon ogon) Fibonacciego

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

więc można to wykorzystać do obliczenia sekwencji. Potrzebujesz dwóch początkowych elementów [0 1] (lub [1 1] w zależności od tego, gdzie zaczynasz sekwencję), a następnie mapujesz po dwóch sekwencjach dodając elementy. Zauważ, że potrzebujesz tutaj leniwych sekwencji.

Myślę, że jest to najbardziej elegancki i (przynajmniej dla mnie) umysł rozciągający wdrożenie.

Edycja: Funkcja fib jest

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

Answer 3

Najbardziej idiomatycznym „funkcjonalny” droga będzie prawdopodobnie tworzyć nieskończone lazy sekwencję Fibonacciego a następnie wyodrębnić pierwsze N ​​wartości, a mianowicie:

(take n some-infinite-fibonacci-sequence) 

Poniższy link zawiera kilka bardzo interesujących sposobów generowania fibonnaci sekwencje wzdłuż tych linii:

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

Wreszcie tutaj jest kolejna realizacja zabawy do rozważenia:

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

To nie jest tak zwięzły jak to może być, ale wykazuje bardzo ładnie użycie destructuring Clojure jest, leniwy sekwencji i funkcja wyższego rzędu, aby rozwiązać ten problem.

Answer 4

Zobacz rozwiązanie Christophe'a Wielkiego Fibonacciego w Programowanie Clojure przez Stu Halloway. To najbardziej eleganckie rozwiązanie, jakie widziałem.

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

zobaczyć również

How can I generate the Fibonacci sequence using Clojure?