Как реализовать Фибоначчи с генераторами?

Question

Я пытаюсь реализовать генераторы, чтобы составить список чисел Фибоначчи в Схеме, но я не могу этого сделать. У меня есть две функции, первая - это функция, которая возвращает числа Фибоначчи в виде списка, а вторая - функция генератора.

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

;FIBONACCI NUMBERS
(define (fib n a b i)
 (if
  (= i n)
  (list b)
 (cons b (fib n b (+ a b) (+ i 1)))
 )
)
(define (fibonacci n)
 (cond
 ((= n 1) (list 1))
 (else (fib n 0 1 1))
 )
)

;GENERATOR
(define (generator start stop step)
  (let ((current (- start 1)))
  (lambda ()
  (cond ((>= current stop) #f)
  (else
   (set! current (+ current step))
    current)))))

(define (next generator)
 (generator))

Answer 1

Когда вы пишете generators, люди будут думать о концепции generators в других языках, которые легко могут быть реализованы в Схеме с call/cc.

(define-coroutine (fib)
  (let loop ((a 0) (b 1))
    (yield a)
    (loop b (+ a b))))

(fib) ; ==> 0
(fib) ; ==> 1
(fib) ; ==> 1
(fib) ; ==> 2
(fib) ; ==> 3

Теперь это похоже на создание степпера из итерации. Это там с потоками и преобразователями. Вы можете создать функции отображения, которые будут составлять последовательные операции, которые будут выполнять расчеты для каждого элемента, вместо того, чтобы выполнять отдельные процессы, генерирующие множество коллекций между ними, как это делала бы цепочка map. В последние годы JavaScript был одним из важных моментов, связанных с генераторами, поскольку ранние версии await и async представляли собой сочетание генераторов и обещаний.

Теперь, если вы думаете больше в более общем смысле, это процедура, которая обрабатывает следующее значение. Вы также можете иметь это:

(define fib 
  (let ((a 0) (b 1))
    (lambda ()
      (let ((result a))
        (set! a b)
        (set! b (+ result b))
        result))))

(fib) ; ==> 0
(fib) ; ==> 1
(fib) ; ==> 1
(fib) ; ==> 2
(fib) ; ==> 3

Как видите, это происходит путем обновления личных привязок. Это больше ОО, чем фантазии настоящих генераторов.

Answer 2

Поскольку Sylwester упомянул потоки, вот решение stream -

(define fib
  (stream-cons 0
               (stream-cons 1
                            (stream-add fib
                                        (stream-rest fib)))))


(stream->list (stream-take fib 20))
; '(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

stream-add добавит два (2) потока вместе, используя +, и примитивы потока -

(define (stream-add s1 s2)
  (if (or (stream-empty? s1)
          (stream-empty? s2))
      empty-stream
      (stream-cons (+ (stream-first s1)
                      (stream-first s2))
                   (stream-add (stream-rest s1)
                               (stream-rest s2)))))

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

(define ((stream-lift f) . s)
  (if (ormap stream-empty? s)
      empty-stream
      (stream-cons (apply f (map stream-first s))
                   (apply (stream-lift f) (map stream-rest s)))))

(define stream-add (stream-lift +))