Взяв пример серии Fibonacci из Wiki Clojure, код Clojure:
(def fib-seq
(lazy-cat [0 1] (map + (rest fib-seq) fib-seq)))
Если бы вы подумали об этом, начиная с [0 1], как это работает? Было бы здорово, если бы были предложения по мыслительному процессу, который приходит в голову в этих терминах.
Как вы отметили, [0 1] устанавливает базовые случаи: первые два значения в последовательности равны нулю, а затем один. После этого каждое значение должно быть суммой предыдущего значения и значения до этого. Следовательно, мы не можем даже вычислить третье значение в последовательности, не имея, по крайней мере, двух, которые предшествуют ему. Вот почему нам нужны два значения, с которых нужно начинать.
Теперь просмотрите форму map. Он говорит, чтобы взять главные элементы из двух разных последовательностей, объединить их с функцией + (добавив несколько значений для создания одной суммы) и выставить результат как следующее значение в последовательности. Форма map объединяет две последовательности:— предположительно равной длины; в одну последовательность с одинаковой длиной.
Две последовательности, подаваемые в map, представляют собой разные представления одной и той же базовой последовательности, сдвинутой на один элемент. Первая последовательность "все, кроме первого значения базовой последовательности". Вторая последовательность представляет собой базовую последовательность, которая, конечно, включает в себя первое значение. Но какова должна быть последовательность оснований?
В приведенном выше определении сказано, что каждый новый элемент представляет собой сумму предыдущего (Z - 1) и предшественника предыдущего элемента (Z - 2). Это означает, что для расширения последовательности значений требуется доступ к ранее вычисленным значениям в одной и той же последовательности. Нам определенно нужен двухэлементный регистр сдвига, но мы также можем запросить доступ к нашим предыдущим результатам. То, что здесь делает рекурсивная ссылка на последовательность, называемую fib-seq. Символ fib-seq обозначает последовательность, состоящую из конкатенации нуля, единицы, а затем суммы ее собственных значений Z - 2 и Z - 1.
Взяв последовательность, называемую fib-seq, рисование первого элемента дает первый элемент вектора [0 1] — нуль. При рисовании второго элемента получается второй элемент вектора — один. При рисовании третьего элемента мы советуем map сгенерировать последовательность и использовать это как оставшиеся значения. Последовательность, сгенерированная map, начинается с суммы первого элемента "остальная часть" [0 1], которая является одной, и первого элемента [0 1], который равен нулю. Эта сумма одна.
Рисуя четвертый элемент, снова обратитесь к map, который теперь должен вычислить сумму второго элемента "остальной" базовой последовательности, которая является сгенерированной map, а второй элемент базы последовательность, которая является одной из вектора [0 1]. Эта сумма равна двум.
Рисование пятого элемента справляется с map, суммируя третий элемент "остальной" базовой последовательности -— опять же, результат, полученный путем суммирования нуля и одного; и третий элемент базовой последовательности -— которые мы только что обнаружили, были двумя.
Вы можете увидеть, как это происходит, чтобы соответствовать заданному определению для серии. Что еще труднее увидеть, так это то, будет ли рисовать каждый элемент повторно пересчитывать все предыдущие значения дважды -— один раз для каждой последовательности, проверенной на map. Оказывается, такого повторения здесь нет.
Чтобы подтвердить это, добавьте определение fib-seq, как это, чтобы использовать функцию +:
(def fib-seq
(lazy-cat [0 1]
(map
(fn [a b]
(println (format "Adding %d and %d." a b))
(+ a b))
(rest fib-seq) fib-seq)))
Теперь попросите первые десять пунктов:
> (doall (take 10 fib-seq))
Adding 1 and 0.
Adding 1 and 1.
Adding 2 and 1.
Adding 3 and 2.
Adding 5 and 3.
Adding 8 and 5.
Adding 13 and 8.
Adding 21 and 13.
(0 1 1 2 3 5 8 13 21 34)
Обратите внимание: для генерации первых десяти значений существует восемь вызовов +.
После написания предыдущего обсуждения я потратил некоторое время на изучение реализации ленивых последовательностей в Clojure — в частности, файл LazySeq.java — и подумал, что это будет хорошее место, чтобы поделиться несколькими наблюдениями.
Во-первых, обратите внимание, что многие функции обработки ленивой последовательности в Clojure в конечном итоге используют lazy-seq для какой-либо другой коллекции. lazy-seq создает экземпляр типа Java LazySeq, который моделирует небольшой конечный автомат. Он имеет несколько конструкторов, которые позволяют ему запускаться в разных состояниях, но наиболее интересным является тот, который начинается только с ссылки на нулевую функцию. Построенный таким образом, LazySeq не оценил функцию и не нашел последовательность делегатов (тип ISeq в Java). В первый раз запрашивается LazySeq для его первого элемента — через first — или любых преемников; через next или rest — он оценивает функцию, выкапывает через результирующий объект, чтобы очистить все слои оболочки других экземпляров LazySeq и, наконец, подает самый внутренний объект через java-функцию RT#seq(), что приводит к экземпляру ISeq.
В этот момент LazySeq имеет ISeq, которому необходимо делегировать вызовы от имени first, next и rest. Обычно "head" ISeq будет иметь тип Cons, который сохраняет постоянное значение в своем "первом" (или "автомобильном" ) слоте, а другой ISeq в слоте "rest" (или "cdr" ), То, что ISeq в слоте "отдыха", в свою очередь, может быть LazySeq, и в этом случае доступ к нему снова потребует этой же оценки функции, отбрасывая любые ленивые обертки на возвращаемое значение и передавая это значение через RT#seq(), чтобы получить еще один ISeq, которому нужно делегировать.
Экземпляры LazySeq остаются связанными друг с другом, но принудительное одно (через first, next или rest) заставляет его делегировать прямо через несколько нелазных ISeq после этого. Обычно это принуждение оценивает функцию, которая дает привязку Cons к первому значению, а ее хвост привязан к другому LazySeq; это цепочка функций генератора, каждая из которых дает одно значение (первый "слот" Cons), связанный с другой возможностью, чтобы дать больше значений (a LazySeq в слоте Cons).
Привязав это назад, в приведенном выше примере последовательности Фибоначчи, map возьмет каждую из вложенных ссылок на fib-seq и проведет их отдельно через повторные вызовы на rest. Каждый такой вызов будет преобразовывать не более одного LazySeq, удерживая неоценимую функцию в LazySeq, указывая на что-то вроде Cons. После преобразования любые последующие обращения быстро решаются на Cons es — где хранятся фактические значения. Когда одна ветвь map zipping проходит fib-seq один элемент за другим, значения уже были разрешены и доступны для доступа по постоянному времени, без дополнительной оценки требуемой функции генератора.
Вот несколько диаграмм, которые помогут визуализировать эту интерпретацию кода:
+---------+
| LazySeq |
fib-seq | fn -------> (fn ...)
| sv |
| s |
+---------+
+---------+
| LazySeq |
fib-seq | fn -------> (fn ...) -+
| sv <------------------+
| s |
+---------+
+---------+
| LazySeq |
fib-seq | fn |
| sv -------> RT#seq() -+
| s <------------------+
+---------+
+---------+ +------+
| LazySeq | | ISeq |
fib-seq | fn | | |
| sv | | |
| s ------->| |
+---------+ +------+
+---------+ +--------+ +------+
| LazySeq | | Cons | | ISeq |
fib-seq | fn | | first ---> 1 | |
| sv | | more -------->| |
| s ------->| | | |
+---------+ +--------+ +------+
+---------+ +--------+ +---------+
| LazySeq | | Cons | | LazySeq |
fib-seq | fn | | first ---> 1 | fn -------> (fn ...)
| sv | | more -------->| sv |
| s ------->| | | s |
+---------+ +--------+ +---------+
Поскольку map прогрессирует, он перескакивает от LazySeq до LazySeq (и, следовательно, Cons до Cons), а самый правый край только расширяется при первом вызове first, next, или rest на заданном LazySeq.
Мой Clojure немного ржавый, но это, кажется, буквальный перевод знаменитого однострочного Haskell:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
[Я буду использовать псевдо-Haskell, потому что это немного более кратким.]
Первое, что вам нужно сделать, это просто позволить лень утонуть. Когда вы посмотрите на определение вроде этого:
zeroes = 0 : zeroes
Ваша непосредственная реакция на кишок как строгий программист будет "бесконечным циклом ZOMG!" Исправить ошибку! " Но это не бесконечный цикл. Это ленивый бесконечный цикл. Если вы делаете что-то глупое, как
print zeroes
Тогда, да, будет бесконечный цикл. Но пока вы просто используете конечное число элементов, вы никогда не заметите, что рекурсия на самом деле не заканчивается. Это действительно сложно получить. Я до сих пор этого не делаю.
Лень - это как денежная система: она основана на предположении, что подавляющее большинство людей никогда не использует подавляющее большинство своих денег. Итак, когда вы кладете 1000 долларов в банк, они не хранят его в безопасности. Они предоставляют его кому-то другому. Фактически, они используют деньги, а это значит, что они дают 5000 долларов кому-то другому. Им только нужно достаточно денег, чтобы они могли быстро перетасовать его, чтобы он там, когда вы смотрите на него, давая вам вид, что они фактически сохраняют ваши деньги.
Пока они могут всегда выдавать деньги, когда вы подходите к банкомату, на самом деле не имеет значения, что подавляющего большинства ваших денег нет: им нужна только небольшая сумма, которую вы снимаете на момент времени, когда вы делаете вывод.
Лень работает одинаково: всякий раз, когда вы смотрите на нее, значение есть. Если вы посмотрите на первый, десятый, hundreth, квадриллионный элемент zeroes, он будет там. Но он будет только там, если и когда вы посмотрите на него, не раньше.
Вот почему это, по крайней мере, рекурсивное определение zeroes работает: пока вы не пытаетесь взглянуть на последний элемент (или каждый элемент) бесконечного списка, вы в безопасности.
Следующий шаг zipWith. (Clojure map является просто обобщением того, что на других языках программирования обычно состоит из трех различных функций: map, zip и zipWith. В этом примере он используется как zipWith.)
Причина, по которой семейство функций zip названо таким образом, состоит в том, что оно действительно работает как молния, а также как наилучшим образом визуализировать его. Скажем, у нас есть какое-то спортивное событие, где каждый участник получает две попытки, и оценка от обоих попыток складывается, чтобы дать конечный результат. Если у нас есть две последовательности, run1 и run2 с оценками из каждого прогона, мы можем вычислить конечный результат следующим образом:
res = zipWith (+) run1 run2
Предполагая, что наши два списка (3 1 6 8 6) и (4 6 7 1 3), мы выставляем оба этих списка бок о бок, как две половинки застежки-молнии, а затем мы их запишем вместе с помощью нашей заданной функции (+ в этот случай), чтобы получить новую последовательность:
3 1 6 8 6
+ + + + +
4 6 7 1 3
= = = = =
7 7 13 9 9
Победитель конкурса №3.
Итак, как выглядит наш fib?
Ну, он начинается с 0, затем мы добавляем 1, затем добавляем сумму бесконечного списка с бесконечным списком, сдвинутым на один элемент. Проще всего просто извлечь из этого:
первый элемент равен нулю:
0
второй элемент - один:
0 1
третий элемент - это первый элемент плюс первый элемент остального (т.е. второй элемент). Мы визуализируем это снова, как застежку-молнию, помещая два списка друг на друга.
0 1
+
1
=
1
Теперь элемент, который мы только что вычислили, - это не только результат функции zipWith, но одновременно и вход, поскольку он добавляется к обоим спискам (которые фактически являются одним и тем же списком, только сдвинутый на один):
0 1 1
+ +
1 1
= =
1 2
и т.д.:
0 1 1 2
+ + +
1 1 2
= = =
1 2 3
0 1 1 2 3 ^
+ + + + |
1 1 2 3 ^ |
= = = = | |
1 2 3 5---+---+
Или, если вы рисуете его немного по-другому и объедините список результатов и второй список ввода (который в любом случае одинаковый):
0 1 1 2 3 ^
+ + + + + |
1 = 1 = 2 = 3 = 5---+
То, как я это визуализирую, в любом случае.
Как это работает:
Каждый член ряда фибоначчи, очевидно, является результатом добавления предыдущих двух членов. Что карта делает здесь, карта применяет + к каждому элементу в каждой последовательности до тех пор, пока не закончится одна из последовательностей (что, конечно, не будет в этом случае). Таким образом, результат представляет собой последовательность чисел, которая возникает из добавления одного члена в последовательности к следующему члену в последовательности. Затем вам нужна ленивая кошка, чтобы дать ей исходную точку и убедиться, что функция возвращает только то, что она просила.
Проблема с этой реализацией заключается в том, что fib-seq удерживается на всей последовательности до тех пор, пока определяется fib-seq, поэтому она в конечном итоге выведет вас из памяти.
Книга Стюарта Хэллоуя посвящает некоторое время анализу различных реализаций этой функции, я думаю, что наиболее интересный ниже (это Кристоф Гранде):
(defn fibo []
(map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))
В отличие от опубликованной реализации, ранее прочитанные элементы последовательности не имеют на них ничего, поэтому можно продолжать работать без генерации OutOfMemoryError.
Как задуматься над этими терминами - вопрос сложнее. До сих пор для меня это вопрос ознакомления с множеством разных способов сделать вещи и попробовать их, в то время как в целом ищет способы применить существующую библиотеку функций, предпочитая использовать рекурсию и ленивый кот. Но в некоторых случаях рекурсивное решение действительно велико, поэтому это зависит от проблемы. Я с нетерпением жду, чтобы получить книгу "Радость" Clojure, потому что я думаю, что это очень поможет мне в этой проблеме.