Давеча рекламировал свои обобщенные последовательности (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)
