Ленивые бесконечные последовательности в Clojure и Python

Вот лучшие реализации, которые я мог бы найти для ленивых бесконечных последовательностей чисел Фибоначчи как в 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 Основные номера

Ответы

Ответ 1

Мне нравится:

(def fibs 
  (map first 
       (iterate 
           (fn [[ a, b       ]]  
                [ b, (+ a b) ]) 
           [0, 1])))     

Что, похоже, имеет некоторое сходство с версией python/generator.

Ответ 2

Я согласен с Павлом, что интуитивно субъективно. Поскольку я (медленно) начинаю хричать 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, мы просто объединяем наш список с собой при более низком смещении, а затем объединяем эти два списки с оператором/функцией +.

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

Ответ 3

Если бы вы не знали каких-либо императивных языков, это было бы интуитивно для вас?

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, и по сути я не мог понять, что он сделал.

Вы думаете, что императивный подход более разборчив, потому что вы привыкли к нему.

Ответ 4

Код 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 вещь? Это где мы все начинаем. Интуитивность - это функция того, что вы узнали до сих пор. Неинтуитивный код - это код, с которым вы еще не знакомы. Экстраполирование из "Я знаю это" на "Оно по своей сути более интуитивно" неверно.

Ответ 5

wiki имеет углубленное рассмотрение различных реализаций Фибоначчи в Clojure, которые могут вас заинтересовать, если вы еще не видели это уже.

Ответ 6

Вы всегда должны использовать язык, который подходит для проблемы *. Ваш пример Python - это чуть более низкий уровень, чем Clojure один - легче понять для новичков, но более утомительно писать и анализировать для тех, кто знает подходящие концепции более высокого уровня.

* Кстати, это также означает, что всегда приятно иметь язык, который вы можете вырастить, чтобы соответствовать.

Ответ 7

Вот одно из решений.

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

Ответ 8

Подумайте, как бы вы писали lazy-cat с recur в clojure.

Ответ 9

(take 5 fibs)

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