Let's see how much DrScheme knows about math.
We all know that 1 + 2 is the same as 2 + 1.
(Don't we?)
We all know that 1 + 2 + 3 is the same as 3 + 2 + 1.
It doesn't matter in what order we add numbers, the sum is
always the same.
Let's make sure DrScheme agrees. Write the following two programs to test this out. Do not use Scheme loops!
|# ; sum-R->L : (Listof Number) -> Number ; Adds up a list of numbers from right to left. (define (sum-R->L lon) ...) ; sum-L->R : (Listof Number) -> Number ; Adds up a list of numbers from left to right. (define (sum-L->R lon) ...) #|Here are some examples that explain what we mean:
(sum-R->L (list 3 4 5)) -> (+ 3 (+ 4 (+ 5 0))) (sum-R->L (list 4)) -> 4 (sum-R->L empty) -> 0 (sum-L->R (list 2 3 4 5)) -> (+ (+ (+ 2 3) 4) 5)) (sum-L->R empty) -> 0 (sum-L->R (list 8)) -> 8
For the first example we just follow the design recipe in a straightforward way.
Let us now think about adding the numbers left to right. The examples suggest that we want to compute the following intermediate values:
(first lon) (+ (first lon) (second lon)) (+ (+ (first lon) (second lon)) (third lon)) (+ (+ (+ (first lon) (second lon)) (third lon)) (fourth lon))
The first item in the addition is the sum computed so far. The second item is the next leading element in the remainder of the list.
We need a helper method:
;; produce the sum of the current sum and all elements of the list ;; sum-acc: Number [Listof Number} -> Number (define (sum-acc curr-sum lon) ...)
Maybe it would help to make some more examples:
(sum-acc 2 (list 3 4 5)) -> (+ (+ (+ 2 3) 4) 5)
(sum-acc n empty) -> n
(sum-acc n (list nn)) -> (+ n nn)
(sum-acc n (list n1 n2 n3 ...)) -> (sum-acc (+ n n1) (n2 n3 ...))
-> (sum-acc (+ (+ n n1) n2) (n3 ...))
The last example is helpful. We highlight what is going on:
(sum-acc n (list n1 n2 n3 ...))
-- --
(sum-acc (+ n n1) (n2 n3 ...))
----+--- --
(sum-acc (+ (+ n n1) n2) (n3 ...))
-----------+--- --
We see that the function sum-acc is invoked at each next step with a new value of the accumulator and the rest of the list as its two arguments. The new value of the accumulator is computed by adding the current accumulator to the value of the first element of the list.
We leave it up to you to finish the design of this function.
Now test these programs against each other: Make up some lists of numbers and make sure that
(equals? (sum-L->R a-list) (sum-R->L a-list))
for each list.
It seems like DrScheme agrees with us.
Let's try another example.
|#
(define JANUS
(list #i31
#i2e+34
#i-1.2345678901235e+80
#i2749
#i-2939234
#i-2e+33
#i3.2e+270
#i17
#i-2.4e+270
#i4.2344294738446e+170
#i1
#i-8e+269
#i0
#i99))
#|
These funny looking numbers that start with #i are just one
way of representing numbers. You'll find numbers like these
in every popular programming language, not just DrScheme.
Numbers like #i2e+34 just mean 2 times
10 to the power of
34, or 2 with 34 zeros after it.
Try running (sum-L->R JANUS).
Try running (sum-R->L JANUS).
The unfortunate side effect is that even simple operations like addition can give wildly inaccurate answers. When adding up JANUS, for instance, we got a small positive number one time and a huge negative number the other!
Care to guess which one was the right answer? Was either one the right answer?
Now try to work out Exercise 31.3.1 in HtDP.
We recognize the need for accumulator when the intermediate computation within the recursive function we are trying to design requires that we remember some information encountered earlier in the computation. The examples of computing the sum or a product of all numbers qualifies only if we specify the order in which the operation should be performed.
Next we think of the meaning of the accumulator. The following two hints may help. First, the accumulator value has the same type as the expected result. Next we determine what should the function compute when there is only one piece of information that we need to remember. This value becomes the value of the first accumulator, and is the value produced when the problem is small enough so that the recursive function invocation never happens.
At this point we should write a comment that explains the meaning of the accumulator. Additionally, we should specify the invariant that the accumulator needs to satisfy. (For explanation of how to specify the invariant, please read the relevant pages in the HtDP text.)
The template for the whole function then becomes:
;; produce a value of the type Y from the given list of X
;; rec-fcn: [Listof X] -> Y
(define (rec-fcn lox)
(rec-fcn-acc base-acc-value lox))
;; recur with updated accumulator, unless the end of list is reached
;; rec-fcn-acc: [Listof X] Y -> Y
(define (rec-fcn-acc lox acc)
(cond
;; at the end produce the accumulated value
[(empty? lox) acc]
;; otherwise invoke rec-fcn-acc with updated accumulator and the rest of the list
[(cons? lox) (rec-fcn-acc (rest lox)
(update acc (first lox))
Identify the parts of this template in your solution to the addition problem.
Next we design two functions that compute the factorial of a given number. We recall that we can define factorial of 5 as one of the following two values:
5! = 1 . 2 . 3 . 4 . 5 5! = 5 . 4 . 3 . 2 . 1
Design the functions fac-L->R and fac-R->L that compute a factorial of the given number.
For help consult HtDP, exercise 31.3.2 and the text before this exercise. Run the exercise 31.3.2 and verify the book's assertions about the times needed to compute the two results.
Now design two variants of the function that produces a product of all numbers in a given list.