Ответ 1
Мне нравится:
(def fibs
(map first
(iterate
(fn [[ a, b ]]
[ b, (+ a b) ])
[0, 1])))
Что, похоже, имеет некоторое сходство с версией python/generator.
Вот лучшие реализации, которые я мог бы найти для ленивых бесконечных последовательностей чисел Фибоначчи как в Clojure, так и в Python:
Clojure:
(def fib-seq (lazy-cat [0 1]
(map + fib-seq (rest fib-seq))))
Использование образца:
(take 5 fib-seq)
Python:
def fib():
a = b = 1
while True:
yield a
a,b = b,a+b
Использование образца:
for i in fib():
if i > 100:
break
else:
print i
Очевидно, что код Python намного интуитивен.
Мой вопрос: есть ли более эффективная (более интуитивная и простая) реализация в Clojure?
Я открываю следующий вопрос: Clojure Основные номера
Мне нравится:
(def fibs
(map first
(iterate
(fn [[ a, b ]]
[ b, (+ a b) ])
[0, 1])))
Что, похоже, имеет некоторое сходство с версией python/generator.
Я согласен с Павлом, что интуитивно субъективно. Поскольку я (медленно) начинаю хричать Haskell, я могу сказать, что делает код Clojure, хотя я никогда не писал строку Clojure в моей жизни. Поэтому я считаю строку Clojure довольно интуитивной, потому что я ее видел раньше, и я приспосабливаюсь к более функциональному мышлению.
Рассмотрим математическое определение, будем ли мы?
{ 0 if x = 0 }
F(x) = { 1 if x = 1 }
{ F(x - 1) + F(x - 2) if x > 1 }
Это меньше, чем идеально, форматирование мудрого - те три скобки, выстроившиеся в линию, должны быть одной гигантской скобкой, но кто считает? Это довольно четкое определение последовательности Фибоначчи для большинства людей с математическим фоном. Давайте посмотрим на то же самое в Haskell, потому что я знаю это лучше, чем Clojure:
fib 0 = 0
fib 1 = 1
fib n = fibs (n - 1) + fibs (n - 2)
Это функция, fib
, которая возвращает n-е число Фибоначчи. Не совсем то, что у нас было на Python или Clojure, поэтому исправьте это:
fibs = map fib [0..]
Это делает fibs
бесконечным списком чисел Фибоначчи. fibs !! 1
равно 1, fibs !! 2
равно 1, fibs !! 10
равно 55 и т.д. Однако это, вероятно, довольно неэффективно даже на языке, который опирается на сильно оптимизированную рекурсию, такую как Haskell. Давайте рассмотрим определение Clojure в Haskell:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Первая пара символов довольно проста: 0 : 1 :
создает список с элементами 0 и 1, а затем еще несколько. Но что все остальное? Ну, fibs
- это список, который у нас уже есть, и tail fibs
вызывает функцию tail
в нашем списке, которая возвращает список, начинающийся со второго элемента (вроде как в Python, говорящем fibs[1:]
)), Поэтому мы берем эти два списка - fibs
и tail fibs
- и мы их запишем вместе с функцией +
(оператор), т.е. Добавляем соответствующие элементы каждого из них. Давайте посмотрим:
fibs = 0 : 1 : ...
tail fibs = 1 : ...
zip result = 1 : ...
Итак, наш следующий элемент - 1! Но тогда мы добавим это обратно в наш fibs
список и посмотрим, что получим:
fibs = 0 : 1 : 1 : ...
tail fibs = 1 : 1 : ...
zip result = 1 : 2 : ...
Что мы имеем здесь, это определение рекурсивного списка. Поскольку мы добавляем больше элементов в конец fibs
с нашим битом zipWith (+) fibs (tail fibs)
, при добавлении элементов нам будет доступно больше элементов. Обратите внимание, что Haskell по умолчанию ленив, поэтому просто создание такого бесконечного списка не приведет к сбою (просто не пытайтесь распечатать его).
Итак, хотя это, пожалуй, теоретически то же самое, что и наше математическое определение раньше, оно сохраняет результаты в нашем fibs
списке (вроде авто-memoization), и мы редко сталкиваемся с проблемами, которые могут возникнуть в наивном решении. Для полноты определим нашу функцию fib
в терминах нашего нового списка fibs
:
fib n = fibs !! n
Если я еще не потерял вас, это хорошо, потому что это означает, что вы понимаете код Clojure. Посмотрите:
(def fib-seq (lazy-cat [0 1]
(map + fib-seq (rest fib-seq))))
Мы делаем список, fib-seq
. Он начинается с двух элементов [0 1]
, как и наш пример Haskell. Мы выполняем ленивую конкатенацию этих двух исходных элементов с помощью (map + fib-seq (rest fib-seq))
- если rest
делает то же самое, что tail
в Haskell, мы просто объединяем наш список с собой при более низком смещении, а затем объединяем эти два списки с оператором/функцией +
.
Несколько раз, проработав это через вашу голову, и изучив некоторые другие примеры, этот способ генерации ряда фибоначчи становится, по крайней мере, полуинтуитивным. Это, по крайней мере, достаточно интуитивно для меня, чтобы определить это на языке, который я не знаю.
Если бы вы не знали каких-либо императивных языков, это было бы интуитивно для вас?
a = a + 5
WTF? a
явно не совпадает с a + 5
.
if a = a + 5
, a + 5 = a
?
Почему это не работает?
if (a = 5) { // should be == in most programming languages
// do something
}
Есть много вещей, которые не ясны, если вы не видели его где-то еще и не понимали его цели. В течение долгого времени я не знал ключевое слово yield
, и по сути я не мог понять, что он сделал.
Вы думаете, что императивный подход более разборчив, потому что вы привыкли к нему.
Код Clojure интуитивно понятен мне (потому что я знаю Clojure). Если вы хотите что-то, что может выглядеть более похоже на то, с чем вы знакомы, вы можете попробовать это, эффективную и чрезмерно вербальную рекурсивную версию:
(use 'clojure.contrib.def) ; SO syntax-highlighting still sucks
(defn-memo fib [n]
(cond (= n 0) 0
(= n 1) 1
:else (+ (fib (- n 1))
(fib (- n 2)))))
(def natural-numbers (iterate inc 0))
(def all-fibs
(for [n natural-numbers]
(fib n)))
Но кому-то, кто не знает, что такое рекурсия или мемуаризация, это тоже не будет интуитивным. Сама идея "бесконечных ленивых последовательностей", вероятно, не интуитивно понятна большинству программистов. Я не могу догадаться, что в вашем мозгу, поэтому я не знаю, какая более интуитивная функция Clojure будет выглядеть для вас, кроме "больше похожа на Python".
Кому-то, кто не знает программирования, все это будет выглядеть как тарабарщина. Какая петля? Какая функция? Что это за yield
вещь? Это где мы все начинаем. Интуитивность - это функция того, что вы узнали до сих пор. Неинтуитивный код - это код, с которым вы еще не знакомы. Экстраполирование из "Я знаю это" на "Оно по своей сути более интуитивно" неверно.
wiki имеет углубленное рассмотрение различных реализаций Фибоначчи в Clojure, которые могут вас заинтересовать, если вы еще не видели это уже.
Вы всегда должны использовать язык, который подходит для проблемы *
. Ваш пример Python - это чуть более низкий уровень, чем Clojure один - легче понять для новичков, но более утомительно писать и анализировать для тех, кто знает подходящие концепции более высокого уровня.
*
Кстати, это также означает, что всегда приятно иметь язык, который вы можете вырастить, чтобы соответствовать.
Вот одно из решений.
(defn fib-seq [a b]
(cons (+ a b) (lazy-seq (fib-seq (+ a b) a))))
(def fibs (concat [1 1] (fib-seq 1 1)))
user=> (take 10 fibs)
(1 1 2 3 5 8 13 21 34 55)
Подумайте, как бы вы писали lazy-cat с recur в clojure.
(take 5 fibs)
Кажется, что он интуитивно понятен, как мог. Я имею в виду, это именно то, что вы делаете. Вам даже не нужно ничего понимать о языке или даже знать, на каком языке это, чтобы знать, что должно произойти.