Мышление в ленивых последовательностях

Как вы отметили, [0 1] устанавливает базовые случаи: первые два значения в последовательности равны нулю, затем одно . После этого каждое значение должно быть суммой предыдущего значения и значения перед этим. Следовательно, мы не можем даже вычислить третье значение в последовательности, если перед ним не будет по крайней мере два. Вот почему нам нужны два значения для начала.

Теперь посмотрим на форму map . Он говорит, что нужно взять элементы заголовка из двух разных последовательностей, объединить их с помощью функции + (сложить несколько значений для получения одной суммы) и предоставить результат как следующее значение в последовательности. Форма map объединяет две последовательности - предположительно одинаковой длины - в одну последовательность одинаковой длины.

Две последовательности, загруженные в карту , представляют собой разные представления одной и той же базовой последовательности, сдвинутой на один элемент. Первая последовательность - это «все, кроме первого значения базовой последовательности». Вторая последовательность - это сама базовая последовательность, которая, конечно же, включает первое значение. Но какой должна быть базовая последовательность?

В приведенном выше определении сказано, что каждый новый элемент является суммой предыдущего ( Z - 1 ) и предшественника предыдущего элемента ( Z - 2 ). Это означает, что для расширения последовательности значений требуется доступ к ранее вычисленным значениям в той же последовательности. Нам определенно нужен двухэлементный регистр сдвига , но вместо этого мы также можем запросить доступ к нашим предыдущим результатам.Вот что здесь делает рекурсивная ссылка на последовательность fib-seq . Символ fib-seq относится к последовательности, которая представляет собой конкатенацию нуля, единицы, а затем суммы собственных значений Z - 2 и Z - 1 . .

Взяв последовательность под названием fib-seq , отрисовка первого элемента дает первый элемент вектора [0 1] - ноль. Рисование второго элемента дает второй элемент вектора - один. После рисования третьего элемента мы обращаемся к карте , чтобы сгенерировать последовательность и использовать ее в качестве оставшихся значений. Последовательность, сгенерированная map здесь, начинается с суммы первого элемента «остальной части» [0 1] , который равен единице, и первого элемента [0 1] , что равно нулю. Эта сумма равна единице.

Рисование четвертого элемента снова обращается к карте , которая теперь должна вычислить сумму второго элемента «остальной части» базовой последовательности, которая генерируется картой , и второй элемент базовой последовательности, который является элементом вектора [0 1] . Эта сумма равна двум.

Рисование пятого элемента обращается к карте , суммируя третий элемент «остальной части» базовой последовательности - опять же, результат суммирования нуля и единицы - и третий элемент базовой последовательности - которых мы только что обнаружили, чтобы их было двое.

Вы можете видеть, как это строится, чтобы соответствовать предполагаемому определению для сериала.Сложнее увидеть, повторяет ли рисование каждого элемента все предыдущие значения дважды - по одному разу для каждой последовательности, проверенной с помощью 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 , которому можно делегировать вызовы от имени сначала , затем и остальное . Обычно "голова" ISeq будет иметь тип Cons , который хранит постоянное значение в своем "первом" (или "автомобильном") слоте и другом ISeq в слоте "rest" (или "cdr"). Этот ISeq в своем слоте "rest", в свою очередь, может быть LazySeq , и в этом случае для доступа к нему снова потребуется такая же оценка функции, удаляя любые ленивые оболочки при возврате. значение и передача этого значения через RT # seq () , чтобы получить еще один ISeq , которому следует делегировать.

Экземпляры LazySeq остаются связанными вместе, но с принудительно один (через сначала , затем или отдых ) заставляет его делегировать сразу несколько неленивых ISeq после этого. Обычно это форсирование оценивает функцию, которая возвращает Cons , привязанную к первому значению, а ее хвост - к другому LazySeq ; это цепочка функций генератора, каждая из которых дает одно значение («первый» слот Cons ), связанное с другой возможностью для получения большего количества значений ( LazySeq в Cons Слот для отдыха ).

Связывая это, в приведенном выше примере последовательности Фибоначчи, карта будет брать каждую из вложенных ссылок на fib-seq и проходить их отдельно с помощью повторных вызовов отдых . Каждый такой вызов преобразует не более одного LazySeq , содержащего неоцененную функцию, в LazySeq , указывающий на что-то вроде Cons . После преобразования любые последующие обращения быстро разрешатся в Cons es - где хранятся фактические значения. Когда одна ветвь map ziping проходит 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 (и, следовательно, Минусы - Минусы ), а крайний правый край расширяется только при первом вызове сначала , затем , или rest на заданном LazySeq .