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-beginner-reader.ss" "lang")((modname 12.2.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 ;A natural-number is either
5 ;1. 0 or
6 ;2. (add1 n) where n is a natural-number
7 ;
8 ;! : natural-number -> natural number
9 ;Computes the factorial of n,
10 ;ie, n * (n-1) * (n-2)...2 * 1.
11 
12 (define (! n)
13   (cond
14     [(zero? n) 1]
15     [(>= n 1) (* n (! (sub1 n)))]))
16 ;
17 ;product : natural-number natural-number -> natural-number
18 ;Given m and n, and assuming m > n, computes (m!)/(n!).
19 
20 (define (product m n)
21   (/ (! m) (! n)))
22 
23 ;; f : number  ->  number
24 (define (f x)
25   (+ (* 3 (* x x)) 
26      (+ (* -6 x)
27         -1)))
28 
29 ;
30 ;A list-of-posns is either
31 ;1. an empty list or
32 ;2. (cons p lop) where p is a posn and lop is a list-of-posns.
33 ;tabulate-f20 : natural-number -> list-of-posns
34 ;Creates a "table".  Returns a list of n posns of the form
35 ;(cons (make-posn (f n) n) (cons (make-posn (f (- n 1) (- n 1)))...
36 ;Stops when n=20 (table includes n=20).
37 
38 (define (tabulate-f20 n)
39   (cond
40     [(< n 20) empty]
41     [else (cons (make-posn (f n) n) (tabulate-f20 (sub1 n)))]))
42 
43 ;
44 ;Let limit be a natural number. A natural number [>=limit] (N[>=limit])
45 ;is either
46 ;
47 ;1. limit or
48 ;2. (add1 n) where n is a natural number [>=limit].
49 
50 ;Contract, Purpose, Header
51 ;tabulate-f-lim : N[limit] N[>=limit] -> lop
52 ;Creates a table of posns containing the entries
53 ;(make-posn (f n) n) from n (inclusive) to limit (exclusive).
54 
55 (define (tabulate-f-lim limit n)
56   (cond
57     [(= n limit) empty]
58     [(> n limit) (cons (make-posn (f n) n) (tabulate-f-lim limit (sub1 n)))]))
59 
60 ;A natural-number [<=limit] (N[<=limit]) is either
61 ;1. limit or
62 ;2. (sub1 n) where n is a natural-number [<=limit].
63 
64 ;Contract, Purpose, Header
65 ;tabulate-f-lim-ascend : N[limit] N[<=limit] -> list-of-posns
66 ;Produces a list-of-posns (lop) of the form
67 ;1. empty list or
68 ;2. (cons (make-posn n (f n)) lop) where lop is a list-of-posns.
69 ;The list begins from n (inclusive) and ascends to limit (exclusive)
70 ;where we have defined that limit >= n.
71 ;
72 ;Template
73 (define (tabulate-f-lim-ascend limit n)
74   (cond
75     [(= limit n) empty]
76     [(>= limit n) (cons (make-posn n (f n))
77                         (tabulate-f-lim-ascend limit (add1 n)))]))
78 
79 ;A natural-number [>=1] (N[>=1]) is either
80 ;1. 1 or
81 ;2. (add1 n) where n is a natural-number [>=1].
82 ;
83 ;is-not-divisible-by<=i : N [>=1] N[>i] -> boolean 
84 ;Determines if m is divisible by any number between
85 ;1 (exclusive) and i (inclusive). Returns
86 ;true if the m is never divisible and false otherwise.
87 ;Template
88 
89 (define (is-not-divisible-by<=i i m)
90   (cond
91     [(= i 1) true]
92     [(> i 1) (and (not (zero? (remainder m i)))
93                   (is-not-divisible-by<=i (sub1 i) m))]))
94 ;
95 ;Purpose, Contract, Header
96 ;prime? : natural-number [>=2]
97 (define (prime? n)
98   (is-not-divisible-by<=i (round (sqrt n)) n))
99 ;
100 ;add : N N -> N
101 ;Adds n and x without using the + operator.
102 ;
103 ;Template
104 (define (add n x)
105   (cond
106     [(= x 0) n]
107     [(> x 0) (add1 (add n (sub1 x)))]))
108 
109 ;multiply : N N -> N
110 ;Multiplies n by x without using either
111 ;the + or * operator.
112 
113 (define (multiply n x)
114   (cond
115     [(zero? x) 0]
116     [(> x 0) (add n (multiply n (sub1 x)))]))
117 
118 ;A rational number [R] can be represented as a fraction
119 ;m/n where both m and n are natural-numbers.
120 
121 ;multiply-by-rational : R N -> R
122 ;Given a natural-number x, multiply by rational-number n.
123 
124 ;(define (multiply-by-rational n x)
125 ;  (cond
126 ;    [(zero? x) 0]
127 ;    [(> x 0) (add-rational n (multiply-by-rational n (sub1 x)))]))
128 
129 ;add-rational : R R -> R
130 ;Given two rational-numbers n and x,
131 ;add the two numbers.
132 ;This is hard...give up
133 ;
134 ;exponent : N N -> N
135 ;Raises x to the nth power.
136 
137 (define (exponent x n)
138   (cond
139     [(zero? n) 1]
140     [(> n 0) (multiply (exponent x (sub1 n)) x)]))
141 ;
142 ;A deep-list is either
143 ;1. a symbol or
144 ;2. (cons dl empty) where dl is a deep-list.
145 
146 ;depth : deep-list -> number
147 ;Consumes a deep-list dl and determines how many
148 ;cons were used to construct it.
149 ;
150 ;Examples
151 ;(depth (cons (cons (cons 'food empty) empty) empty))
152 ;3
153 ;(depth (cons 'food empty))
154 ;1
155 ;(depth 'food)
156 ;0
157 
158 (define (depth dl)
159   (cond
160     [(symbol? dl) 0]
161     [(cons? dl) (+ 1 (depth (first dl)))]))
162 
163 ;make-deep : symbol natural-number -> deep-list
164 ;Consumes word and n to produce a deep-list
165 ;containing word constructed using n cons's.
166 ;
167 ;Examples:
168 ;(make-deep 'hey 3)
169 ;(cons (cons (cons 'hey empty) empty) empty)
170 ;(make-deep 'hey 0)
171 ;'hey
172 ;(make-deep 'hey 1)
173 ;(cons 'hey empty)
174 ;
175 ;Template
176 ;(define (make-deep word n)
177 ;  (cond
178 ;    [(zero? n) ...]
179 ;    [(> n 0) ... (make-deep word (sub1 n))]))
180 
181 (define (make-deep word n)
182   (cond
183     [(zero? n) word]
184     [(> n 0) (cons (make-deep word (sub1 n)) empty)]))
185 
186 ;Let the depth of a deep-list represent a natural-number.
187 ;The depth of a deep-list represents the number of cons
188 ;used to construct it.
189 ;
190 ;Some examples:
191 ;1. anysymbol represents 0,
192 ;2. (cons anysymbol empty) represents 1
193 ;3. (cons (cons anysymbol empty)) represents 2,
194 ;and so forth, where anysymbol is a symbol.
195 ;
196 ;Hence, we can represent
197 ;1.0 as (make-deep 'anysymbol 0)
198 ;2.3 as (make-deep 'anysymbol 3)
199 ;3.8 as (make-deep 'anysymbol 8).
200 ;
201 ;addDL : deep-list deep-list -> deep-list
202 ;Given dl1 and dl2, produces a new deep-list
203 ;that represents the sum of the natural numbers
204 ;of dl1 and dl2.  In other words,
205 ;produces a new deep-list as deep as the sum of
206 ;the depth of dl1 and dl2.
207 
208 (define (addDL dl1 dl2)
209   (make-deep 'anysymbol (+ (depth dl1) (depth dl2))))
210 
211 (define DEEPLIST1 (make-deep 'anysymbol 5))
212 (define DEEPLIST2 (make-deep 'anysymbol 8))