1 ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 ;; about the language level of this file in a form that our tools can easily process.
3 #reader(lib "htdp-intermediate-reader.ss" "lang")((modname 17.8.12) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "dir.ss" "teachpack" "htdp") (lib "hangman.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "dir.ss" "teachpack" "htdp") (lib "hangman.ss" "teachpack" "htdp")))))
4 ;A list-of-numbers is either
5 ;1. empty or
6 ;2. (cons n lon)
7 ;where n is a number and lon is a list-of-numbers.
8 ;
9 ;list=?-1 and list=?-2 : list-of-numbers list-of-numbers -> boolean
10 ;Given lon1 and lon2, return true if the two lists are equal, false otherwise.
11 
12 ;(define (list=?-1 lon1 lon2)
13 ;  (cond
14 ;    [(and (empty? lon1)
15 ;          (empty? lon2)) true]
16 ;    [(and (cons? lon1)
17 ;          (empty? lon2)) false]
18 ;    [(and (empty? lon1)
19 ;          (cons? lon2)) false]
20 ;    [(and (cons? lon1)
21 ;          (cons? lon2)) (and (= (first lon1) (first lon2))
22 ;                             (list=?-1 (rest lon1) (rest lon2)))]))
23 
24 (define (list=?-1 lon1 lon2)
25   (cond
26     [(and (empty? lon1)
27           (empty? lon2)) true]
28     [(and (cons? lon1)
29           (cons? lon2)) (and (= (first lon1) (first lon2))
30                              (list=?-1 (rest lon1) (rest lon2)))]
31     [else false]))
32 
33 
34 (define (list=?-2 lon1 lon2)
35   (cond
36     [(empty? lon1) (empty? lon2)]
37     [(cons? lon1) (and (cons? lon2)
38                        (= (first lon1) (first lon2))
39                        (list=?-2 (rest lon1) (rest lon2)))]))
40    
41 ;Test
42 ;(list=?-2 empty empty)
43 ;(list=?-2 empty '(1))
44 ;(list=?-2 '(1) empty)
45 ;(list=?-2 '(1) '(1))
46 ;(list=?-2 '(1) '(1 2))
47 
48 ;A list-of-symbols is either
49 ;1. empty or
50 ;2. (cons s los)
51 ;where s is a symbol and los is a list-of-symbols.
52 ;
53 ;sym-list=? : list-of-symbols list-of-symbols -> boolean
54 (define (sym-list=? los1 los2)
55   (cond
56     [(and (empty? los1)
57           (empty? los2)) true]
58     [(and (cons? los1)
59           (cons? los2)) (and (symbol=? (first los1) (first los2))
60                              (sym-list=? (rest los1) (rest los2)))]
61     [else false]))
62 
63 ;sort-lon : list-of-numbers -> list-of-numbers
64 ;Given a-lon, sort lon.
65 
66 (define (sort-lon a-lon)
67   (cond
68     [(empty? a-lon) empty]
69     [(cons? a-lon) (insert-number (first a-lon) (sort-lon (rest a-lon)))]))
70 
71 ;insert-number : number list-of-numbers -> list-of-numbers
72 ;Given a-number and a-lon (sorted in ascending order), insert a-number in the proper position in lon to return the resulting sorted list-of-numbers.
73 
74 (define (insert-number a-number a-lon)
75   (cond
76     [(empty? a-lon) (list a-number)]
77     [(< a-number (first a-lon)) (append (list a-number)
78                                         a-lon)]
79     [else (append (list (first a-lon))
80                   (insert-number a-number (rest a-lon)))]))
81 
82 ;contains-same-numbers : list-of-numbers list-of-numbers -> boolean
83 ;Given lon1 and lon2, return true if the two lists have the same numbers, regardless of order.
84 
85 (define (contains-same-numbers lon1 lon2)
86   (list=?-1 (sort-lon lon1) (sort-lon lon2)))
87 
88 ;Data Definition
89 ;
90 ;An atom is either
91 ;1. a number,
92 ;2. a symbol, or
93 ;3. a boolean.
94 ;
95 ;A list-of-atoms is either
96 ;1. empty or 
97 ;2. (cons a loa)
98 ;where a is an atom and loa is a list-of-atoms.
99 ;
100 ;list-equal? : list-of-atoms list-of-atoms -> boolean
101 ;Given loa1 and loa2, determine if the two lists are equal (corresponding elements within the list have equivalent atoms).
102 
103 (define (list-equal? loa1 loa2)
104   (cond
105     [(and (empty? loa1)
106           (empty? loa2)) true]
107     [(and (cons? loa1)
108           (empty? loa2)) false]
109     [(and (empty? loa1)
110           (cons? loa2)) false]
111     [(and (cons? loa1)
112           (cons? loa2)) (and (atoms-equal? (first loa1) (first loa2))
113                              (list-equal? (rest loa1) (rest loa2)))]))
114     
115 ;atoms-equal? : atom atom -> boolean
116 ;Given atom1 and atom2, determine if the two atoms are equal.
117 
118 (define (atoms-equal? atom1 atom2)
119   (cond
120     [(and (number? atom1)
121           (number? atom2)) (= atom1 atom2)]
122     [(and (boolean? atom1)
123           (boolean? atom2)) (boolean=? atom1 atom2)]
124     [(and (symbol? atom1)
125           (symbol? atom2)) (symbol=? atom1 atom2)]
126     [else false]))
127 
128 ;(define atomic1 (list 5 'hi 'joe true false))
129 ;(define atomic2 (list 5 'hi 'joe true false))
130 
131 ;A web-page (wp) is either
132 ;1. empty,
133 ;2. (cons s wp), or
134 ;3. (cons ewp wp)
135 ;where s is a symbol, wp is a web-page (wp), and ewp is a web-page (wp).
136 
137 ;wp=? : wp wp -> boolean
138 ;Given wp1 and wp2, determine if the two web-pages are identical.
139 
140 (define (wp=? wp1 wp2)
141   (cond
142     [(empty? wp1) (empty? wp2)]
143     [(symbol? (first wp1)) (and (cons? wp2) (symbol? (first wp2))
144                                 (symbol=? (first wp1) (first wp2))
145                                 (wp=? (rest wp1) (rest wp2)))]
146     [(list? (first wp1)) (and (cons? wp2) (list? (first wp2))
147                               (wp=? (first wp1) (first wp2))
148                               (wp=? (rest wp1) (rest wp2)))]))
149 
150 ;(define empwp empty)
151 ;(define swpwp (cons 'firstPage (cons 'secondPage empty)))
152 ;(define ewpwp (cons (cons 'firstPage empty) (cons 'secondPage empty)))
153 ;
154 ;(wp=? empwp empwp)
155 ;(not (wp=? swpwp empwp))
156 ;(not (wp=? ewpwp empwp))
157 ;(not (wp=? empwp swpwp))
158 ;(wp=? swpwp swpwp)
159 ;(not (wp=? ewpwp swpwp))
160 ;(not (wp=? empwp ewpwp))
161 ;(not (wp=? swpwp ewpwp))
162 ;(wp=? ewpwp ewpwp)
163 
164 ;posn=? : posn posn -> boolean
165 ;Given posn1 and posn2, determine if they are equal.
166 
167 (define (posn=? posn1 posn2)
168   (and (posn? posn1) (posn? posn2)
169        (= (posn-x posn1) (posn-x posn2))
170        (= (posn-y posn1) (posn-y posn2))))
171 
172 (define-struct node (name left right))
173 
174 ;A binary tree (BT) either
175 ;1. empty or
176 ;2. (make-node name left right)
177 ;(make-node name left right)
178 ;where name is a symbol and left, right are binary trees (BT).
179 
180 ;tree=? : BT BT -> boolean
181 (define (tree=? bt1 bt2)
182   (cond
183     [(empty? bt1) (empty? bt2)]
184     [(node? bt1) (and (node? bt2)
185                       (tree=? (node-left bt1) (node-left bt2))
186                       (tree=? (node-right bt1) (node-right bt2)))]))
187 #|
188 Test
189 (define five (make-node 'five empty empty))
190 (define four (make-node 'four empty empty))
191 (define three (make-node 'three empty empty))
192 (define two (make-node 'two four five))
193 (define one (make-node 'one two three))
194 
195 (tree=? one one)
196 (not (tree=? one two))
197 (not (tree=? one three))
198 (not (tree=? two four))
199 
200 |#
201 
202 ;An Slist is either
203 ;1. empty or
204 ;2. (cons s sl)
205 ;where s is a Sexpr and sl is a Slist.
206 ;
207 ;An Sexpr is either
208 ;1. a number
209 ;2. a boolean
210 ;3. a symbol
211 ;4. a Slist.
212 ;
213 ;Slist=? Slist Slist -> boolean
214 ;Given Slist1 and Slist2, determines if the two Slists are identical.
215 
216 (define (Slist=? Slist1 Slist2)
217   (cond
218     [(empty? Slist1) (empty? Slist2)]
219     [(cons? Slist1) (and (cons? Slist2)
220                          (Sexpr=? (first Slist1) (first Slist2))
221                          (Slist=? (rest Slist1) (rest Slist2)))]))
222 
223 ;Sexpr=? Sexpr Sexpr -> boolean
224 ;Given Sexpr1 and Sexpr2, determines if the two Sexprs are identical.
225 
226 (define (Sexpr=? Sexpr1 Sexpr2)
227   (cond
228     [(number? Sexpr1) (and (number? Sexpr2)
229                            (= Sexpr1 Sexpr2))]
230     [(boolean? Sexpr1) (and (boolean? Sexpr2)
231                             (boolean=? Sexpr1 Sexpr2))]
232     [(symbol? Sexpr1) (and (symbol? Sexpr2)
233                            (symbol=? Sexpr1 Sexpr2))]
234     [(cons? Sexpr1) (and (cons? Sexpr2)
235                          (Slist=? Sexpr1 Sexpr2))]))
236 
237 ;An Slist is either
238 ;1. empty or
239 ;2. (cons s sl)
240 ;where s is a Sexpr and sl is a Slist.
241 ;
242 ;An Sexpr is either
243 ;1. a number
244 ;2. a boolean
245 ;3. a symbol
246 ;4. a Slist.
247 
248 ;(define Sexpr6 true)
249 ;(define Sexpr5 15)
250 ;(define Slist4 (cons Sexpr5 empty))
251 ;(define Sexpr2 Slist4)
252 ;(define Slist3 (cons Sexpr6 empty))
253 ;(define Slist2 (cons Sexpr2 Slist3))
254 ;(define Sexpr1 'FirstExpr)
255 ;(define Slist1 (cons Sexpr1 Slist2))
256 ;
257 ;(Slist=? empty empty)
258 ;(not (Slist=? empty (cons 15 empty)))
259 ;(not (Slist=? (cons 15 empty) empty))
260 ;(not (Slist=? (cons true empty) (cons false empty)))
261 ;(Slist=? Slist1 Slist1)
262 ;(not (Slist=? Slist2 Slist1))
263 ;(not (Slist=? Slist4 Slist2))
264 
265 ;A list-of-data (lod) is either
266 ;1. empty or
267 ;2. (cons d lod) where d is a Scheme datum and lod is a list-of-data.
268 ;
269 ;replace-eol-with : list-of-data list-of-data -> list-of-data
270 ;Given lod1 and lod2, append lod2 to the end of lod1.
271 
272 (define (replace-eol-with lod1 lod2)
273   (cond
274     [(empty? lod1) lod2]
275     [(cons? lod1) (cons (first lod1) (replace-eol-with (rest lod1) lod2))]))
276 
277 ;test-replace-eol-with : list-of-data list-of-data list-of-data -> boolean
278 ;Given lod1, lod2, and expected-result, append lod2 to the end of lod1 and see if it matches the expected result.
279 
280 (define (test-replace-eol-with lod1 lod2 expected-result)
281   (equal? (replace-eol-with lod1 lod2) expected-result))
282 
283 ;(test-replace-eol-with '(Hi My Name Is Joe) '(Nice To Meet You Joe) '(Hi My Name Is Joe Nice To Meet You Joe))
284 ;(not (test-replace-eol-with '(Hi My Name Is Joe) '(Nice To Meet You Joe) '(Hi My Name Is Joe Nice To Meet You Joey)))
285 
286 ;list-pick : list-of-symbols N[>=1] -> symbol
287 ;Given a-los and n, find the nth symbol in a-los.  The first symbol in a-los has an index of 1.
288 
289 (define (list-pick a-los n)
290   (cond
291     [(and (= n 1)
292           (empty? a-los)) (error 'list-pick "list too short")]
293     [(and (= n 1)
294           (cons? a-los)) (first a-los)]
295     [(and (> n 1)
296           (empty? a-los)) (error 'list-pick "list too short")]
297     [(and (> n 1)
298           (cons? a-los)) (list-pick (rest a-los) (sub1 n))]))
299 
300 (define los '(Fred Ted Bill Bob Joe))
301 
302 ;test-list-pick : list-of-symbols N[>=1] symbol -> boolean
303 
304 ;Given a-los, n, and expected-result, pick the n-th symbol from a-los using list-pick and see if it matches our expected-result.
305 
306 (define (test-list-pick a-los n expected-result)
307   (equal? expected-result (list-pick a-los n)))
308 
309 ;(test-list-pick los 3 'Bill)
310 ;(not (test-list-pick los 4 'Bill))
311 
312 test-evaluate 
313 
314 ;A SchemeData (a representation of a Scheme expression) is either
315 ;1. a number,
316 ;2. a symbol,
317 ;3. an operator structure, or
318 ;4. a function.
319 
320 (define-struct add (left right))
321 (define-struct sub (left right))
322 (define-struct mul (left right))
323 (define-struct div (left right))
324 
325 ;An operator is a structure
326 ;(make-operator left right)
327 ;where operator is replaced by one of the four operators:
328 ;1. add (addition)
329 ;2. sub (subtraction)
330 ;3. mul (multiplication)
331 ;4. div (division)
332 ;and left and right are SchemeData.
333 ;
334 ;An operator structure
335 ;(make-operator left right)
336 ;represents the expression
337 ;(operator left right)
338 ;in Scheme.
339 
340 (define-struct function (name arg))
341 
342 ;A function is a structure
343 ;(make-function name arg)
344 ;where name is a symbol and arg is a SchemeData.
345 ;
346 ;A function structure
347 ;(make-function name arg)
348 ;represents the expression
349 ;(name arg)