-
Notifications
You must be signed in to change notification settings - Fork 0
/
excercise2.17~2.23.rkt
204 lines (166 loc) · 6.43 KB
/
excercise2.17~2.23.rkt
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#lang racket
;; Excercise 2.17:
;; Define a procedure last-pair that returns the list
;; that contains only the last element of a given (nonempty) list:
;; (last-pair (list 23 72 149 34))
;; (34)
(define (last-pair items)
(if (= (length items) 1)
(car items)
(last-pair (cdr items))))
;; Excercise 2.18:
;; Define a procedure reverse that takes a list as argument
;; and returns a list of the same elements in reverse order:
;; (reverse (list 1 4 9 16 25))
;; (25 16 9 4 1)
(define (myreverse items)
(if (null? items)
'()
(append (myreverse (cdr items)) (list (car items)))))
;; Excercise 2.19:
;; Consider the change-counting program of Section 1.2.2.
;; It would be nice to be able to easily change the currency used
;; by the program, so that we could compute the number of ways to
;; change a British pound, for example. As the program is written, the
;; knowledge of the currency is distributed partly into the procedure
;; first-denomination and partly into the procedure count-change
;; (which knows that there are five kinds of U.S. coins).
;; It would be nicer to be able to supply a list of coins to be used for making change.
;; We want to rewrite the procedure cc so that its second argument is
;; a list of the values of the coins to use rather than an integer specifying
;; which coins to use. We could then have lists that defined each kind of currency:
(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))
;; We could then call cc as follows:
;; (cc 100 us-coins)
;; => 292
;; To do this will require changing the program cc somewhat. It will
;; still have the same form, but it will access its second argument differently,
;; as follows:
(define (cc amount coin-values)
(cond ((= amount 0) 1)
((or (< amount 0) (no-more? coin-values)) 0)
(else
(+ (cc amount
(except-first-denomination
coin-values))
(cc (- amount
(first-denomination coin-values))
coin-values)))))
;; Define the procedures first-denomination, except-first-denomination
;; and no-more? in terms of primitive operations on list
;; structures. Does the order of the list coin-values affect the answer
;; produced by cc? Why or why not?
(define (first-denomination coins)
(car coins))
(define (except-first-denomination coins)
(cdr coins))
(define (no-more? coins)
(null? coins))
;(cc 100 us-coins)
;; The order of the list coin-values does not affect the answer,
;; because both getting coin value and using coin value are not related to order.
;; Excercise 2.20:
;; The procedures +, *, and list take arbitrary numbers
;; of arguments. One way to define such procedures is to use
;; define with dotted-tail notation. In a procedure definition, a parameter
;; list that has a dot before the last parameter name indicates
;; that, when the procedure is called, the initial parameters (if any)
;; will have as values the initial arguments, as usual, but the final parameter’s
;; value will be a list of any remaining arguments. For instance,
;; given the definition
;; (define (f x y . z) <body>)
;; the procedure f can be called with two or more arguments. If we
;; evaluate
;; (f 1 2 3 4 5 6)
;; then in the body of f, x will be 1, y will be 2, and z will be the list
;; (3 4 5 6). Given the definition
;; (define (g . w) <body>)
;; the procedure g can be called with zero or more arguments. If we
;; evaluate
;; (g 1 2 3 4 5 6)
;; then in the body of g, w will be the list (1 2 3 4 5 6).
;; Use this notation to write a procedure same-parity that takes one
;; or more integers and returns a list of all the arguments that have
;; the same even-odd parity as the first argument. For example,
;; (same-parity 1 2 3 4 5 6 7)
;; => (1 3 5 7)
;; (same-parity 2 3 4 5 6 7)
;; => (2 4 6)
(define (same-parity x . l)
(if (even? x)
(filter even? (cons x l))
(filter odd? (cons x l))))
;; Excercise 2.21:
;; The procedure square-list takes a list of numbers
;; as argument and returns a list of the squares of those numbers.
;; (square-list (list 1 2 3 4))
;; => (1 4 9 16)
(define (square-list items)
(define (square x) (* x x))
(if (null? items)
'()
(cons (square (car items)) (square-list (cdr items)))))
(define (square-list2 items)
(define (square x) (* x x))
(map square items))
;; Excercise 2.22:
;; Louis Reasoner tries to rewrite the first square-list
;; procedure of Exercise 2.21 so that it evolves an iterative process:
(define (Louis-square-list items)
(define (square x) (* x x))
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(cons (square (car things))
answer))))
(iter items '()))
;; Unfortunately, defining square-list this way produces the answer
;; list in the reverse order of the one desired. Why?
;; Louis then tries to fix his bug by interchanging the arguments to
;; cons:
(define (Louis-square-list-improve items)
(define (square x) (* x x))
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(cons answer
(square (car things))))))
(iter items '()))
;; The first one doesn't work because it conses the last item from the
;; front of the list to the answer, then gets the next item from the
;; front, etc.
;; The improved version conses the answer to the squared value,
;; but the answer is a list, so you'll end up with (list (list
;; ...) lastest-square).
;; one of the right answers:
(define (square-list-improve items)
(define (square x) (* x x))
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(append answer
(list (square (car things)))))))
(iter items '()))
;; Excercise 2.23:
;; The procedure for-each is similar to map. It takes
;; as arguments a procedure and a list of elements. However, rather
;; than forming a list of the results, for-each just applies the procedure
;; to each of the elements in turn, from left to right. The values
;; returned by applying the procedure to the elements are not used
;; at all—for-each is used with procedures that perform an action,
;; such as printing. For example,
;(for-each (lambda (x)
; (newline)
; (display x))
; (list 57 321 88))
; => 57
; 321
; 88
(define (my-for-each proc items)
(if (null? items)
(void)
(begin (proc (car items)) (my-for-each proc (cdr items)))))