Posts

Showing posts from January, 2018

SICP Exercise 2.22

Image
Exercise 2.22.   Louis Reasoner tries to rewrite the first  square-list  procedure of exercise  2.21  so that it evolves an iterative process: (define (square-list items)   (define (iter things answer)     (if (null? things)         answer         (iter (cdr things)               (cons (square (car things))                     answer))))   (iter items nil)) Unfortunately, defining  square-list  this way produces the answer list in the reverse order of the one desired. Why? Louis then tries to fix his bug by interchanging the arguments to  cons : (define (square-list items)   (define (iter things answer)     (if (null? things)         answer         (iter (cdr things)               (cons answer                     (square (car things))))))   (iter items nil)) This doesn't work either. Explain. SOLUTION
Post a Comment
Read more

SICP Exercise 2.21 square-list

Exercise 2.21.   The procedure  square-list  takes a list of numbers as argument and returns a list of the squares of those numbers. (square-list (list 1 2 3 4)) (1 4 9 16) Here are two different definitions of  square-list . Complete both of them by filling in the missing expressions: (define (square-list items)   (if (null? items)       nil       (cons < ?? > < ?? >))) (define (square-list items)   (map < ?? > < ?? >)) SOLUTION The code and tests are here .
Post a Comment
Read more

SICP Exercise 2.20 same-parity

Exercise 2.20.    The procedures  + ,  * , and  list  take arbitrary numbers of arguments. One way to define such procedures is to use  define  with  dotted-tail notation . In a procedure definition, a parameter list that has a dot before the last parameter name indicates that, when the procedure is called, the initial parameters (if any) will have as values the initial arguments, as usual, but the final parameter's value will be a  list  of any remaining arguments. For instance, given the definition (define (f x y . z)  <body> ) the procedure  f  can be called with two or more arguments. If we evaluate (f 1 2 3 4 5 6) then in the body of  f ,  x  will be 1,  y  will be 2, and  z  will be the list  (3 4 5 6) . Given the definition (define (g . w)  <body> ) the procedure  g  can be called with zero or more arguments. If we evaluate (g 1 2 3 4 5 6) then in the body of  g ,  w  will be the list  (1 2 3 4 5 6) . 11 Use this notation to write a procedure  s
Post a Comment
Read more

SICP Exercise 2.19 count change

Exercise 2.19.   Consider the  change-counting program of section  1.2.2 . It would be nice to be able to easily change the currency used by the program, so that we could compute the number of ways to change a British pound, for example. As the program is written, the knowledge of the currency is distributed partly into the procedure  first-denomination  and partly into the procedure  count-change  (which knows that there are five kinds of U.S. coins). It would be nicer to be able to supply a list of coins to be used for making change. We want to rewrite the procedure  cc  so that its second argument is a list of the values of the coins to use rather than an integer specifying which coins to use. We could then have lists that defined each kind of currency: (define us-coins (list 50 25 10 5 1)) (define uk-coins (list 100 50 20 10 5 2 1 0.5)) We could then call  cc  as follows: (cc 100 us-coins) 292 To do this will require changing the program  cc  somewhat. It will still hav
Post a Comment
Read more

SICP Exercise 2.18 reverse

Exercise 2.18.   Define a procedure  reverse  that takes a list as argument and returns a list of the same elements in reverse order: (reverse (list 1 4 9 16 25)) (25 16 9 4 1) SOLUTION The code and tests are here .
Post a Comment
Read more

SICP Exercise 2.17 last-pair

Exercise 2.17.   Define a procedure  last-pair  that returns the list that contains only the last element of a given (nonempty) list: (last-pair (list 23 72 149 34)) (34) SOLUTION The code and tests are here .
Post a Comment
Read more

SICP Exercise 2.16

Exercise 2.16.   Explain, in general, why equivalent algebraic expressions may lead to different answers. Can you devise an interval-arithmetic package that does not have this shortcoming, or is this task impossible? (Warning: This problem is very difficult.) EXPLANATION Equivalent arithmetic expressions can lead to different answers. This is because each primitive operation with intervals i.e.  addition, subtraction, multiplication, division and reciprocal introduces its own error bounds into the calculation.  The center and width of the final computed interval depends upon the way in which the component intervals are combined. Can we devise an interval-arithmetic package that does not have this shortcoming? First of all, we need to be clear about the  algebraic expressions that the package will support. For each of these expressions, we will first need to determine the  algebraic form that minimizes the repetitions of intervals. Then we will need to implement this a
Post a Comment
Read more

SICP Exercise 2.15

Exercise 2.15.   Eva Lu Ator, another user, has also noticed the different intervals computed by different but algebraically equivalent expressions. She says that a formula to compute with intervals using Alyssa's system will produce tighter error bounds if it can be written in such a form that no variable that represents an uncertain number is repeated. Thus, she says,  par2  is a ``better'' program for parallel resistances than  par1 . Is she right? Why? SOLUTION Eva Lu Ator is right. We can see in the solution to exercise 2.14 that the system will produce tighter error bounds if  we minimize the repetition of intervals. So par2 is a better program than par1. We can also see from the examples in the solution to exercise 2.14 that expressions that use the same interval  everywhere also produce larger error bounds with more repetitions of the interval. In real-world engineering problems that involve complex arithmetic expressions, it may not always be possible
Post a Comment
Read more

SICP Exercise 2.14 parallel resistors

Image
After considerable work, Alyssa P. Hacker delivers her finished system. Several years later, after she has forgotten all about it, she gets a frenzied call from an irate user, Lem E. Tweakit. It seems that Lem has noticed that the formula for parallel resistors can be written in two  algebraically equivalent ways: and He has written the following two programs, each of which computes the parallel-resistors formula differently: (define (par1 r1 r2)   (div-interval (mul-interval r1 r2)                 (add-interval r1 r2))) (define (par2 r1 r2)   (let ((one (make-interval 1 1)))     (div-interval one                   (add-interval (div-interval one r1)                                 (div-interval one r2))))) Lem complains that Alyssa's program gives different answers for the two ways of computing. This is a serious complaint. Exercise 2.14.   Demonstrate that Lem is right. Investigate the behavior of the system on a variety of arithmetic expressions. Make some i
Post a Comment
Read more