Как вы заметили, [0 1] устанавливает базовые случаи: первые два значения в последовательности равны нулю, а затем единице. После этого каждое значение должно быть суммой предыдущего значения и значения перед этим. Следовательно, мы не можем даже вычислить третье значение в последовательности, не имея по крайней мере двух, которые предшествуют ему. Вот почему нам нужно начать с двух значений.
Теперь посмотрите на форму map. В нем говорится, что нужно взять элементы заголовка из двух разных последовательностей, объединить их с функцией + (добавление нескольких значений для получения одной суммы) и представить результат как следующее значение в последовательности. Форма map объединяет две последовательности & mdash; предположительно равной длины & mdash; в одну последовательность одинаковой длины.
Две последовательности, поданные на map, представляют собой разные виды одной и той же базовой последовательности, смещенные на один элемент. Первая последовательность - это «все, кроме первого значения базовой последовательности». Вторая последовательность - это сама базовая последовательность, которая, конечно, включает в себя первое значение. Но какой должна быть базовая последовательность?
В приведенном выше определении говорится, что каждый новый элемент является суммой предыдущего ( Z - 1 ) и предшественника предыдущего элемента ( Z - 2 ). Это означает, что расширение последовательности значений требует доступа к ранее вычисленным значениям в той же последовательности. Нам определенно нужен двухэлементный сдвиговый регистр , но мы также можем запросить доступ к нашим предыдущим результатам. Вот что делает здесь рекурсивная ссылка на последовательность под названием fib-seq. Символ fib-seq относится к последовательности, которая представляет собой конкатенацию нуля, единицы, а затем суммы собственных Z - 2 и Z - 1 значений.
Взяв последовательность, называемую fib-seq, при рисовании первого элемента получается первый элемент вектора [0 1] & mdash; нуль. Рисование второго элемента дает второй элемент вектора & mdash; один. После отрисовки третьего элемента мы консультируемся с map, чтобы сгенерировать последовательность и использовать ее в качестве оставшихся значений. Последовательность, генерируемая map, здесь начинается с суммы первого элемента «остатка» [0 1], который равен единице, и первого элемента [0 1], который равен нулю. Эта сумма равна единице.
Рисование четвертого элемента снова обращается к map, которое теперь должно вычислять сумму второго элемента "остальной части" базовой последовательности, который генерируется map, и второго элемента базы последовательность, которая из вектора [0 1]. Эта сумма равна двум.
Рисование пятого элемента обращается к map, суммируя третий элемент "остальной части" базовой последовательности & mdash; опять же, результат, полученный в результате суммирования нуля, а один - и третий элемент базовой последовательности & mdash; которого мы только что нашли.
Вы можете видеть, как это строится, чтобы соответствовать намеченному определению для серии. Что еще труднее понять, так это то, что при рисовании каждого элемента все предыдущие значения пересчитываются дважды & mdash; один раз для каждой последовательности, проверенной 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 & mdash; в частности, файл LazySeq.java & mdash; и подумал, что это хорошее место, чтобы поделиться несколькими наблюдениями.
Во-первых, обратите внимание, что многие функции обработки ленивых последовательностей в Clojure в конечном итоге используют lazy-seq по сравнению с другими коллекциями. lazy-seq создает экземпляр типа Java LazySeq, который моделирует небольшой конечный автомат. У него есть несколько конструкторов, которые позволяют запускать его в разных состояниях, но наиболее интересный случай - это тот, который начинается с ссылки на нулевую функцию. Построенный таким образом, LazySeq не оценивал функцию и не находил последовательность делегатов (тип ISeq в Java). Первый раз спрашивает LazySeq о первом элементе & mdash; через first & mdash; или любые преемники & ndash; через next или rest & mdash; он оценивает функцию, просматривает полученный объект, чтобы очистить все слои-обертки других LazySeq экземпляров, и, наконец, передает внутренний объект через функцию java RT#seq(), что приводит к экземпляру ISeq.
На данный момент LazySeq имеет ISeq, которому можно делегировать вызовы от имени first, next и rest. Обычно «head» ISeq будет иметь тип Cons, который хранит постоянное значение в своем «первом» (или «автомобильном») слоте, а другой ISeq в своем «остальном» (или «cdr») слоте , То, что ISeq в своем слоте "rest" может, в свою очередь, быть LazySeq, и в этом случае для доступа к нему снова потребуется такая же оценка функции, отстранение всех ленивых оболочек возвращаемого значения и передача этого значения через RT#seq() чтобы получить еще один ISeq для делегирования.
Экземпляры LazySeq остаются связанными вместе, но наличие принудительного единицы (через first, next или rest) заставляет его делегировать прямо некоторым не ленивым ISeq после этого. Обычно это форсирование оценивает функцию, которая выдает Cons, привязанную к первому значению, а его хвост, привязанный к другому LazySeq; это цепочка функций генератора, каждая из которых выдает одно значение («первый» слот Cons), связанное с другой возможностью выдавать больше значений (LazySeq в «110» * слоте «rest»).
Связывая это, в приведенном выше примере последовательности Фибоначчи, map возьмет каждую из вложенных ссылок на fib-seq и проведет их по отдельности с помощью повторных вызовов rest. Каждый такой вызов преобразует не более одного LazySeq, содержащего неоцененную функцию, в LazySeq, указывающий на что-то вроде Cons. После преобразования любые последующие обращения быстро разрешатся до Cons es & mdash; где хранятся фактические значения. Когда одна ветвь 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.