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

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

a = a + 5

WTF? a явно не то же самое, что a + 5 .

если a = a + 5 , это a + 5 = a ?

Почему это не работает ???

if (a = 5) { // should be == in most programming languages
    // do something
}

Есть много вещей, которые непонятны, если вы не видели это раньше где-то в другом месте и не понимали его цель. Долгое время я не знал ключевого слова yield и, по сути, не мог понять, что оно делает.

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

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

Код Clojure мне интуитивно понятен (потому что я знаю Clojure). Если вам нужно что-то, что могло бы больше походить на то, с чем вы знакомы, вы можете попробовать эту эффективную и чрезмерно многословную рекурсивную версию:

(use 'clojure.contrib.def)   ; SO's 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)))

Но для тех, кто не знает, что такое рекурсия или мемоизация, это не t тоже будет интуитивно понятным. Сама идея «бесконечных ленивых последовательностей», вероятно, не является интуитивной для большинства программистов. Я не могу угадать, что у вас в голове, поэтому я не знаю, как для вас будет выглядеть более интуитивно понятная функция Clojure, кроме «больше похожей на Python».

Для тех, кто не разбирается в программировании, все это будет похоже на тарабарщину. Что за петля? Что за функция? Что это за доходность ? Который' с того места, где мы все начинаем. Интуитивность - это функция того, что вы уже узнали. Неинтуитивный код - это код, с которым вы еще не знакомы. Экстраполяция «я знаю это» на «это интуитивно более интуитивно» неверна.

(take 5 fibs)

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

Я согласен с Павлом, то, что интуитивно, субъективно. Поскольку я (медленно) начинаю разбираться в 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 бесконечным списком чисел Фибоначчи. выдумки !! 1 равно 1, выдумки !! 2 равно 1, выдумки !! 10 равно 55 и так далее. Однако это, вероятно, довольно неэффективно даже для языка, который полагается на сильно оптимизированную рекурсию, такого как Haskell. Давайте посмотрим на определение Clojure в Haskell:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Первая пара символов довольно проста: 0: 1: составляет список с элементами 0 и 1, а затем еще несколько. Но что все остальное? Итак, fibs - это список, который у нас уже есть, а tail fibs вызывает функцию tail в нашем списке, который возвращает список, начиная со 2-го элемента (вроде как в 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 (своего рода автоматическая запоминание), и мы редко сталкиваемся с проблемами, которые могут возникнуть в наивное решение. Для полноты давайте определим нашу функцию 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, мы ' re просто объединяет наш список с самим собой с меньшим смещением, а затем объединяет эти два списка с помощью оператора / функции + .

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

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

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

В wiki есть подробное описание различных реализаций Фибоначчи в 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)