Exercise 1.34 Suppose we define the procedure
(define (f g) (g 2))Then we have
(f square) 4 (f (lambda (z) (* z (+ z 1)))) 6What happens if we (perversely) ask the interpreter to evaluate the combination (f f)? Explain.
Interpreter gets stuck in an infinite loop. It will keep trying to evaluate (f f) which involves evaluating (f (f f)) and then (f (f (f f))) &c.
exercise 1.9 Each of the following two procedures defines a method for adding two positive integers in terms of the procedures inc, which increments its argument by 1, and dec, which decrements its argument by 1.
(define (+ a b) (if (= a 0) b (inc (+ (dec a) b)))) (define (+ a b) (if (= a 0) b (+ (dec a) (inc b))))Using the substitution model, illustrate the process generated by each procedure in evaluating (+ 4 5). Are these processes iterative or recursive?
The first is iterative
(+ 4 5) (inc (+ (dec 4) 5)) (inc (+ 3 5)) (inc (inc (+ (dec 3) 5))) (inc (inc (+ 2 5))) (inc (inc (inc (+ (dec 2) 5)))) (inc (inc (inc (+ 1 5)))) (inc (inc (inc (inc (+ (dec 1) 5))))) (inc (inc (inc (inc (+ 0 5))))) (inc (inc (inc (inc 5)))) (inc (inc (inc 6))) (inc (inc 7)) (inc 8) 9The second is recursive
(+ 4 5) (+ (dec 4) (inc 5)) (+ 3 6) (+ (dec 3) (inc 6)) (+ 2 7) (+ (dec 2) (inc 7)) (+ 1 8) (+ (dec 1) (inc 8)) (+ 0 9) 9
exercise 1.10 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) (A 2 4) (A 3 3)
1 ]=> (A 1 10) ;Value: 1024 1 ]=> (A 2 4) ;Value: 65536 1 ]=> (A 3 3) ;Value: 65536
Consider the following procedures, where A is the procedure defined above:
(define (f n) (A 0 n)) (define (g n) (A 1 n)) (define (h n) (A 2 n)) (define (k n) (* 5 n n))
Give concise mathematical definitions for the functions computed by the procedures f, g, and h for positive integer values of n. For example, (k n) computes 5n2.
f(n) = 2n g(n) = 2n h(n) = (2n)n
exercise 1.6 To paraphrase, Alyssa wants to know why if needs to be provided as a special form; why can't it just be defined in terms of cond? Alyssa P. Hacker's amiga Eva Lu Ator says this can be done, and defines this:
(define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause)))Elated, Alyssa goes on to use new-if to rewrite the provided square–root program as
(define (sqrt-iter guess x) (new-if (good-enough? guess x) guess (sqrt-iter (improve guess x) x)))What happens when Alyssa uses this to compute square roots?
Because our compiler is using applicative–order evaluation, it's going to try to evaluate all the args—ie, guess and (sqrt-iter (improve guess x) x). The later is recursive, so the compiler will get stuck in an inifite loop :c
exercise 1.7 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.
1 ]=> (sqrt 0.001) ;Value: .04124542607499115 1 ]=> (sqrt 1e13) ^C Interrupt option (? for help): ;Quit!For smaller numbers the answer given is wrong. (sqrt 0.001) gives approximately 0.0413 when it is really close to 0.0316. This happens because we have allowed that a good-enough answer squared is one within 0.001 from from x, the number we're trying to find the square root of. The static number 0.001 is too large to give a precise enough answer.
For larger numbers the procedure never finishes (infinite loop). In the case of (sqrt 1e13), eventually improve spits out 3162277.6601683795. (good-enough? 3162277.664010480 1e13) evaluates, correctly, to false. But when we go to improve upon this result, because of the limit of precision in our calculations (the number of digits calculated is not sufficient) we get 3162277.6601683795 again. And again, and again.
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.
(define (good-enough? guess x) (< (abs (- (improve guess x) guess)) (* guess 0.00001)))
- (abs (- (improve guess x) guess)) = change from one iteration to the next
- (* guess 0.00001) = a very small fraction of the guess
Does this work better for small and large numbers?
1 ]=> (sqrt 0.001) ;Value: .03162278245070105 1 ]=> (sqrt 1e13) ;Value: 3162277.6640104805Yes it works much better now :]
exercise 1.8 Newton's method for cube roots is based on the fact that if y is an approximation to the cube root of x, then a better approximation is given by this
Use this formula to implement a cube-root procedure analogous to the square-root procedure.
The only procedures I needed to define that weren't provided in the book (if under different, but analagous, names) were cube and improve. Listing all the necessary procedures here for context.
(define (cbrt x) (cbrt-iter 1.0 x)) (define (cbrt-iter guess x) (if (good-enough? guess x) guess (cbrt-iter (improve guess x) x))) (define (good-enough? guess x) (< (abs (- (cube guess) x)) 0.001)) (define (cube x) (* x x x)) (define (improve guess x) (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))
So yesterday I hit the 50-problem mark on Project Euler. The problem was the one about how many ways can you make 200 GBP. SICP implemented this problem and I just happened to be reading it, so after I read the problem I went and implemented it in Haskell. While it ran in under a minute, I thought it was rather slow….Anyway that's totally not what this is about. Perhaps I'll make a post about this problem later.
In light of finishing 50 problems, I'm going to be taking a wee break (like, a week? less, quite possibly) and start doing the exercises from SICP. I've actually done nearly all the ones from chapter 2, but then it occurred to me to do something logical and start from chapter one…. So without furthur ado:
Exercise 1.1. Below is a sequence of expressions. What is the result printed by the interpreter in response to each expression? Assume that the sequence is to be evaluated in the order in which it is presented.
I'm only posting the more complex ones, or the ones I was not entirely sure about. All solutions are easily verifiable with an interpreter. Wrote some comments in, as well.
]=> (+ (* 2 4) (- 4 6)) ;; (+ 8 (-2))
6
]=> (define a 3)
a
]=> (define b (+ a 1))
b
]=> (+ a b (* a b))
;; (+ 3 4 (* 3 4)) -> (+ 3 4 12)
19
]=> (= a b)
#f
]=> (if (and (> b a) (< b (* a b)))
b
a)
4
]=> (cond ((= a 4) 6) ;; a is 3, this condition false
((= b 4) (+ 6 7 a)) ;; b is 4, this condition true
(else 25))
16
]=> (+ 2 (if (> b a) b a))
6 ;; (+ 2 b) -> (+ 2 4)
]=> (* (cond ((> a b) a) ;;false
((< a b) b) ;;true
(else -1))
(+ a 1))
;; (* b (+ a 1)) -> (*4 4)
16
Exercise 1.2. Translate the […] expression into prefix form.
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7)))Exercise 1.3. Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.
(define (sum-squares-largest a b c) (cond ((and (< a b) (< a c)) (+ (* b b) (* c c))) ;a is smaller than b & c so sum the squares of b & c ((and (< b c) (< b a)) (+ (* a a) (* c c))) (else (+ (* a a) (* b b)))))
Exercise 1.4. Observe that our model of evaluation allows for combinations whose operators are compound expressions. Use this observation to describe the behavior of the following procedure:
(define (a-plus-abs-b a b) ((if (> b 0) + -) a b))If b is a positive number we will add b to a. If b is a negative number, subtract b from a. This expression is essentially adding the absolute value of b to a.
Exercise 1.5. (Paraphrased!) Ben Bitdiddle (what is the clever pun in his name? I know there must be one, but I don't understand it…) is trying to test if his interpreter is using applicative–order evaluation or normal–order evaluation. He defines these expresions:
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
When he evaluates (test 0 (p)) what will be returned if the interpreter is applicative–order, and what will be returned if the interpreter is normal–order?
normal The interpreter will look to see if (= x 0), which is true, so it will return 0 and stop. applicative will never terminate. The interpreter will try to evaluate the arguments—it will "plug–in" 0 for x, and then try to do the same, plugging in p for y, but because p is recursively defined, the interpreter will be doing this plugging–in forever.
The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.
We shall consider fractions like, 30/50 = 3/5, to be trivial examples.
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.
If the product of these four fractions is given in its lowest common terms, find the value of the denominator.
One of the hardest things—for me, at least—about problem solving is actually understanding the problem. Left this one off for a while because I wasn't sure what was meant by trivial. Of course then I decided to apply my brain properly and realized that a nontrivial example would look like this: ab/ca or ba/ac, if a, b and c are digits.
Wrote a function to check if a fraction is nontrivial and soon discovered a problem: if b & c were equal (ie, the numerator and denominator were palindromes), I would end up cancelling out a total of 4 digits and wouldn't have any number left at all!
So, I concluded, for the numerator n and denominator d of the fraction f, these conditions need to be true:
And, happily, these conditions found me exactly four rational fractions. The rest was easy as pie: just folded over a list of the four fractions with a function that multiplies rational numbers, simplified the result, and extracted the denominator. Happy day :]
Project Euler 97, find the last ten digits of 28433×2^7830457+1.
Oh gods this is embarrassing.
I spent the longest time wondering what was wrong with this:
theprime = 28433 * (2^7830457)+1
last10 = take 10 $ reverse $ show theprime
main = print last10
And now I know! I got all the right digits, but in the wrong order because I initially reversed number. (Is this another one of those problems that can be optimized? Unsure how I would go about that….)
Posting this one so I don't forget how silly I am!
More Project Euler! Here's 53: how many, not necessarily distinct, values of nCr, for 1 ≤ n ≤ 100, are greater than one-million?
This ended up being much, much easier than I expected! I felt this was so simple it may not have even deserved an accompanying blog post.
We are given an equation for nCr, so I simply wrote a function to implement it, as well as a recursive function for the factorial, n!. (Does Haskell have one? I bet it does….)
Wrote a simple list comprehension that passed n from 1 to 100 and r from 1 to n into nCr, kept the result around if it was greater than one–million, and then counted those up with length! The hardest part was making sure I had the right amount of zeroes in one–million ;P