Очистка функции Clojure

Question

Исходя из императивных языков программирования, я пытаюсь обернуть голову вокруг Clojure в надежде использовать его для его многопоточности.
Одна из проблем из 4Clojure состоит в том, чтобы написать функцию, которая генерирует список чисел Фибоначчи длины N, для N> 1. Я написал функцию, но, учитывая мой ограниченный фон, я хотел бы получить некоторый вклад в будь это лучший способ Clojure или нет. Код выглядит следующим образом:

(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

Наиболее идиоматическим «функциональным» способом, вероятно, было бы создание бесконечной ленивой последовательности чисел Фибоначчи и затем извлечение первых n значений, то есть:

(take n some-infinite-fibonacci-sequence)

Следующая ссылка имеет несколько очень интересных способовгенерация последовательностей Фибоначчи по этим направлениям:

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

Наконец, вот еще одна забавная реализация, которую следует рассмотреть:

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

Это не так кратко, как могло бы быть, нодовольно наглядно демонстрирует использование деструктуризации Clojure, ленивых последовательностей и функций высшего порядка для решения проблемы.

Answer 2

Вот версия Фибоначчи, которая мне очень нравится (я взял реализацию из clojure wikibook: http://en.wikibooks.org/wiki/Clojure_Programming)

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

Это работает так: представьте, что у вас уже есть бесконечная последовательность чисел Фибоначчи. Если вы возьмете хвост последовательности и добавите его поэлементно к исходной последовательности, вы получите (хвост хвоста) последовательности Фибоначчи

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

Таким образом, вы можете использовать это для расчета последовательности. Вам нужны два начальных элемента [0 1] (или [1 1] в зависимости от того, где вы начинаете последовательность), а затем вы просто отображаете две последовательности, добавляя элементы. Обратите внимание, что вам нужны ленивые последовательности здесь.

Я думаю, что это самая элегантная и (по крайней мере, для меня) реализация, расширяющая сознание.

Редактировать: функция fib

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

Answer 3

См. Решение Фибоначчи Кристофа Гранда в Программирование Clojure Стю Хэллоуэй. Это самое элегантное решение, которое я видел.

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

Также см.

Как я могу сгенерировать последовательность Фибоначчи, используя Clojure?

Answer 4

Вот один из способов сделать это, который дает вам немного времени для ленивых последовательностей, хотя, безусловно, это не совсем оптимальный способ вычисления последовательности Фибоначчи.

Учитывая определение последовательности Фибоначчи, мы можем видеть, что она построена путем многократного применения одного и того же правила к базовому случаю '(1 1). Функция Clojure iterate звучит так, как будто для этого подойдет:

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

Таким образом, для нашей функции мы бы хотели получить что-то, что будет принимать значения, которые мы вычислили до сих пор, суммирует два самых последних и возвращает список нового значения и всех старых значений.

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

Список аргументов здесь просто означает, что x и y будут связаны с первыми двумя значениями из списка, переданного в качестве аргумента функции, список, содержащий все аргументы после первых двух, будет связан с _ и исходный список, переданный в качестве аргумента функции, может быть передан через all.

Теперь, iterate вернет бесконечную последовательность промежуточных значений, поэтому для нашего случая мы захотим обернуть это во что-то, что просто вернет интересующее нас значение; Ленивое вычисление остановит всю бесконечную последовательность, вычисляемую.

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

Обратите внимание, что это возвращает результат в порядке, обратном вашей реализации; это легко исправить с помощью reverse, конечно.

Редактировать: или действительно, как говорит Амаллой, используя векторы:

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