blob: 61373cd77017af8aa63746c42f5ff77980f6f514 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
#lang racket
;; fib.rkt - A variety of iterative implementations of the Fibonacci Sequence
;; All are based on accumulators
;; Natural -> Natural
;; produce the n'th Fibonacci number
(define (fib-iter n)
(cond
[(= n 0) 1]
[(= n 1) 1]
[else
(let-values ([(n-2 n-1)
;; i-2 = fib (i-2)
;; i-1 = fib (i-1)
(for/fold ([i-2 1] [i-1 1])
([i (in-range 2 n)])
(values i-1 (+ i-2 i-1)))])
(+ n-2 n-1))]))
(define (fib-iter2 n)
(cond
[(= n 0) 1]
[(= n 1) 1]
[else
;; i-2 = fib (i-2)
;; i-1 = fib (i-1)
(let loop ([i-2 1] [i-1 1] [i 2])
(if (= i n)
(+ i-2 i-1)
(loop i-1 (+ i-2 i-1) (add1 i))))]))
(define (fib-iter3 n)
(cond
[(= n 0) 1]
[(= n 1) 1]
[else
;; i-2 = fib (i-2)
;; i-1 = fib (i-1)
(do ([i-2 1 i-1]
[i-1 1 (+ i-2 i-1)]
[i 2 (add1 i)])
[(= i n)
(+ i-2 i-1)])]))
;; New variant of for with accumulators and a final expression in terms of
;; the accumulators
(define-syntax (for/acc stx)
(syntax-case stx ()
[(_ ([id* init*] ...)
(clauses ...)
body
result)
(with-syntax ([original stx])
#'(let-values ([(id* ...)
(for/fold/derived original
([id* init*] ...)
(clauses ...)
body)])
result))]))
(define (fib-iter4 n)
(cond
[(= n 0) 1]
[(= n 1) 1]
[else
;; i-2 = fib (i-2)
;; i-1 = fib (i-1)
(for/acc ([i-2 1] [i-1 1])
([i (in-range 2 n)])
(values i-1 (+ i-2 i-1))
(+ i-2 i-1))]))
;; New variant of for with accumulators and a final expression in terms of
;; the accumulators
(define-syntax (for/do stx)
(syntax-case stx ()
[(_ ([id* init* step*] ...)
(clauses ...)
result)
(with-syntax ([original stx])
#'(let-values ([(id* ...)
(for/fold/derived original
([id* init*] ...)
(clauses ...)
(values step* ...))])
result))]))
(define (fib-iter5 n)
(cond
[(= n 0) 1]
[(= n 1) 1]
[else
;; i-2 = fib (i-2)
;; i-1 = fib (i-1)
(for/do ([i-2 1 i-1] [i-1 1 (+ i-2 i-1)])
([i (in-range 2 n)])
(+ i-2 i-1))]))
;; Fibonacci's problem, as described by Greg Rawlins in "Compared to What":
;; Suppose you have a pair of rabbits and suppose every month each pair
;; bears a new pair that from the second month on becomes productive.
;; how many pairs of rabbits will you have in a year?
;; Analysis:
;; - At time 0 you have 1 unproductive pair: 1 pair, 0 productive pairs
;; - Each month, each productive pair produces an unproductive pair
;; - Each month, last months unproductive pairs transition to productive
;; - how many pairs are there at time step 12?
;; The following function solves the problem *directly* as a
;; structural recursion over natural numbers with two
;; accumulators (for lost context (fertile) and result-so-far (total))
;; Natural -> Natural
;; produce the solution to Fibonacci's problem after n months
(define (fib-rabbit n0)
;; Accumulator: total is Natural
;; Invariant: total pairs of rabbits after (- n0 n) months
;; Accumulator: fertile is Natural
;; Invariant: productive pairs of rabbits after (- n0 n) months
(local [(define (fib-acc fertile total n)
(cond [(zero? n) total]
[else
(fib-acc total ;; next month, all will be productive
(+ ;; next months pairs include:
total ;; - this months pairs plus
fertile) ;; - offspring from productive pairs
(sub1 n))]))]
(fib-acc 0 1 n0)))
|
