SICP Exercise 2.62 union-set (ordered representation)

Exercise 2.62.  Give a (n) implementation of union-set for sets represented as ordered lists.

SOLUTION

 The code and tests are here.

Comments

Post a Comment

Popular posts from this blog

SICP Exercise 1.28 (Miller-Rabin Test)

Exercise 1.28.    One variant of the Fermat test that cannot be fooled is called the  Miller-Rabin test  (Miller 1976; Rabin 1980). This starts from  an alternate form of Fermat's Little Theorem, which states that if  n  is a prime number and  a  is any positive integer less than  n , then  a  raised to the ( n  - 1)st power is congruent to 1 modulo  n . To test the primality of a number  n  by the Miller-Rabin test, we pick a random number  a < n  and raise  a  to the ( n  - 1)st power modulo  n  using the  expmod  procedure. However, whenever we perform the squaring step in  expmod , we check to see if we have discovered a ``nontrivial square root of 1 modulo  n ,'' that is, a number not equal to 1 or  n  - 1 whose square is equal to 1 modulo  n . It is possible to prove that if such a nontrivial square root of 1 exists, then  n  is not prime. It is also possible to prove that if  n  is an odd number that is not prime, then, for at least half the numbers a < n , co
Read more

SICP Exercise 4.4 eval support for and and or

Exercise 4.4.    Recall the definitions of the special forms  and  and  or  from chapter 1: and : The expressions are evaluated from left to right. If any expression evaluates to false, false is returned; any remaining expressions are not evaluated. If all the expressions evaluate to true values, the value of the last expression is returned. If there are no expressions then true is returned. or : The expressions are evaluated from left to right. If any expression evaluates to a true value, that value is returned; any remaining expressions are not evaluated. If all expressions evaluate to false, or if there are no expressions, then false is returned. Install  and  and  or  as new special forms for the evaluator by defining appropriate syntax procedures and evaluation procedures  eval-and  and  eval-or . Alternatively, show how to implement  and  and  or  as derived expressions. SOLUTION I have implemented the solution in two ways as suggested in the problem above: a) Installed 
Read more

SICP Exercise 3.11 make-account internal definitions with local state

Image
Exercise 3.11.    In section  3.2.3  we saw how the environment model described the behavior of procedures with local state. Now we have seen how internal definitions work. A typical message-passing procedure contains both of these aspects. Consider the bank account procedure of section  3.1.1 : (define (make-account balance)   (define (withdraw amount)     (if (>= balance amount)         (begin (set! balance (- balance amount))                balance)         "Insufficient funds"))   (define (deposit amount)     (set! balance (+ balance amount))     balance)   (define (dispatch m)     (cond ((eq? m 'withdraw) withdraw)           ((eq? m 'deposit) deposit)           (else (error "Unknown request -- MAKE-ACCOUNT"                        m))))   dispatch) Show the environment structure generated by the sequence of interactions (define acc (make-account 50)) ((acc 'deposit) 40) 90 ((acc 'withdraw) 60) 30 Where is the local state for  acc  kep
Read more