Ряд Фибоначчи

Давеча рекламировал свои обобщенные последовательности (Generic Sequences), а какие могут быть последовательности без ряда Фибоначчи? Это что-то вроде обязательного ритуала. Опустим здесь тот факт, что я создал эту библиотеку для вполне практической задачи, когда мне понадобилось быстро и эффективно сравнивать деревья, а там ленивые последовательности дюже полезны.

Итак, ниже приведена рабоче-крестьянская версия, которая выдает ленивую бесконечную последовательности ряда Фибоначчи через то, что я назвал Sequence Comprehension:

(defparameter *fibs-1*
  (with-seq/cc
    (do ((a 1 b)
         (b 1 (+ a b)))
        (nil)
      (yield/cc a))))

Очень просто, не правда ли?

Теперь каноническая версия через поток:

(defparameter *fibs-2*
  (reclet 
      ((fibs (seq->stream
              (seq-cons
               1 (seq-cons
                  1 (seq-map
                     (lambda (x)
                       (+ (first x) (second x)))
                     (seq-zip
                      (delay-seq fibs)
                      (delay-seq (seq-cdr fibs)))))))))
    fibs))

Проверка:

? (seq->list (seq-take 20 *fibs-1*))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

? (seq->list (seq-take 20 *fibs-2*))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

Дополнение.

Чтобы не сложилось неправильного впечатления, сейчас покажу наиболее эффективную реализацию, которая только возможна в рамках моей библиотеки.

(defparameter *fibs-3*
  (make-seq
   (labels ((traverse (a b)
              (enum-cons a (traverse b (+ a b)))))
     (traverse 1 1))))

Основная идея заключается в том, что мы работаем как с обычным списком, что очень удобно при обходе индуктивных/рекурсивных структур данных. Собственно, все комбинаторы написаны у меня в таком стиле.

И если вам по какой-то причине не нравятся комбинаторы, то результат можно получить с помощью известного макроса iter, для которого я добавил конструкцию in-seq:

? (iter (for i from 1 to 20)
        (for x in-seq *fibs-3*)
        (collect x))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)