1 12687dd9 2023-08-04 jrmu ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 12687dd9 2023-08-04 jrmu ;; about the language level of this file in a form that our tools can easily process.
3 12687dd9 2023-08-04 jrmu #reader(lib "htdp-beginner-reader.ss" "lang")((modname 11.4.1) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp")))))
4 12687dd9 2023-08-04 jrmu ;A natural-number is either
6 12687dd9 2023-08-04 jrmu ;2. (add1 n) where n is a natural-number
8 12687dd9 2023-08-04 jrmu ;! : natural-number -> natural number
9 12687dd9 2023-08-04 jrmu ;Computes the factorial of n,
10 12687dd9 2023-08-04 jrmu ;ie, n * (n-1) * (n-2)...2 * 1.
12 12687dd9 2023-08-04 jrmu (define (! n)
14 12687dd9 2023-08-04 jrmu [(zero? n) 1]
15 12687dd9 2023-08-04 jrmu [(>= n 1) (* n (! (sub1 n)))]))
17 12687dd9 2023-08-04 jrmu ;product : natural-number natural-number -> natural-number
18 12687dd9 2023-08-04 jrmu ;Given m and n, and assuming m > n, computes (m!)/(n!).
20 12687dd9 2023-08-04 jrmu (define (product m n)
21 12687dd9 2023-08-04 jrmu (/ (! m) (! n)))
23 12687dd9 2023-08-04 jrmu ;; f : number -> number
24 12687dd9 2023-08-04 jrmu (define (f x)
25 12687dd9 2023-08-04 jrmu (+ (* 3 (* x x))
30 12687dd9 2023-08-04 jrmu ;A list-of-posns is either
31 12687dd9 2023-08-04 jrmu ;1. an empty list or
32 12687dd9 2023-08-04 jrmu ;2. (cons p lop) where p is a posn and lop is a list-of-posns.
33 12687dd9 2023-08-04 jrmu ;tabulate-f20 : natural-number -> list-of-posns
34 12687dd9 2023-08-04 jrmu ;Creates a "table". Returns a list of n posns of the form
35 12687dd9 2023-08-04 jrmu ;(cons (make-posn (f n) n) (cons (make-posn (f (- n 1) (- n 1)))...
36 12687dd9 2023-08-04 jrmu ;Stops when n=20 (table includes n=20).
38 12687dd9 2023-08-04 jrmu (define (tabulate-f20 n)
40 12687dd9 2023-08-04 jrmu [(< n 20) empty]
41 12687dd9 2023-08-04 jrmu [else (cons (make-posn (f n) n) (tabulate-f20 (sub1 n)))]))
44 12687dd9 2023-08-04 jrmu ;Let limit be a natural number. A natural number [>=limit] (N[>=limit])
47 12687dd9 2023-08-04 jrmu ;1. limit or
48 12687dd9 2023-08-04 jrmu ;2. (add1 n) where n is a natural number [>=limit].
50 12687dd9 2023-08-04 jrmu ;Contract, Purpose, Header
51 12687dd9 2023-08-04 jrmu ;tabulate-f-lim : N[limit] N[>=limit] -> lop
52 12687dd9 2023-08-04 jrmu ;Creates a table of posns containing the entries
53 12687dd9 2023-08-04 jrmu ;(make-posn (f n) n) from n (inclusive) to limit (exclusive).
55 12687dd9 2023-08-04 jrmu (define (tabulate-f-lim limit n)
57 12687dd9 2023-08-04 jrmu [(= n limit) empty]
58 12687dd9 2023-08-04 jrmu [(> n limit) (cons (make-posn (f n) n) (tabulate-f-lim limit (sub1 n)))]))
60 12687dd9 2023-08-04 jrmu ;A natural-number [<=limit] (N[<=limit]) is either
61 12687dd9 2023-08-04 jrmu ;1. limit or
62 12687dd9 2023-08-04 jrmu ;2. (sub1 n) where n is a natural-number [<=limit].
64 12687dd9 2023-08-04 jrmu ;Contract, Purpose, Header
65 12687dd9 2023-08-04 jrmu ;tabulate-f-lim-ascend : N[limit] N[<=limit] -> list-of-posns
66 12687dd9 2023-08-04 jrmu ;Produces a list-of-posns (lop) of the form
67 12687dd9 2023-08-04 jrmu ;1. empty list or
68 12687dd9 2023-08-04 jrmu ;2. (cons (make-posn n (f n)) lop) where lop is a list-of-posns.
69 12687dd9 2023-08-04 jrmu ;The list begins from n (inclusive) and ascends to limit (exclusive)
70 12687dd9 2023-08-04 jrmu ;where we have defined that limit >= n.
73 12687dd9 2023-08-04 jrmu (define (tabulate-f-lim-ascend limit n)
75 12687dd9 2023-08-04 jrmu [(= limit n) empty]
76 12687dd9 2023-08-04 jrmu [(>= limit n) (cons (make-posn n (f n))
77 12687dd9 2023-08-04 jrmu (tabulate-f-lim-ascend limit (add1 n)))]))
79 12687dd9 2023-08-04 jrmu ;A natural-number [>=1] (N[>=1]) is either
81 12687dd9 2023-08-04 jrmu ;2. (add1 n) where n is a natural-number [>=1].
83 12687dd9 2023-08-04 jrmu ;is-not-divisible-by<=i : N [>=1] N[>i] -> boolean
84 12687dd9 2023-08-04 jrmu ;Determines if m is divisible by any number between
85 12687dd9 2023-08-04 jrmu ;1 (exclusive) and i (inclusive). Returns
86 12687dd9 2023-08-04 jrmu ;true if the m is never divisible and false otherwise.
89 12687dd9 2023-08-04 jrmu (define (is-not-divisible-by<=i i m)
91 12687dd9 2023-08-04 jrmu [(= i 1) true]
92 12687dd9 2023-08-04 jrmu [(> i 1) (and (not (zero? (remainder m i)))
93 12687dd9 2023-08-04 jrmu (is-not-divisible-by<=i (sub1 i) m))]))
95 12687dd9 2023-08-04 jrmu ;Purpose, Contract, Header
96 12687dd9 2023-08-04 jrmu ;prime? : natural-number [>=2]
97 12687dd9 2023-08-04 jrmu (define (prime? n)
98 12687dd9 2023-08-04 jrmu (is-not-divisible-by<=i (round (sqrt n)) n))
100 12687dd9 2023-08-04 jrmu ;add : N N -> N
101 12687dd9 2023-08-04 jrmu ;Adds n and x without using the + operator.
104 12687dd9 2023-08-04 jrmu (define (add n x)
106 12687dd9 2023-08-04 jrmu [(= x 0) n]
107 12687dd9 2023-08-04 jrmu [(> x 0) (add1 (add n (sub1 x)))]))
109 12687dd9 2023-08-04 jrmu ;multiply : N N -> N
110 12687dd9 2023-08-04 jrmu ;Multiplies n by x without using either
111 12687dd9 2023-08-04 jrmu ;the + or * operator.
113 12687dd9 2023-08-04 jrmu (define (multiply n x)
115 12687dd9 2023-08-04 jrmu [(zero? x) 0]
116 12687dd9 2023-08-04 jrmu [(> x 0) (add n (multiply n (sub1 x)))]))
118 12687dd9 2023-08-04 jrmu ;A rational number [R] can be represented as a fraction
119 12687dd9 2023-08-04 jrmu ;m/n where both m and n are natural-numbers.
121 12687dd9 2023-08-04 jrmu ;multiply-by-rational : R N -> R
122 12687dd9 2023-08-04 jrmu ;Given a natural-number x, multiply by rational-number n.
124 12687dd9 2023-08-04 jrmu ;(define (multiply-by-rational n x)
126 12687dd9 2023-08-04 jrmu ; [(zero? x) 0]
127 12687dd9 2023-08-04 jrmu ; [(> x 0) (add-rational n (multiply-by-rational n (sub1 x)))]))
129 12687dd9 2023-08-04 jrmu ;add-rational : R R -> R
130 12687dd9 2023-08-04 jrmu ;Given two rational-numbers n and x,
131 12687dd9 2023-08-04 jrmu ;add the two numbers.
132 12687dd9 2023-08-04 jrmu ;This is hard...give up
134 12687dd9 2023-08-04 jrmu ;exponent : N N -> N
135 12687dd9 2023-08-04 jrmu ;Raises x to the nth power.
137 12687dd9 2023-08-04 jrmu (define (exponent x n)
139 12687dd9 2023-08-04 jrmu [(zero? n) 1]
140 12687dd9 2023-08-04 jrmu [(> n 0) (multiply (exponent x (sub1 n)) x)]))
142 12687dd9 2023-08-04 jrmu A deep-list is either
143 12687dd9 2023-08-04 jrmu 1. a symbol or
144 12687dd9 2023-08-04 jrmu 2. (cons dl empty) where dl is a deep-list.
146 12687dd9 2023-08-04 jrmu ;depth : deep-list -> number
147 12687dd9 2023-08-04 jrmu ;Consumes a deep-list dl and determines how many
148 12687dd9 2023-08-04 jrmu ;cons were used to construct it.
151 12687dd9 2023-08-04 jrmu ;(depth (cons (cons (cons 'food empty) empty) empty))
153 12687dd9 2023-08-04 jrmu ;(depth (cons 'food empty))
155 12687dd9 2023-08-04 jrmu ;(depth 'food)
158 12687dd9 2023-08-04 jrmu (define (depth dl)
160 12687dd9 2023-08-04 jrmu [(symbol? dl) 0]
161 12687dd9 2023-08-04 jrmu [(cons? dl) (+ 1 (depth (first dl)))]))
163 12687dd9 2023-08-04 jrmu ;make-deep : symbol natural-number -> deep-list
164 12687dd9 2023-08-04 jrmu ;Consumes word and n to produce a deep-list
165 12687dd9 2023-08-04 jrmu ;containing word constructed using n cons's.
168 12687dd9 2023-08-04 jrmu ;(make-deep 'hey 3)
169 12687dd9 2023-08-04 jrmu ;(cons (cons (cons 'hey empty) empty) empty)
170 12687dd9 2023-08-04 jrmu ;(make-deep 'hey 0)
172 12687dd9 2023-08-04 jrmu ;(make-deep 'hey 1)
173 12687dd9 2023-08-04 jrmu ;(cons 'hey empty)
176 12687dd9 2023-08-04 jrmu ;(define (make-deep word n)
178 12687dd9 2023-08-04 jrmu ; [(zero? n) ...]
179 12687dd9 2023-08-04 jrmu ; [(> n 0) ... (make-deep word (sub1 n))]))
181 12687dd9 2023-08-04 jrmu (define (make-deep word n)
183 12687dd9 2023-08-04 jrmu [(zero? n) word]
184 12687dd9 2023-08-04 jrmu [(> n 0) (cons (make-deep word (sub1 n)) empty)]))
186 12687dd9 2023-08-04 jrmu ;Let the depth of a deep-list represent a natural-number.
187 12687dd9 2023-08-04 jrmu ;The depth of a deep-list represents the number of cons
188 12687dd9 2023-08-04 jrmu ;used to construct it.
190 12687dd9 2023-08-04 jrmu ;Some examples:
191 12687dd9 2023-08-04 jrmu ;1. anysymbol represents 0,
192 12687dd9 2023-08-04 jrmu ;2. (cons anysymbol empty) represents 1
193 12687dd9 2023-08-04 jrmu ;3. (cons (cons anysymbol empty)) represents 2,
194 12687dd9 2023-08-04 jrmu ;and so forth, where anysymbol is a symbol.
196 12687dd9 2023-08-04 jrmu ;Hence, we can represent
197 12687dd9 2023-08-04 jrmu ;1.0 as (make-deep 'anysymbol 0)
198 12687dd9 2023-08-04 jrmu ;2.3 as (make-deep 'anysymbol 3)
199 12687dd9 2023-08-04 jrmu ;3.8 as (make-deep 'anysymbol 8).
201 12687dd9 2023-08-04 jrmu ;addDL : deep-list deep-list -> deep-list
202 12687dd9 2023-08-04 jrmu ;Given dl1 and dl2, produces a new deep-list
203 12687dd9 2023-08-04 jrmu ;that represents the sum of the natural numbers
204 12687dd9 2023-08-04 jrmu ;of dl1 and dl2. In other words,
205 12687dd9 2023-08-04 jrmu ;produces a new deep-list as deep as the sum of
206 12687dd9 2023-08-04 jrmu ;the depth of dl1 and dl2.
208 12687dd9 2023-08-04 jrmu (define (addDL dl1 dl2)
209 12687dd9 2023-08-04 jrmu (make-deep 'anysymbol (+ (depth dl1) (depth dl2))))
211 12687dd9 2023-08-04 jrmu (define DEEPLIST1 (make-deep 'anysymbol 5))
212 12687dd9 2023-08-04 jrmu (define DEEPLIST2 (make-deep 'anysymbol 8))
