Ответ 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.