How to implement Fibonacci with generators?

Question

I'm trying to implement generators to make a list of fibonacci numbers in Scheme, but i can't do it. I have two functions, the first is a function that returns the Fibonacci numbers in the form of a list and the second is the generator function.

What I have to do is finally transform the Fibonacci function into a generator from a list of Fibonacci numbers.

;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))

Sylwester · Answer 1 · 2019-06-08T00:09:15.220

When you write generators people will think about the concept of generators in other lamnguages which can easily be implemented in Scheme withcall/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

Now this is kind of like making a stepper out of an iteration. It's up there with streams and transducers. You can make mapping functions that compose operations in series which does the calculations per item instead of doing separate processes generating lots of collections in between each one like chaining map would do. One of the big things in JavaScript the last years has been linked to generators since an early version of await and async were a combination of generators and promises.

Now if you are thinking more in the more general sense a procedure that proces the next value. You could have that as well:

(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

As you see this does the deed by updating private bindings. It's more OO than the fancy real generators.

what are "transducers" that you mention here? you mean like in JS/Clojure? or you have some Scheme reference in mind? (I've just found https://docs.racket-lang.org/rebellion/Transducers.html BTW). — Will Ness, Jun 21 '22 at 19:10

Mulan · Accepted Answer · 2019-06-08T18:28:50.750

Since Sylwester mentioned streams, here's a stream solution -

(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 will add two (2) streams together using + and stream primitives -

(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)))))

Or you can take a more generalised approach that allows use of any procedure and any number of streams -

(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 +))

How to implement Fibonacci with generators?

2 Answers2