SICP 2.3 exercises cont.

2.58

Part A is easy.

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list a1 '+ a2))))

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list  m1 '* m2))))

(define (sum? x)
  (and (pair? x) (eq? (cadr x) '+)))

(define (addend s) (car s))

(define (augend s) (caddr s))

(define (product? x)
  (and (pair? x) (eq? (cadr x) '*)))

(define (multiplier p) (car p))

(define (multiplicand p) (caddr p))

Part B took me a good chunk of the day to get right.

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list a1 '+ a2))))

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        ((product? m1) (append m1 (cons '* m2)))
        ((product? m2) (append (list m1 '*) m2))
        (else (list  m1 '* m2))))

(define (simplify e)
  (if (null? (cdr e)) (car e) e))

(define (sum? x)
  (if (and (pair? x) (not (null? (cdr x))))
      (or (eq? (cadr x) '+) (sum? (cddr x)))
    #f))

(define (addend s)
  (if (product? s)
      (make-product (car s) (addend (cddr s)))
      (car s)))

(define (augend s)
  (if (product? s)
      (augend (cddr s))
      (simplify (cddr s))))

(define (product? x)
  (if (and (pair? x) (not (null? (cdr x))))
    (eq? (cadr x) '*)
    #f))

(define (multiplier p) (car p))

(define (multiplicand p)
  (simplify (cddr p)))

I half cheated by looking here, but actually the last part is not good enough as it doesn’t handle precedence. Meanwhile the scheme wiki has some complex looking solutions which I couldn’t be bothered to read properly. In the end, I went with some recursive definitions for the addition selectors and predicates which is easier to understand (to me, anyway) and works, at least for the examples I’ve tested.

(deriv '((3 + 4) * x * y + 4 * z + x) 'x)
(((3 + 4) * y) + 1)

(deriv '(3 * x * y * z + 6 * x * c) 'x)
((3 * y * z) + (6 * c))

2.59

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((element-of-set? (car set1) set2) (union-set (cdr set1) set2))
        (else (cons (car set1) (union-set (cdr set1) set2)))))

2.60

(define (adjoin-set x set)
  (cons x set))

(define (union-set set1 set2)
  (append set1 set2))

element-of? and intersection-set are the same as before. The result is faster union and adjoin operations, but slower membership and intersection operations, so this representation would be preferred where sets grow frequently.

2.61

(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((= x (car set)) set)
        ((< x (car set)) (cons x set))
        (else (cons (car set) (adjoin-set x (cdr set))))))

2.62

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else (let ((x1 (car set1)) (x2 (car set2)))
                (cond ((= x1 x2)
                       (cons x1 (union-set (cdr set1) (cdr set2))))
                      (( x1 x2)
                       (cons x2 (union-set set1 (cdr set2)))))))))
Advertisements

One Comment on “SICP 2.3 exercises cont.”

  1. angelo says:

    difficile trovare persone competenti su questo argomento, ma sembra che voi sappiate di cosa state parlando! Grazie


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s