10 result: 10 (+ 5 3 4) result: 12 (- 9 1) result: 8 (/ 6 2) result: 3 (+ (* 2 4) (- 4 6)) result: 6 (define a 3) result: ;Value: a… this represents variable definition (define b (+ a 1)) result: ;Value: b… this represent function definition (+ a b (* a b)) result: 19 (= a b) result: #f (if (and (> b a) (< b (* a b))) b a) result: 4 (cond ((= a 4) 6) ((= b 4) (+ 6 7 a)) (else 25)) result: 16 (+ 2 (if (> b a) b a)) result: 6 (* (cond ((> a b) a) ((< a b) b) (else -1)) (+ a 1)) result: 16
Transform the following expresssion into prefix form: (5 + 4 + (3 - (3 - (6 + 4/5))))/(3(6 - 3)(3 - 7)) (/ (+ 5
4
(- 2
(- 3
(+ 6 (/ 4 5)))))
(* 3
(- 6 2)
(- 2 7))) (define (max_iter list max)
(cond ((null? list) max)
((> max (car list)) (max_iter (cdr list) max))
(else (max_iter (cdr list) (car list)))))
(define (max list) (max_iter list (car list)))
(define (remove_from_list_iter element inputList outputList removed)
(cond ((null? inputList) outputList)
((or removed (not (equal? element (car inputList)))) (remove_from_list_iter element (cdr inputList) (cons (car inputList) outputList) removed))
(else (remove_from_list_iter element (cdr inputList) outputList #t)))
)
(define (remove_from_list element list) (remove_from_list_iter element list '() #f))
(define (square a) (* a a))
(define (sum_of_square_of_two_largest a b c) (+ (square (max (list a b c))) (square (max (remove_from_list (max (list a b c)) (list a b c))))))
(sum_of_square_of_two_largest 1 2 3)(define (a-plus-abs-b a b) ((if (> b 0) + -) a b))
Answer: When b is greater than cero a and b get added otherwise we substract b from a (given that b would be negative this resuls in this (a -(-b)))
Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order evaluation or normal-order evaluation. He defines the following two procedures: (define (p) (p))(define (test x y) (if (= x 0) 0 y)) Then he evaluates the expression (test 0 (p)) What behavior will Ben observe with an interpreter that uses applicative-order evaluation? What behavior will he observe with an interpreter that uses normal-order evaluation? Explain your answer.
Answer: Applicative Order Evaluation: It will fist evaluate the arguments of the (test 0 (p)) call and when it evaluates (p) p will call itself recursively at infinitum. Normal Order Evaluation: It will expand the test function before evaluating the arguments resulting in:
(if (= 0 0) 0 (p)))
then the if statement will evaluate the condition (which resolves to true) and the function would finally return 0 never reaching the (p) call.
Alyssa P. Hacker doesn’t see why if needs to be provided as a special form. “Why can’t I just define it as an ordinary procedure in terms of cond?” she asks. Alyssa’s friend Eva Lu Ator claims this can indeed be done, and she defines a new version of if: (define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause))) Eva demonstrates the program for Alyssa: (new-if (= 2 3) 0 5) 5(new-if (= 1 1) 0 5) 0
Delighted, Alyssa uses new-if to rewrite the square-root program:
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
(define (average x y)
(/ (+ x y) 2))
(define (improve guess x)
(average guess (/ x guess)))
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
(define (sqrt x)
(sqrt-iter 1.0 x)) What happens when Alyssa attempts to use this to compute square roots? Explain.
The sqrt function will infinetely recurse because the new-if function within it uses applicative order evaluation. That means that the sqrt-iter will keep calling itself again and again even when the guess is good enough. This doesn’t happen with the special form ‘if’ because it only calls sqrt-iter if the guess is not good enough.
If the interpreter used Normal order evaluation it would not infinetely recurse because it would reach the ‘cond’ special form and that would serve to stop the infinite recursion through the condition check.
Normal-Order-Evaluation (sqrt 2)
(sqrt-iter 1 2)
(new-if (good-enough? 1 2) 1 (sqrt-iter (improve 1 2) 2))
(cond ((good-enough? 1 2) 1) <------- here we have the cond special form that will prevent (else (sqrt-iter (improve 1 2) 2))) the execution of sqrt-iter when the guess is good enough
The good-enough? test used in computing square roots will not be very effective for finding the square roots of very small numbers. Also, in real computers, arithmetic operations are almost always performed with limited precision. This makes our test inadequate for very large numbers. Explain these statements, with examples showing how the test fails for small and large numbers. An alternative strategy for implementing good-enough? is to watch how guess changes from one iteration to the next and to stop when the change is a very small fraction of the guess. Design a square-root procedure that uses this kind of end test. Does this work better for small and large numbers?For very large numbers the tolerance being so small will keep the program in an infinite loop because due to limited precission the difference between the square of the guess and the input number will never be smaller than the tolerance. For very small number you’ll fulfill the tolerance condition way before finding a reasonable approximation for the sqrt value.
Improved srt: The idea is to check whether the guess is good enough by checking how much it is changing between iterations not how close it is to the expected value
(define (average x y)
(/ (+ x y) 2))
(define (square x) (* x x))
(define (improve guess x)
(average guess (/ x guess)))
(define (abs x) (if (< x 0) (- x) x))
(define (good-enough? guess x)
(> 0.00001 (abs (- (improve guess x) guess))))
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
(define (sqrt x)
(sqrt-iter 1 x))
(sqrt 0.000001) (define (average x y)
(/ (+ x y) 2))
(define (square x) (* x x))
(define (improve guess x)
(/
(+ (* 2 guess)
(/ x (square guess)))
3))
(define (abs x) (if (< x 0) (- x) x))
(define (good-enough? guess x)
(> 0.00001 (abs (- (improve guess x) guess))))
(define (cbrt-iter guess x)
(if (good-enough? guess x)
guess
(cbrt-iter (improve guess x)
x)))
(define (cbrt x)
(cbrt-iter 1 x))
(cbrt 27.0) Using the substitution model, illustrate the process generated by each procedure in evaluating (+ 4 5) . Are these processes iterative or recursive?
Procedure 1:
(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b))))(+ 4 5) (inc (+ 3 5)) (inc (inc (+ 2 5))) (inc (inc (inc (+ 1 5)))) (inc (inc (inc (inc (+ 0 5))))) (inc (inc (inc (inc 5)))) (inc (inc (inc 6))) (inc (inc 7)) (inc 8) 9
This is a recursive process as evidenced by the incresing number of pending operations that accumulate and then resolve after reaching the base condition.
Procedure 2:
(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))(+ 4 5) (+ 3 6) (+ 2 7) (+ 1 8) (+ 0 9) 9
This is an iterative process as evidenced by its set of variables (in this case a and b) that fully define the stage in the iterations and its lack of pending operations.
The following procedure computes a mathematical function called Ackermann’s function.
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))What are the values of the following expressions? (A 1 10) result: 1024 (A 2 4) result: 65536 (A 3 3) result: 65536
Consider the following procedures, where A is the procedure defined above and give concise mathematical definitions for the functions computed by the procedures f , g , and h for positive integer values of n.
(define (f n) (A 0 n)) computes: 2*n y=-0 -> 0 and y=1 –> 2 (define (g n) (A 1 n)) computes: 2^n y=-0 -> 0 and y=1 –> 2 (define (h n) (A 2 n)) computes: 2^(2^2^2) ..... (n - 1) times y=-0 -> 0 and y=1 –> 2 (define (k n) (* 5 n n)) computes: 5n^2
A function f is defined by the rule that f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n>=3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.
Recursive:
(define (f n)
(cond ((< n 3) n)
(else (+ (f (- n 1))
(* 2 (f (- n 2)))
(* 3 (f (- n 3)))))))
(f 4)Iterative:
(define (f_iter a b c n count)
(cond ((< n 3) n)
((= count n) a)
(else (f_iter (+ a (* 2 b) (* 3 c)) a b n (+ count 1)))
))
(define (f n)
(f_iter 2 1 0 n 2))
(f 4)The following pattern of numbers is called Pascal’s triangle. The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it. 35 Write a procedure that computes elements of Pascal’s triangle by means of a recursive process.
0 0 1 0 0 1 1 0 0 1 2 1 0 0 1 3 3 1 0 0 1 4 6 4 1 0
(pascal row column) ===> number
; 0
; 0 1 0
; |0 |1| 1| 0
; 0 |1 2| 1 0
; 0 1 |3| 3 1 0
; 0 1 4 6 4 1 0
;(pascal 3 1) => (pascal 2 0) + (pascal 2 1)
;(pascal 2 0) => (pascal 1 -1) + (pascal 1 0)
;(pascal 2 1) => (pascal 1 0) + (pascal 1 1)
(define (pascal row column)
(cond ((< row 0) 0)
((< column 0) 0)
((> column row ) 0)
((and (= row 0) (= column 0)) 1)
(else (+ (pascal (- row 1) column)
(pascal (- row 1) (- column 1))))))
(pascal 4 2)Prove that Fib(n) is the closest integer to n / 5, where = (1 + 5)/2. Hint: Let = (1 - 5)/2. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that Fib(n) = ( n - n )/ 5.
Fib(n) = Fib(n - 1) + Fib(n - 2)
Fib(n) = (a^n - b^n)/(5)^(1/2)
(a^n - b^n)/(5)^(1/2) = (a^(n - 1) - b^(n - 1))/(5)^(1/2) + (a^(n -2) - b^(n -2))/(5)^(1/2)
a^n - b^n = a^(n - 1) - b^(n - 1) + a^(n -2) - b^(n -2)
.... go here for the full proof: https://codology.net/post/sicp-solution-exercise-1-13/
Draw the tree illustrating the process generated by the count-change procedure of section 1.2.2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))
(count-change 11)(count-change 11)
(cc 11 5)__
| \ |
(cc 11 4) (cc -39 5)
| \___ |
| \ |
(cc 11 3) (cc -14 4)
| \_______________________________________________________ |
| \ |
(cc 11 2) (cc 1 3)
| \_________________________ | \__ |
| \ | \ |
(cc 11 1) (cc 6 2) (cc 1 2) (cc -9 3)
| \___ | \__ | \__ |
| \ | \ | \ |
(cc 11 0) (cc 10 1) (cc 6 1) (cc 1 2) (cc 1 1) (cc -4 2) / | / | | \__ | \__ / | / | | \ | \ (cc 10 0) (cc 9 1) (cc 6 0) (cc 5 1) (cc 1 1) (cc -4 2) (cc 1 0) (cc 0 1) / | / | | \__ / | / | | \ (cc 9 0) (cc 8 1) (cc 5 0) (cc 4 1) (cc 1 0) (cc 0 1) __/ | __/ | / | / | (cc 8 0) (cc 7 1) (cc 4 0) (cc 3 1) __/ | __/ | / | / | (cc 7 0) (cc 6 1) (cc 3 0) (cc 2 1) __/ | __/ | / | / | (cc 6 0) (cc 5 1) (cc 2 0) (cc 1 1) __/ | __/ | / | / | (cc 5 0) (cc 4 1) (cc 1 0) (cc 0 1) __/ | / | (cc 4 0) (cc 3 1) __/ | / | (cc 3 0) (cc 2 1) __/ | / | (cc 2 0) (cc 1 1) __/ | / | (cc 1 0) (cc 0 1)
- Space complexity: When we analyse the tree of calls generated by the cc procedure we can observe that the maximum depth of the tree is determined by the substraction of the kinds-of-coin denomination to the total amount. Specifically the deepest branch will be the one that contains the greatest number of uses of the lowest demonination coin. Worst case scenario, the one that produces the deepest branch, will be when the change is comprised fully of the lowest demonination coin. The number of levels for this worst case branch will be equal to the ratio between the amount and the lowest denomination coin (11 / 1 for this problem) plus the number of other types of coins available (5 in this problem). The worst case scenario depth for (cc amount koc) will be equal to: depth = amount/koc(lowest) + koc - 1 so the space complexity is linear with respect to ‘amount’.
- Time complexity:
The sine of an angle (specified in radians) can be computed by making use of the approximation sin(x) ~= x if x is sufficiently small, and the trigonometric identity
sin(r) = 3 * sin(r/3) - 4 * (sin(r/3))^3
(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0)))))
(sine 0.1)a. How many times is the procedure p applied when (sine 12.15) is evaluated? (sine 12.15) (p (sine (4.05))) (p (p (sine (1.35)))) (p (p (p (sine (0.45))))) (p (p (p (p (sine (0.15)))))) (p (p (p (p (p (sine (0.05))))))) (p (p (p (p (p 0.05)))))
As we can see the procedure p is applied 5 times.
b. What is the order of growth in space and number of steps (as a function of a) used by the process generated by the sine procedure when (sine a) is evaluated?
The number of calls will be determined by the numbers of powers of 3 contained within number ‘a’ when we use 0.1 as our unit of measure.
number_of_calls = log_3(a/0.1) = log_3(12.15/0.1) = log_3(121.5) = 4.36907....
because we cannot make 0.36907… of a call that means we need to round up to the neares whole number in this case 5.
As we can see in the expansion the depth of the stack (or the number of deferred operations) that we need to keep track of is equal to the number of times the p procedure is called, so the process generated by the sine function has logarithmic growth both in time and space.
Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt. ; b^n = b^n/2*b^n/2
; b^n = b^((n/2)2)
; b^n = (b^2)^n/2
; b = base
; n = power
; a = result
(define (even? n) (= (remainder n 2) 0))
(define (square n) (* n n))
(define (power_iter b n a)
(cond ((= n 0) a)
((even? n) (power_iter (square b) (/ n 2) a))
(else (power_iter b (- n 1) (* a b))))
)
(define (power b n)
(power_iter b n 1))
(power 3 3) (define (even? n) (= (remainder n 2) 0))
(define (double n) (* n 2))
(define (halve n) (/ n 2))
(define (multiply a b)
(cond ((or (= a 0) (= b 0)) 0)
((= b 1) (+ a))
((even? b) (double (multiply a (/ b 2))))
(else (+ a (multiply a (- b 1))))))
(multiply 2 3) ; a * b = sum(a) b times
; a * b = sum(2 * a) (b/2) times if even
; a * b = sum(2 * a) ((b - 1)/2) + a times if odd
;a b c
;2 2 0
;4 1 0
;a b c
;7 3 0
;7 2 7
;14 1 7
(define (even? n) (= (remainder n 2) 0))
(define (double n) (* n 2))
(define (halve n) (/ n 2))
(define (multiply_iter a b c)
(cond ((or (= a 0) (= b 0)) 0)
((= b 1) (+ a c))
((even? b) (multiply_iter (double a) (halve b) c))
(else (multiply_iter a (- b 1) (+ c a))))
)
(define (multiply a b)
(multiply_iter a b 0))
(multiply 9 10) (define (fib n)
(fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-iter a
b
<??> ; compute p'
<??> ; compute q'
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1))))) (define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))Supposing normal-order evaluation:
(gcd 206 40) if (= 40 0)… (gcb 40 (remainder 206 40)) if (= (remainder 206 40))… (gcb (remainder 206 40) (remained 40 (remainder 206 40))) …
(define (divides? a b)
(= (remainder b a) 0))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (smallest-divisor n)
(find-divisor n 2))
(smallest-divisor 199)NOTE: Run this code within the guile. For some reason it doesn’t output the result when running it from org-mode.
(smallest-divisor 199) = 199 (smallest-divisor 199) = 1999 (smallest-divisor 199) = 7
(define (square x)
(display "square:")
(display x)
(newline)
(* x x)
)
(define (even? x) (if (= 0 (remainder x 2)) #t #f))
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
(define (expmod base exp m)
(display "base:")
(display base)
(display " ")
(display "exp:")
(display exp)
(display " ")
(display "m:")
(display m)
(newline)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
(define (expmod2 base exp m)
(display "base:")
(display base)
(display " ")
(display "exp:")
(display exp)
(display " ")
(display "m:")
(display m)
(newline)
(remainder (fast-expt base exp) m))
(expmod 5 101 101)
(display "---------")
(newline)
(expmod2 5 101 101)
As we can see by the printed output the original expmod function contains a modulo(remainder) operation within it that makes sure that the numbers being squared do not become higher than the number m being tested. On the other hand the second expmod implementation squares numbers that can be very long due to it only applying the modulo(remainder) operation once at the end and arithmetic with arbitrarily long numbers is expensive.
Original
(define (square x)
(display "square:")
(display x)
(newline)
(* x x)
)
(define (even? x) (if (= 0 (remainder x 2)) #t #f))
(define (expmod base exp m)
(display "base:")
(display base)
(display " ")
(display "exp:")
(display exp)
(display " ")
(display "m:")
(display m)
(newline)
(display "-----")
(newline)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
(expmod 2 4 3)
Modified
(define (square x)
(display "square:")
(display x)
(newline)
(* x x)
)
(define (even? x) (if (= 0 (remainder x 2)) #t #f))
(define (expmod base exp m)
(display "base:")
(display base)
(display " ")
(display "exp:")
(display exp)
(display " ")
(display "m:")
(display m)
(newline)
(display "-----")
(newline)
(cond ((= exp 0) 1)
((even? exp)
(remainder (* (expmod base (/ exp 2) m)
(expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
(expmod 2 4 3)
As you can see by running both and looking at the printed output, the procedure that uses the product directly creates a recursive tree process that results in a lot of redundant computations.
; Identity
(define (identity x) x)
; Increment
(define (inc x) (+ x 1))
; Sum (Recursive Process)
(define (sum_r a b term next)
(if (> a b) 0
(+ (term a) (sum_r (next a) b term next))))
; Sum (Iterative Process)
(define (sum_i a b term next acc)
(if (> a b) acc
(sum_i (next a) b term next (+ (term a) acc))))
(define (sum a b term next) (sum_i a b term next 0))
; Even
(define (even? num) (if (= (remainder num 2) 0) #t #f))
; Simpson's Rule Integral
(define (simp_rule_integral f a b n)
(define h (/ (- b a) n))
(define (y_k k) (f (+ a (* k h))))
(define (new_term k)
(cond ((or (= k 0) (= k n)) (y_k k))
((even? k) (* 2 (y_k k)))
(else (* 4 (y_k k)))
) )
(* (/ h 3) (sum 0 n new_term inc))
)
; Test by integrating the cube function from 0 to 1
(define (cube x) (* x x x))
(simp_rule_integral cube 0 1 10) ; Identity
(define (identity x) x)
; Increment
(define (inc x) (+ x 1))
; Iterative Solution
(define (sum term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ (term a) result))))
(iter a 0))
(sum identity 0 inc 10) ; Identity
(define (identity x) x)
; Increment
(define (inc x) (+ x 1))
; Iterative Solution
(define (product a b term next)
(define (iter a result)
(if (> a b)
result
(iter (next a) (* (term a) result))))
(iter a 1))
; Recursive Solution
(define (product_r a b term next)
(if (> a b) 1
(* (term a) (product_r (next a) b term next))))
(product_r 1 5 identity inc) ; Identity
(define (identity x) x)
; Increment
(define (inc x) (+ x 1))
; Recursive Solution
(define (acc_r a b base combiner term next)
(if (> a b) base
(combiner (term a) (acc_r (next a) b base combiner term next))))
; Iterative Solution
(define (acc a b base combiner term next)
(define (iter a result)
(if (> a b)
result
(iter (next a) (combiner (term a) result))))
(iter a base))
(define (sum a b term next) (acc a b 0 + term next))
(define (sum_r a b term next) (acc_r a b 0 + term next))
(define (product a b term next) (acc a b 1 * term next))
(define (product_r a b term next) (acc_r a b 1 * term next))
(display "sum1_10i: ")(display (sum 1 10 identity inc))(newline)
(display "sum1_10r: ")(display (sum_r 1 10 identity inc))(newline)
(display "product1_5i: ")(display (product 1 5 identity inc))(newline)
(display "product1_5r: ")(display (product_r 1 5 identity inc))(newline) ; Identity
(define (identity x) x)
; Increment
(define (inc x) (+ x 1))
; Iterative Solution
(define (acc_filtered a b base combiner filter term next)
(define (iter a result)
(if (> a b)
result
(iter (next a)
(if (filter a)
(combiner (term a) result)
result))))
(iter a base))
; Square
(define (square x) (* x x))
; Even?
(define (even? num) (if (= (remainder num 2) 0) #t #f))
; Prime?
(define (smallest-div n)
(define (divides? a b)
(= 0 (remainder b a)))
(define (find-div n test)
(cond ((> (square test) n) n) ((divides? test n) test)
(else (find-div n (+ test 1)))))
(find-div n 2))
(define (prime? n)
(if (= n 1) false (= n (smallest-div n))))
; GCD1?
(define (gcd m n)
(cond ((< m n) (gcd n m))
((= n 0) m)
(else (gcd n (remainder m n)))))
(define (relative-prime? m n)
(= (gcd m n) 1))
(define (product_of_relative_primes n)
(define (filter x)
(relative-prime? x n))
(acc_filtered 1 n 1 * filter identity inc))
(define (sum_f a b filter term next) (acc_filtered a b 0 + filter term next))
(define (product_f a b filter term next) (acc_filtered a b 1 * filter term next))
(display "sum_of_primes_between_1_10: ")(display (sum_f 1 10 prime? identity inc))(newline)
(display "product_of_relative_primes_1_10: ")(display (product_of_relative_primes 10))(newline)
(define (f g) (g 2))
(define (square x) (* x x))
(f square)
(f (lambda (z) (* z (+ z 1))))
(f f)An error gets thrown. When we try to evaluate (f f) we end up trying to apply 2 to the number 2: (f f) ((g 2) 2) (2 2) ERROR: application: not a procedure;
(define (average x y) (/ (+ x y) 2))
(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0) (define (average x y) (/ (+ x y) 2))
(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(display guess)(newline)
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
(fixed-point (lambda (x) (/ (log 1000) (log x))) 3.0) ; N1/(D1 + (N2/(D2 + (Nk/DK))))
; Recursive Solution
(define (cont-frac_r n d k)
(define (cont-frac-step n d k i)
(if (> i k)
0
(/ (n i) (+ (d i) (cont-frac-step n d k (+ i 1))))))
(cont-frac-step n d k 1))
; Iterative Solution
(define (cont-frac n d k)
(define (cont-frac-iter i acc)
(if (= 0 i)
acc
(cont-frac-iter (- i 1) (/ (n i) (+ (d i) acc)))))
(cont-frac-iter k 0))
(display "cont-frac_1_over_phi_recursive: ")
(display (cont-frac_r (lambda (i) 1.0) (lambda (i) 1.0) 100))
(newline)
(display "cont-frac_1_over_phi_iterative: ")
(display (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 100))
(newline)
(display (/ 1 1.6180327868852458))
(define (cont-frac n d k)
(define (cont-frac-iter i acc)
(if (= 0 i)
acc
(cont-frac-iter (- i 1) (/ (n i) (+ (d i) acc)))))
(cont-frac-iter k 0))
(display "e ~= ")
(display (+ 2
(exact->inexact (cont-frac (lambda (i) 1)
(lambda (i)
(let ((m3 (remainder i 3)))
(cond ((or (= i 1) (= i 2)) i)
((or (= m3 0) (= m3 1)) 1)
(else (+ (* (/ (- i 5) 3) 2) 4)))))
100)))) (define (cont-frac n d k)
(define (cont-frac-iter i acc)
(if (= 0 i)
acc
(cont-frac-iter (- i 1) (/ (n i) (+ (d i) acc)))))
(cont-frac-iter k 0))
(define (tan-cf x k)
(cont-frac (lambda (i) (if (= i 1) x (- (* x x))))
(lambda (i) (- (* i 2) 1))
k))
(display "tan-cf(pi/4) ~= ")
(display (tan-cf (/ 3.1416 4) 1000))
(newline)
(display "tan(pi/4) = 1") ; Cubic function
; x^3 + ax^2 + bx + c
(define (cubic a b c)
(lambda (x)
(+ (* x x x)
(* a x x)
(* b x)
c))) (define (double f)
(lambda (x) (f(f x))))
(define (inc x) (+ x 1))
(define (square x) (* x x))
(display "inc(inc(0)) = ")
(display ((double inc) 0))
(newline)
(display "square(square(2)) = ")
(display ((double square) 2))
(newline)
(display "(((double (double double)) inc) 5) = ")
(display (((double (double double)) inc) 5)) (define (inc x) (+ x 1))
(define (square x) (* x x))
(define (compose f g)
(lambda (x) (f (g x))))
(display "((compose square inc) 6) = ")
(display ((compose square inc) 6)) (define (square x) (* x x))
(define (compose f g)
(lambda (x) (f (g x))))
(define (repeated f n)
(if (<= n 1) f (repeated (compose f f) (- n 1))))
(display "((repeated square 2) 5) = ")
(display ((repeated square 2) 5)) (define (compose f g)
(lambda (x) (f (g x))))
(define (repeated f n)
(if (<= n 1) f (repeated (compose f f) (- n 1))))
; smooth = f(x - dx) + f(x) + f(x + dx)
; n-fold smoothed function
(define dx 0.00001)
(define (smooth f)
(lambda (x) (/ (+ (f x) (f (+ x dx)) (f (- x dx)) 3))))
(define (smooth_n f n)
((repeated smooth n) f )) ; Average-dampening
(define (average a b) (/ (+ a b) 2))
(define (average-damp f)
(lambda (x) (average x (f x))))
; Derivative
(define dx 0.00001)
(define (deriv g)
(lambda (x)
(/ (- (g (+ x dx)) (g x))
dx)))
; Fixed-point
(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
; Newtons-method
(define (newton-transform g)
(lambda (x)
(- x (/ (g x) ((deriv g) x)))))
(define (newtons-method g guess)
(fixed-point (newton-transform g) guess)) (define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
(define (numer x) (car x))
(define (denom x) (cdr x))
(define (print-rat x)
(newline)
(display (numer x))
(display "/")
(display (denom x)))
(define (make-rat-base n d)
(let ((g (gcd n d)))
(cons (/ n g) (/ d g))))
(define (make-rat n d)
(if (< d 0) (make-rat-base (- n) (- d)) (make-rat-base n d)))
(print-rat (make-rat 4 -8)) (define (print-point p)
(newline)
(display "(")
(display (x-point p))
(display ",")
(display (y-point p))
(display ")"))
(define (make-point x y)
(cons x y))
(define (x-point point)
(car point))
(define (y-point point)
(cdr point))
(define (make-segment start-point end-point)
(cons start-point end-point))
(define (start-point segment)
(car segment))
(define (end-point segment)
(cdr segment))
(define (mid-point-segment segment)
(let ((x-avg (/ (+ (x-point (start-point segment)) (x-point (end-point segment))) 2))
(y-avg (/ (+ (y-point (start-point segment)) (y-point (end-point segment))) 2)))
(make-point x-avg y-avg)))
(print-point (mid-point-segment (make-segment (make-point 1 0) (make-point 0 1)))) ; Utility Functions
(define (print-point p)
(display "(")
(display (x-point p))
(display ",")
(display (y-point p))
(display ")"))
(define (make-point x y)
(cons x y))
(define (x-point point)
(car point))
(define (y-point point)
(cdr point))
(define (make-segment start-point end-point)
(cons start-point end-point))
(define (start-point segment)
(car segment))
(define (end-point segment)
(cdr segment))
(define (mid-point-segment segment)
(let ((x-avg (/ (+ (x-point (start-point segment)) (x-point (end-point segment))) 2))
(y-avg (/ (+ (y-point (start-point segment)) (y-point (end-point segment))) 2)))
(make-point x-avg y-avg)))
(define (average x y)
(/ (+ x y) 2))
(define (square x) (* x x))
(define (improve guess x)
(average guess (/ x guess)))
(define (good-enough? guess x)
(> 0.00001 (abs (- (improve guess x) guess))))
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
(define (sqrt x)
(sqrt-iter 1 x))
(define (length a b)
(let ((xp (abs (- (x-point a) (x-point b))))
(yp (abs (- (y-point a) (y-point b)))))
(sqrt (+ (square xp) (square yp)))))
; --- New code ---
(define (make-rectangle tl tr bl br)
(cons (cons tl tr) (cons bl br)))
(define (top-points rectangle) (car rectangle))
(define (top-left-point rectangle)
(car (top-points rectangle)))
(define (top-right-point rectangle)
(cdr (top-points rectangle)))
(define (bottom-points rectangle) (cdr rectangle))
(define (bottom-left-point rectangle)
(car (bottom-points rectangle)))
(define (bottom-right-point rectangle)
(cdr (bottom-points rectangle)))
(define (perimeter rectangle)
(+ (length (top-left-point rectangle) (top-right-point rectangle))
(length (top-right-point rectangle) (bottom-right-point rectangle))
(length (bottom-right-point rectangle) (bottom-left-point rectangle))
(length (bottom-left-point rectangle) (top-left-point rectangle))))
(define (area rectangle)
(* (length (top-left-point rectangle) (top-right-point rectangle))
(length (bottom-left-point rectangle) (bottom-right-point rectangle))))
; --- Test ---
(define (print-rectangle rectangle)
(print-point (top-left-point rectangle))
(display "------")
(print-point (top-right-point rectangle))
(newline)
(display "| |")
(newline)
(print-point (bottom-left-point rectangle))
(display "------")
(print-point (bottom-right-point rectangle))
(newline)
(newline)
(display "perimeter: ")(display (exact->inexact (perimeter rectangle)))
(newline)
(display "area: ")(display (exact->inexact (area rectangle))))
(define p1 (make-point 0 2))
(define p2 (make-point 2 2))
(define p3 (make-point 0 0))
(define p4 (make-point 2 0))
(define rectangle1 (make-rectangle p1 p2 p3 p4))
(print-rectangle rectangle1)
(define (cons x y)
(lambda (m) (m x y)))
(define (car z)
(z (lambda (p q) p)))
(define (cdr z)
(z (lambda (p q) q)))
(define p (cons 1 2))
(display "p(x) = 1 = ")
(display (car p))
(newline)
(display "p(y) = 2 = ")
(display (cdr p)) The cons function returns a lamda that takes in as its only argument a function that gets accepts the values of x and y in that order. Now the car and cdr function simply receive both x and y and immediately return the appropriate one.
(define (exp base n)
(define (exp_iter base n acc)
(if (= n 0) acc (exp_iter base (- n 1) (* acc base))))
(exp_iter base n 1))
(define (count-powers num base)
(define (count-powers-iter num base count)
(define temp (/ num base))
(if (= (floor temp) temp)
(count-powers-iter temp base (+ count 1))
count))
(count-powers-iter num base 0))
(define (cons a b)
(* (exp 2 a) (exp 3 b)))
(define (car p)
(count-powers p 2))
(define (cdr p)
(count-powers p 3))
(display "pair = (5 3)")
(newline)
(define pair (cons 5 3))
(display "pair(x) = ") (display (car pair))
(newline)
(display "pair(y) = ") (display (cdr pair))
(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))
; define one
(define one (lambda (f) (lambda (x) (f x))))
; define two
(define two (lambda (f) (lambda (x) (f (f x)))))
; define +
(define (add a b)
(lambda (f)
(lambda (x)
((a f) ((b f) x)))))
(define (to_decimal f)
((f (lambda (x) (+ 1 x))) 0))
(display "church_numeral 0 =")(display (to_decimal zero)) (newline)
(display "church_numeral 1 =")(display (to_decimal one)) (newline)
(display "church_numeral 2 =")(display (to_decimal two)) (newline) ; Interval Arithmetic Operations
(define (add-interval x y)
(make-interval (+ (lower-bound x) (lower-bound y))
(+ (upper-bound x) (upper-bound y))))
(define (mul-interval x y)
(let ((p1 (* (lower-bound x) (lower-bound y)))
(p2 (* (lower-bound x) (upper-bound y)))
(p3 (* (upper-bound x) (lower-bound y)))
(p4 (* (upper-bound x) (upper-bound y))))
(make-interval (min p1 p2 p3 p4)
(max p1 p2 p3 p4))))
(define (div-interval x y)
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y)))))
; Constructor
(define (make-interval a b) (cons a b))
; Selectors
(define (upper-bound interval) (max (car interval) (cdr interval)))
(define (lower-bound interval) (min (car interval) (cdr interval)))
(define i_v1 (make-interval 1 5))
(define i_v2 (make-interval 5 1))
(display "i_v1 upper-bound = ")(display (upper-bound i_v1))(newline)
(display "i_v2 upper-bound = ")(display (upper-bound i_v2))(newline)
(display "i_v1 lower-bound = ")(display (lower-bound i_v1))(newline)
(display "i_v2 lower-bound = ")(display (lower-bound i_v2))(newline) ; Interval Arithmetic Operations
(define (add-interval x y)
(make-interval (+ (lower-bound x) (lower-bound y))
(+ (upper-bound x) (upper-bound y))))
(define (mul-interval x y)
(let ((p1 (* (lower-bound x) (lower-bound y)))
(p2 (* (lower-bound x) (upper-bound y)))
(p3 (* (upper-bound x) (lower-bound y)))
(p4 (* (upper-bound x) (upper-bound y))))
(make-interval (min p1 p2 p3 p4)
(max p1 p2 p3 p4))))
(define (div-interval x y)
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y)))))
; Constructor
(define (make-interval a b) (cons a b))
; Selectors
(define (upper-bound interval) (max (car interval) (cdr interval)))
(define (lower-bound interval) (min (car interval) (cdr interval)))
(define i_v1 (make-interval 1 5))
(define i_v2 (make-interval 5 1))
; Substraction
(define (sub-interval i1 i2)
(add-interval i1
(make-interval (- (upper-bound i2))
(- (lower-bound i2)))))
(define sub_interval (sub-interval i_v1 i_v2))
(display "upper-bound i_v1 - i_v2 = ")(display (upper-bound sub_interval))(newline)
(display "lower-bound i_v1 - i_v2 = ")(display (lower-bound sub_interval))(newline) ; Interval Arithmetic Operations
(define (add-interval x y)
(make-interval (+ (lower-bound x) (lower-bound y))
(+ (upper-bound x) (upper-bound y))))
(define (mul-interval x y)
(let ((p1 (* (lower-bound x) (lower-bound y)))
(p2 (* (lower-bound x) (upper-bound y)))
(p3 (* (upper-bound x) (lower-bound y)))
(p4 (* (upper-bound x) (upper-bound y))))
(make-interval (min p1 p2 p3 p4)
(max p1 p2 p3 p4))))
(define (div-interval x y)
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y)))))
; Constructor
(define (make-interval a b) (cons a b))
; Selectors
(define (upper-bound interval) (max (car interval) (cdr interval)))
(define (lower-bound interval) (min (car interval) (cdr interval)))
; Substraction
(define (sub-interval i1 i2)
(add-interval i1
(make-interval (- (upper-bound i2))
(- (lower-bound i2)))))
; Display
(define (display_width interval)
(display (/ (- (upper-bound interval)
(lower-bound interval)) 2)))
(define (display_interval interval)
(display "[")
(display (lower-bound interval))
(display ", ")
(display (upper-bound interval))(display "]"))
; Show differnce of sum or difference is a function only of the width of the intervals
; Show that is not the case for multiplication and division
(define i_v1 (make-interval 1 5))
(define i_v2 (make-interval 5 1))
(define i_v3 (make-interval 4 8))
(define i_v4 (make-interval -6 -2))
(define sum_interval_1 (add-interval i_v1 i_v2))
(define diff_interval_1 (sub-interval i_v1 i_v2))
(define mul_interval_1 (mul-interval i_v1 i_v2))
(define div_interval_1 (div-interval i_v1 i_v2))
(define sum_interval_2 (add-interval i_v3 i_v4))
(define diff_interval_2 (sub-interval i_v3 i_v4))
(define mul_interval_2 (mul-interval i_v3 i_v4))
(define div_interval_2 (div-interval i_v3 i_v4))
(display "sum1_width = ")(display_width sum_interval_1)(newline)
(display "sum2_width = ")(display_width sum_interval_2)(newline)
(display "diff1_width = ")(display_width diff_interval_1)(newline)
(display "diff2_width = ")(display_width diff_interval_2)(newline)
(display "mul1_width = ")(display_width mul_interval_1)(newline)
(display "mul2_width = ")(display_width mul_interval_2)(newline)
(display "div1_width = ")(display_width div_interval_1)(newline)
(display "div2_width = ")(display_width div_interval_2)(newline)We used two pairs of intervals with equal widths to test the claim and as we can see the resulting values for the sum and difference for these intervals is the same while the result for the multiplation and divition is not.
; Interval Arithmetic Operations
(define (add-interval x y)
(make-interval (+ (lower-bound x) (lower-bound y))
(+ (upper-bound x) (upper-bound y))))
(define (mul-interval x y)
(let ((p1 (* (lower-bound x) (lower-bound y)))
(p2 (* (lower-bound x) (upper-bound y)))
(p3 (* (upper-bound x) (lower-bound y)))
(p4 (* (upper-bound x) (upper-bound y))))
(make-interval (min p1 p2 p3 p4)
(max p1 p2 p3 p4))))
(define (div-interval x y)
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y)))))
; Constructor
(define (make-interval a b) (cons a b))
; Selectors
(define (upper-bound interval) (max (car interval) (cdr interval)))
(define (lower-bound interval) (min (car interval) (cdr interval)))
; Substraction
(define (sub-interval i1 i2)
(add-interval i1
(make-interval (- (upper-bound i2))
(- (lower-bound i2)))))
; Width
(define (width-interval interval)
(/ (- (upper-bound interval)
(lower-bound interval)) 2))
(define (div-interval-safe x y)
(if (>= 0 (* (upper-bound y) (lower-bound y)))
(error "Division by an interval that spans zero is meaningless.")
(div-interval x y)))
(define i_v1 (make-interval 1 5))
(define i_v2 (make-interval -2 1))
(display (div-interval-safe i_v1 i_v1))(newline)
(display (div-interval-safe i_v1 i_v2))(newline) ; Interval Arithmetic Operations
(define (add-interval x y)
(make-interval (+ (lower-bound x) (lower-bound y))
(+ (upper-bound x) (upper-bound y))))
(define (mul-interval x y)
(let ((p1 (* (lower-bound x) (lower-bound y)))
(p2 (* (lower-bound x) (upper-bound y)))
(p3 (* (upper-bound x) (lower-bound y)))
(p4 (* (upper-bound x) (upper-bound y))))
(make-interval (min p1 p2 p3 p4)
(max p1 p2 p3 p4))))
(define (div-interval-inner x y)
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y)))))
(define (div-interval x y)
(if (>= 0 (* (upper-bound y) (lower-bound y)))
(error "Division by an interval that spans zero is meaningless.")
(div-interval-inner x y)))
; Constructor
(define (make-interval a b) (cons a b))
; Selectors
(define (upper-bound interval) (max (car interval) (cdr interval)))
(define (lower-bound interval) (min (car interval) (cdr interval)))
; Substraction
(define (sub-interval i1 i2)
(add-interval i1
(make-interval (- (upper-bound i2))
(- (lower-bound i2)))))
; Width
(define (width-interval interval)
(/ (- (upper-bound interval)
(lower-bound interval)) 2))
; Multiplication implementation that tests for signs of endpoints
(define (mul-interval x y)
(let ((p1 (* (lower-bound x) (lower-bound y)))
(p2 (* (lower-bound x) (upper-bound y)))
(p3 (* (upper-bound x) (lower-bound y)))
(p4 (* (upper-bound x) (upper-bound y))))
(make-interval (min p1 p2 p3 p4)
(max p1 p2 p3 p4))))
(define (last-pair element)
(if (null? (cdr element))
element
(last-pair (cdr element))))
(display "last pair is: ")(display (last-pair (list 23 72 149 34))) (define (reverse l)
(define (reverse-iter lst r-l)
(let ((a (car lst))
(b (cdr lst)))
(if (null? b) (cons a r-l) (reverse-iter b (cons a r-l)))))
(reverse-iter l null))
(display "list= ")(display (list 1 4 9 16 25))(newline)
(display "reverse list= ")(display (reverse (list 1 4 9 16 25))) ; Utility Procedures
(define (first-denomination l)
(car l))
(define (except-first-denomination l)
(cdr l))
(define (no-more? l) (null? l))
; Count Change
(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)))))
; Test
(define us-coins (list 50 25 10 5 1))
(define us-coins-reversed (list 1 5 10 25 50))
(display "cc 100 using us-coins = 292 = ")(display (cc 100 us-coins))(newline)
(display "cc 100 using us-coins-reversed = 292 = ")(display (cc 100 us-coins))Changing the order of the coins will only chage where in the call-tree the procedures for specific amount/coins combination get called. The result of of cc is the sum of the result of all these procedure calls so changing where they happen in the tree doesn’t do anything to change the result.
; I added the leading and trailing '*' to prevent babel
; from interpreting the result as a list.
(define (display-list l)
(define (display-elements-iter l)
(define (display-element ele last)
(display ele)
(if last (display "") (display ", ")))
(if (not(null? l))
((lambda (a b)
(display-element a (null? b))
(display-elements-iter b)) (car l) (cdr l))
null))
(display "*(")
(display-elements-iter l)
(display ")*"))
(define (even? a) (= 0 (remainder a 2)))
(define (odd? a) (not(even? a)))
(define (filter2 sl predicate)
(if (null? sl)
null
(if (predicate (car sl))
(cons (car sl) (filter2 (cdr sl) predicate))
(filter2 (cdr sl) predicate))))
(define (same-parity . l)
(if (even? (car l)) (filter2 l even?) (filter2 l odd?)))
(display "(1 3 5 7) = ")(display-list (same-parity 1 2 3 4 5 6 7))(newline)
(display "(2 4 6) = ") (display-list (same-parity 2 3 4 5 6 7)) (define (map proc items)
(if (null? items)
nul
(cons (proc (car items))
(map proc (cdr items)))))
(define (square-list items)
(if (null? items)
null
(cons (* (car items) (car items)) (square-list (cdr items)))))
(define (square-list2 items)
(map (lambda (x) (* x x)) items))
(display "(1 4 9 16) = ")(display (square-list (list 1 2 3 4)))(newline)
(display "(1 4 9 16) = ")(display (square-list2 (list 1 2 3 4)))(newline) (define (square-list items)
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(cons answer
(* (car things) (car things))))))
(iter items null))
(display (square-list (list 1 2 3)))Using the cons procedure to create a list involves creating a pair composed of en element and another pair. The square list procedure is essentially taking elements from the start of the things list and putting them in a second list called answer by combining through the use of cons whatever was in answer together with a new start element and this process of starting with an empty list and adding elements at the start of the list essentially fills the list in reverse order. Changing the order of the arguments doesn’t work because it doesn’t make sense. This results in a pair whose first element is a pair and the second one is a value essentially resulting in this: (((nil 1) 4) 9)
(define (for-each proc items)
(proc (car items))
(for-each proc (cdr items)))
(for-each (lambda (x) (display x)(newline)) (list 1 2 3)) (define (nth i l)
(if (= i 0)
(if (pair? l) (car l) l)
(nth (- i 1) (cdr l))))
(define list_l (list 1 (list 2 (list 3 4))))
(define list_c (cons 1 (cons 2 (cons 3 (cons 4 null)))))
(display "list: ")(display list_l)(newline)
(display "list[0]: ")(display (nth 0 list_l))(newline)
(display "list[1]: ")(display (nth 1 list_l))(newline)
(display "list[2]: ")(display (nth 2 list_l))(newline)
(newline)
(display "--------")(newline)
(newline)
(display "cons: ")(display list_c)(newline)
(display "cons[0]: ")(display (nth 0 list_c))(newline)
(display "cons[1]: ")(display (nth 1 list_c))(newline)
(display "cons[2]: ")(display (nth 2 list_c))(newline)
(display "cons[3]: ")(display (nth 3 list_c))(newline)
(display "cons[4]: ")(display (nth 4 list_c))(newline) (define l1 (list 1 3 (list 5 7) 9))
(define l2 (list (list 7)))
(define l3 (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))
(define (go-in l d)
(if (= d 0) l (go-in (car (cdr l)) (- d 1))))
(display "l1: ")(display (car (cdr (car (cdr (cdr l1))))))(newline)
(display "l2: ")(display (car (car l2)))(newline)
(display "l3: ")(display (go-in l3 6))(newline)(define x (list 1 2 3))
(define y (list 4 5 6))
(display "(append x y) = (1 2 3 4 5 6) = ")(display (append x y))(newline)
(display "(cons x y) = ((1 2 3) 4 5 6) = ")(display (cons x y))(newline)
(display "(list x y) = ((1 2 3) (4 5 6)) = ")(display (list x y))(newline) (define (reverse l)
(define (reverse-iter lst r-l)
(let ((a (car lst))
(b (cdr lst)))
(if (null? b) (cons a r-l) (reverse-iter b (cons a r-l)))))
(reverse-iter l null))
(define x (list (list 1 2) (list 3 4)))
(define (reverse-if-list l)
(if (pair? l) (reverse l) l))
(define (map proc items)
(if (pair? items)
(if (null? items)
null
(cons (proc (car items))
(map proc (cdr items))))
items))
(define (deep-reverse l)
(map (lambda (x) (deep-reverse x)) (reverse-if-list l)))
(display "x = ((1 2) (3 4)) = ")(display x)(newline)
(display "(reverse x) = ((3 4) (1 2)) = ")(display (reverse x))(newline)
(display "(deep-reverse x) = ((4 3) (2 1)) = ")(display (deep-reverse x)) (define x (list (list 1 2) (list 3 4)))
(define (fringe l)
(if (pair? l)
(append (fringe (car l)) (fringe (cdr l)))
(if (null? l)
l
(cons l null))))
(display "x = ((1 2) (3 4)) = ")(display x)(newline)
(display "(fringe x) = (1 2 3 4) = ")(display (fringe x))(newline)
(display "(fringe (x x)) = (1 2 3 4 1 2 3 4) = ")(display (fringe (list x x))) (define (nth i l)
(if (= i 0)
(if (pair? l) (car l) l)
(nth (- i 1) (cdr l))))
(define (make-mobile left right)
(list left right))
(define (make-branch length structure)
(list length structure))
(define (left-branch bm) (nth 0 bm))
(define (right-branch bm) (nth 1 bm))
(define (branch-length b) (nth 0 b))
(define (branch-structure b) (nth 1 b))
(define (total-weight bm)
(let ((tw-or-w (lambda (x) (if (pair? x)
(total-weight x)
x))))
(+ (tw-or-w (branch-structure (left-branch bm))) (tw-or-w (branch-structure (right-branch bm))))))
(define (balanced? bm)
(define (is-weight? x) (not (pair? x)))
(define (get-structure-weight s)
(if (is-weight? s)
s
(+ (get-structure-weight (branch-structure (left-branch s)))
(get-structure-weight (branch-structure (right-branch s))))))
(define (get-torque b) (* (branch-length b) (get-structure-weight (branch-structure b))))
(define (balanced-or-true s) (if (is-weight? s) #t (balanced? s)))
(define torque-l (get-torque (left-branch bm)))
(define torque-r (get-torque (right-branch bm)))
(and (balanced-or-true (branch-structure (left-branch bm)))
(balanced-or-true (branch-structure (right-branch bm)))
(= torque-l torque-r)))
; TESTS
(define mobile1 (make-mobile (make-branch 1 (make-mobile (make-branch 4 5)
(make-branch 1 1)))
(make-branch 2 3)))
(define mobile2 (make-mobile (make-branch 2 (make-mobile (make-branch 4 5)
(make-branch 5 4)))
(make-branch 3 6)))
(display "TEST_MOBILES:")(newline)
(display "mobile1 = (1,(4,5)<-->(1,1))<-X->(2,3)")(newline)
(display "mobile2 = (2,(4,5)<-->(5,4))<-X->(3,6)")(newline)
(display "-------------")(newline)
(display "mobile1-total-weight = 9 = ")
(display (total-weight mobile1))(newline)
(display "mobile2-total-weight = 15 = ")
(display (total-weight mobile2))(newline)
(display "-------------")(newline)
(display "mobile1-balanced = false = ")
(display (balanced? mobile1))(newline)
(display "mobile2-balanced = true = ")
(display (balanced? mobile2))(newline)
; How much do you need to change your programs to convert to the new representation?
; RE: I would only need to change the getter methods defined at the start for accessing branches, structure and length
; given that all the functions written are making use of them as an interface their implementation does not matter as
; long as the expected behaviour i.e. what they return, remains the same. (define (subsets s)
(if (null? s)
(list null)
(let ((rest (subsets (cdr s))))
(append rest (map (lambda (r) (cons (car s) r)) rest)))))
(define s (list 1 2 3))
(display "subset = ")(display s)(newline)
(display "powerset = ")(display (subsets s))I found this problem to be tricky but the subsets function essentially returns the union of:
- all subsets of the current set without the first element
- all subsets of the current set without the first element with the first elements added into all its subsets
Example: Given the set (1 2 3)
- The set of all subsets of (1 2 3) without the first element is: (() (2) (3) (2 3))
- The set of all subsets of (1 2 3) without the first element with the first element added back in is: ((1) (1 2) (1 3) (1 2 3))
- And the union of these two sets is: (() (1) (2) (3) (1 2) (2 3) (1 3) (1 2 3))
This definition is applied recursevily for calculating each smaller subset until we reach the empty set as a stop condition for our recursion. This would be the results for revery call: nil -> (()) 3 -> (()) | ((3)) = (() (3)) 2 -> (() (3)) | ((2) (2 3)) = (() (2) (3) (2 3)) 1 -> (() (2) (3) (2 3)) | ((1) (1 2) (1 3) (1 2 3)) = (() (1) (2) (3) (1 2) (2 3) (1 3) (1 2 3))
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (map p sequence)
(accumulate (lambda (x y) (cons (p x) y)) null sequence))
(define (append seq1 seq2)
(accumulate cons seq2 seq1))
(define (length sequence)
(accumulate (lambda (x y) (+ 1 y)) 0 sequence))
(display "map(x^2, (1,2,3,4)) = ") (display (map (lambda (x) (* x x)) (list 1 2 3 4)))(newline)
(display "append((1,2), (3,4,5)) = ")(display (append (list 1 2) (list 3 4 5)))(newline)
(display "length((3,4,5)) = ")(display (length (list 3 4 5)))(newline)