Endless Fibonacci series, take only n from the list without using a mutation?

Question

I am trying to solve this problem in a purely functional way without using set! .

I wrote a function that calls a given lambda for every number in a fibonacci series, forever.

 (define (each-fib fn) (letrec ((next (lambda (ab) (fn a) (next b (+ ab))))) (next 0 1))) 

I think it is as brief as it can be, but if I can cut it, please enlighten me :)

With a definition like the one above, is it possible to write another function that takes the first n numbers from a Fibonacci series and gives me a list back, but without using a mutation variable to track the state (which I understand is not very functional).

The function signature does not have to be the same as the following ... any approach that each-fib will use without using set! is beautiful.

 (take-n-fibs 7) ; (0 1 1 2 3 5 8) 

I guess there are some extensions + a currying trick that I can use, but I keep returning to the desire to use set! that I am trying to avoid (purely for educational purposes / changing my thinking to purely functional).

Answer 1

Try this using lazy code using deferred evaluation :

 (define (each-fib fn) (letrec ((next (lambda (ab) (fn a) (delay (next b (+ ab)))))) (next 0 1))) (define (take-n-fibs n fn) (let loop ((in) (promise (each-fib fn))) (when (positive? i) (loop (sub1 i) (force promise))))) 

As already mentioned, each-fib can be further simplified with a help called let :

 (define (each-fib fn) (let next ((a 0) (b 1)) (fn a) (delay (next b (+ ab))))) 

In any case, it was necessary to slightly modify each-fib to use the delay primitive, which creates a promise:

A promise encapsulates an expression that will be evaluated on demand through force . After the promise was force d, each subsequent force of the promise gives the same result.

I can't think of a way to stop the original (unmodified) procedure from endless iteration. But with the change above, take-n-fibs can support lazy evaluating as many values ​​as possible and no more.

In addition, take-n-fibs now gets a function to print or process each value in turn, use it as follows:

 (take-n-fibs 10 (lambda (n) (printf "~a " n))) > 0 1 1 2 3 5 8 13 21 34 55 

Answer 2

You provide an iterative function on the fibonacci elements. If you want to accumulate the result instead of repeating each element, you should use a different primitive, which will be fold (or reduce ), and not iter .
(You could probably use continuations to turn iter into fold , but it would probably be less readable and less efficient than a direct solution using either fold or mutation.)

Note, however, that using a battery updated with a mutation is also great if you understand what you are doing: you use the state variable locally for convenience, but the take-n-fibs function, visible from the outside, is observationally clean, so you Do not “pollute” your program as a whole with side effects.

A quick prototype for fold-fib , adapted from your own code. I made an arbitrary choice regarding "when stop folding": if the function returns null , we return the current drive instead of continuing to bend.

 (define (fold-fib init fn) (letrec ([next (lambda (acc ab) (let ([acc2 (fn acc a)]) (if (null? acc2) acc (next acc2 b (+ ab)))))]) (next init 0 1))) (reverse (fold-fib '() (lambda (acc n) (if (> n 10) null (cons n acc))))) 

It would be better to have a more reliable agreement to put an end to folding.

Answer 3

I wrote several options. First you ask

 (define (each-fib fn) (letrec ((next (lambda (ab) (fn a) (next b (+ ab))))) (next 0 1))) 

can be written shorter. The template is used so often that a special named let syntax has been introduced. Your function looks like this using the name let:

 (define (each-fib fn) (let next ([a 0] [b 1]) (fn a) (next b (+ ab)))) 

In order to control transferred from one function to another, you can use the style of continued transmission in languages ​​with TCO support. Each function receives an additional argument, often called k (to continue). Function k is something to do next.

Using this style, you can write your program as follows:

 (define (generate-fibs k) (let next ([a 0] [b 1] [kk]) (ka (lambda (k1) (next b (+ ab) k1))))) (define (count-down nk) (let loop ([nn] [fibs '()] [next generate-fibs]) (if (zero? n) (k fibs) (next (λ (a next) (loop (- n 1) (cons a fibs) next)))))) (count-down 5 values) 

Now it’s a little annoying to write in style manually, so it can be convenient to enter cooperative routines. Violation of the rules for using set! I decided to use the generic fibs variable, in which generate-fibs repeatedly writes new fibonacci numbers. The count-down procedure simply reads the values ​​when the countdown ends.

 (define (make-coroutine co-body) (letrec ([state (lambda () (co-body resume))] [resume (lambda (other) (call/cc (lambda (here) (set! state here) (other))))]) (lambda () (state)))) (define fibs '()) (define generate-fib (make-coroutine (lambda (resume) (let next ([a 0] [b 1]) (set! fibs (cons a fibs)) (resume count-down) (next b (+ ab)))))) (define count-down (make-coroutine (lambda (resume) (let loop ([n 10]) (if (zero? n) fibs (begin (resume generate-fib) (loop (- n 1)))))))) (count-down) 

And a bonus you will get a version with shared streams:

 #lang racket (letrec ([result #f] [count-down (thread (λ () (let loop ([n 10] [fibs '()]) (if (zero? n) (set! result fibs) (loop (- n 1) (cons (thread-receive) fibs))))))] [produce-fibs (thread (λ () (let next ([a 0] [b 1]) (when (thread-running? count-down) (thread-send count-down a) (next b (+ ab))))))]) (thread-wait count-down) result) 

The stream version is specific to Racket, others should work anywhere.

Answer 4

Building a list would be difficult. But displaying the results can be done (very bad)

 #lang racket (define (each-fib fn) (letrec ((next (lambda (ab) (fn a) (next b (+ ab))))) (next 0 1))) (define (take-n-fibs n fn) (let/cc k (begin (each-fib (lambda (x) (if (= x (fib (+ n 1))) (k (void)) (begin (display (fn x)) (newline)))))))) (define fib (lambda (n) (letrec ((f (lambda (iab) (if (<= ni) a (f (+ i 1) b (+ ab)))))) (f 1 0 1)))) 

Please note that I use the regular fibonacci function as escape (as I said, very bad). I think no one will recommend such programs.

Anyway

 (take-n-fibs 7 (lambda (x) (* xx))) 0 1 1 4 9 25 64