(define fibonacci-naïve
(λ (n)
"This function calculates the Fibonacci sequence naïvely."
(cond
((or (= 0 n) (= 1 n)) n)
(else (+ (fibonacci-naïve (- n 1))
(fibonacci-naïve (- n 2)))))))
(define fibonacci-linear
(λ (n)
"This function calculates the Fibonacci sequence sequentially."
(cond
((or (= 0 n) (= 1 n)) n)
(else
(cdr
(for/fold ((acc (cons 0 1))) ((i (in-range 2 (+ n 1))))
(cons (cdr acc) (+ (car acc) (cdr acc)))))))))
(define fibonacci-tail
(λ (n)
"This function calculates the Fibonacci sequence tail-optimized."
(letrec
((fibonacci-t
(λ (n p1 p2)
(cond
((= n 0) p1)
(else (fibonacci-t (- n 1) p2 (+ p1 p2)))))))
(fibonacci-t n 0 1))))
(define fibonacci-dijkstra
(λ (n)
"This function calculates the Fibonacci sequence with
Edsger W. Dijkstra's algorithm."
(letrec
((fibonacci-d
(λ (a b p q c)
(cond ((= c 0) b)
((even? c) (fibonacci-d a
b
(+ (* p p) (* q q))
(+ (* q q) (* 2 p q))
(/ c 2)))
(else (fibonacci-d (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- c 1)))))))
(fibonacci-d 1 0 0 1 n))))
(define-syntax run
(syntax-rules (with list and time)
((_ <fn> <range>)
(for ((i (in-range (car <range>) (cdr <range>))))(<fn> i)))
((_ with list <fn> <range>)
(for/list ((i (in-range (car <range>) (cdr <range>))))(<fn> i)))
((_ with time <fn> <range>)
(time (for ((i (in-range (car <range>) (cdr <range>))))(<fn> i))))
((_ with list and time <fn> <range>)
(time (for/list ((i (in-range (car <range>) (cdr <range>))))(<fn> i))))))
(fibonacci-naïve 30)
(fibonacci-linear 100000)
(fibonacci-tail 100000)
(fibonacci-dijkstra 100000)
(run with time fibonacci-naïve (cons 0 30))
(run with time fibonacci-linear (cons 0 1000))
(run with time fibonacci-tail (cons 0 1000))
(run with time fibonacci-dijkstra (cons 0 1000))