sicp-ex-2.88



<< Previous exercise (2.87) | Index | Next exercise (2.89) >>


assem

just using the mul -1 would make sure to handle the generic negation of all types as we've already implemented the sub procedures before for the (complex,real,rational,integer) so there's no need to redo the work.

 (define (new-installation-to-polynomials) 
     (define (make-negated cur-term-list) 
         (if (null? cur-term-list ) the-empty-term-list  
             (let ((first (first-term cur-term-list))  
                   (rest (rest-terms cur-term-list))) 
                   (adjoin-term  
                                         (make-term (order first) (mul (coeff first) -1 ))  
                                         (make-negated rest))))) 
    
   (define (sub-polynomials p1 p2 )  
     (cond ((same-variable? (variable p1) (variable p2))  
            (make-poly (variable p1) 
                      (add-term (term-list p1) 
                      (make-negated (term-list p2))))) 
           (else (error "polys to the same variable SUB-POLYNOMIALS")))) 
   (put 'sub '(polynomial polynomial) sub-polynomials )) 

meterogan

  
 (define (negate x) (apply-generic 'negate x)) 
  
 ;; add into scheme-number package 
 (put 'negate 'scheme-number 
       (lambda (n) (tag (- n)))) 
  
 ;; add into rational package 
 (put 'negate 'rational 
      (lambda (rat) (make-rational (- (numer rat)) (denom rat)))) 
  
 ;; add into complex package 
 (put 'negate 'complex 
      (lambda (z) (make-from-real-imag (- (real-part z)) 
                                       (- (imag-part z))))) 
  
 ;; add into polynomial package 
 (define (negate-terms termlist) 
   (if (empty-termlist? termlist) 
         the-empty-termlist 
         (let ((t (first-term termlist))) 
           (adjoin-term (make-term (order t) (negate (coeff t))) 
                        (negate-terms (rest-terms termlist)))))) 
 (put 'negate 'polynomial 
          (lambda (poly) (make-polynomial (variable poly) 
                                          (negate-terms (term-list poly))))) 
 (put 'sub '(polynomial polynomial) 
       (lambda (x y) (tag (add-poly x (negate y))))) 
          

I have fixed all the errors in meterogan's solution.

 (define (negate x) (apply-generic 'negate x)) 
  
 ;; add into scheme-number package 
 (put 'negate '(scheme-number) 
      (lambda (x) (tag (- x)))) 
  
 ;; add into rational package 
 (put 'negate '(rational) 
      (lambda (x) (tag (make-rat (- (numer x)) (denom x))))) 
  
 ;; add into complex package 
 (put 'negate '(complex) 
      (lambda (z) (tag (make-from-real-imag (- (real-part z)) 
                                            (- (imag-part z)))))) 
  
 ;; add into polynomial package 
 (define (negate-terms termlist) 
   (if (empty-termlist? termlist) 
       (the-empty-termlist) 
       (let ((t (first-term termlist))) 
         (adjoin-term (make-term (order t) (negate (coeff t))) 
                      (negate-terms (rest-terms termlist)))))) 
 (define (negate-poly p) 
   (make-poly (variable p) (negate-terms (term-list p)))) 
 (define (sub-poly p1 p2) 
   (if (same-variable? (variable p1) (variable p2)) 
       (add-poly p1 (negate-poly p2)) 
       (error "Polys not in the same var: SUB-POLY" 
              (list p1 p2)))) 
 (put 'negate '(polynomial) 
      (lambda (p) (tag (negate-poly p)))) 
 (put 'sub '(polynomial polynomial) 
      (lambda (p1 p2) (tag (sub-poly p1 p2)))) 
  

AFAICT the only bugs in meterogan's solution are:

  1. [minor] no need to tag the negation for 'scheme-number, assuming we are living in the world of exercise 2.78 (which the authors assume in footnote 58)
  2. by directly basing sub-poly on add-poly, the error messages will have "ADD-POLY" in them, which is confusing.
  3. it's correct to use the generic negate procedure instead of "-" to support nested complex types (e.g. negating a complex number with a rational real part).

You only corrected #2.



 (define (negate-terms termlist) 
    (map  
       (lambda (t)(make-term(order t) 
                            (- (coeff t)))) 
        termlist)) 
  
 ;; I got the same idea as hi-artem to use map procedure, however I think we need to use the generic negate for coeff as well 
  
 (define (negate-poly p) 
   (make-polynomial (variable p) 
                    (map 
                      (lambda (term) 
                        (make-term 
                          (order term) 
                          (negate (coeff term)))) 
                      (term-list p)))) 

I think hi-artem is wrong and meterogan is right. Because MAP only works on lists, it is impossible to achieve Abstract masking if MAP is used.However, there are also errors in meterogan's writing.It should look like this:

 ;; add into complex package 
 (put 'negate 'complex 
      (lambda (z) (make-from-real-imag (negate (real-part z)) 
                                       (negate (imag-part z))))) 
  
 (put 'sub '(polynomial polynomial) 
       (lambda (x y) (tag (add-poly x (contents (negate (tag y))))))) 




Totti

I didn't follow the book's suggestion and implemented the sub procedure by adding the terms of the first polynomial to the multiplication of all terms of the second by -1 or -1x^0.

 (define (sub-poly p1 p2) 
       (if (same-variable? (variable p1) (variable p2)) 
           (make-poly (variable p1) 
                      (add-terms (term-list p1) 
                                 (mul-term-by-all-terms (make-term 0 -1) 
                                                        (term-list p2)))) 
           (error "Polys not in same var -- SUB-POLY" 
                  (list p1 p2)))) 

Alice

Other solutions seems to forget to tag their constructors.

  
 ;; generic negation 
 (define (negate x) 
   (apply-generic 'negate x)) 
  
 ;; in scheme number package 
 (put 'negate 'scheme-number (lambda (x) (tag (- x)))) ; tag is optional here 
  
 ;; rat package 
 (put 'negate 'rational (lambda (x) (tag (make-rat (- (numer x)) (denom x))))) 
  
 ;; into rectangular 
 (put 'negate 'rectangular (lambda (x) 
                             (tag (make-from-real-imag  
                                    (- (real-part x)) (- (imag-part x)))))) 
  
 ;; into polar 
 (put 'negate 'polar (lambda (x) (tag (make-from-mag-ang 
                                        (mag x) (+ (ang x) 180))))) 
  
 ;; into complex 
 (put 'negate 'complex negate) ; double tag system 
  
 ;; into poly 
 (define (negate-terms L) 
   (if (empty-termlist? L) the-empty-term-list ; what a stupid name, why "the"? 
     (let ((t1 (first-term L))) 
       (let ((negated-t1  
               (make-term (order t1) (negate (coeff t1))))) 
         (adjoin-term negated-t1 
                      (negate-terms (rest L))))))) 
  
 ;; Silly, but fun alternative. I'm assuming we can always multiply by minus-one 
 (define (negate-terms poly) 
   (let ((minus-one (make-term 0 -1))) 
   (make-polynomial (var poly) 
                    (mul-term-by-all-terms minus-one (terms poly))))) 
 (define (negate-poly poly) 
   (make-poly (var poly) 
              (negat-terms (terms poly)))) 
  
 (put 'negate 'polynomial (lambda (x) (tag (negate-poly x)))) 
  
  
 ;; generic sub in terms of negate and add 
 (define (sub x y) 
   (apply-generic 'add x (negate y)))  
  
 ;; We can subtract polynomials now :D 

master

Can't we just copy the strategy used in add-terms? Subtraction of polynomials boils down to subtraction of its coefficients, for which sub is defined on all types up to this point. Not that having a unary negation procedure isn't valuable, but it doesn't really seem strictly necessary in the context of the exercise. In the spirit of the book, we should really abstract out all the common code, but that's another issue.

 (define (sub-terms L1 L2) 
   (cond ((empty-termlist? L1) L2) 
         ((empty-termlist? L2) L1) 
         (else 
          (let ((t1 (first-term L1)) 
                (t2 (first-term L2))) 
            (cond ((> (order t1) (order t2)) 
                   (adjoin-term 
                    t1 (sub-terms (rest-terms t1) L2))) 
                  ((< (order t1) (order t2)) 
                   (adjoin-term 
                    t2 (sub-terms L1 (rest-terms L2)))) 
                  (else 
                   (adjoin-term 
                    (make-term (order t1) 
                               (sub (coeff t1) (coeff t2))) 
                    (sub-terms (rest-terms L1) 
                               (rest-terms L2))))))))) 

Ergomaniac

A quick note on tagging, because it seems there's confusion. Take the book example for polynomials:

This architecture is good because it abstracts the implementation details of tagging and creation from the package's users.

So, what about the missing tagging in the above solutions? Well, I think it depends. It might be reasonable to install the negation code in a negation "package", in which case you'd be using the external constructors and not tag. On the other hand, it would also be reasonable to go into each number package and add a negation procedure, in which case you'd need to tag. Answering which of these is better in practice puzzles me, honestly - see 2.76 for a good related discussion.