By imposing an ordering on variables, extend the polynomial package so that addition and multiplication of polynomials works for polynomials in different variables. (This is not easy!)
From Naïve to "Not Easy"
In what I called the "naïve approach" to this exercise, we based our solution upon the observation that a polynomial of one indeterminate can be expressed as a polynomial of another indeterminate by simply treating the former polynomial as the coefficient of the zero-order term of the latter polynomial. We also showed exposed the limitations of this approach using the following example arithmetic operation:((5y2 + 2y - 1)x2 + (2y2 + y + 2)x - 3) - ((5x2 + 2x)y2 + (2x2 + x)y - (x2 - 2x + 5))..which, using the naïve approach, would give us the result:
((5y2 + 2y - 1)x2 + (2y2 + y + 2)x - ((5x2 + 2x)y2 + (2x2 + x)y - (x2 - 2x - 2))...but which, using the approach of first converting "one polynomial to the type of the other by expanding and rearranging terms" and then performing the calculation would work out as follows:
((5y2 + 2y - 1)x2 + (2y2 + y + 2)x - 3) - ((5x2 + 2x)y2 + (2x2 + x)y - (x2 - 2x + 5)) = ((5y2 + 2y - 1)x2 + (2y2 + y + 2)x - 3) - (5x2y2 + 2xy2 + 2x2y + xy - x2 + 2x - 5) = ((5y2 + 2y - 1)x2 + (2y2 + y + 2)x - 3) - (5y2x2 + 2y2x + 2yx2 + yx - x2 + 2x - 5) = ((5y2 + 2y - 1)x2 + (2y2 + y + 2)x - 3) - (5y2x2 + 2yx2 - x2 + 2y2x + yx + 2x - 5) = ((5y2 + 2y - 1)x2 + (2y2 + y + 2)x - 3) - ((5y2 + 2y - 1)x2 + (2y2 + y + 2)x - 5) = (5y2 + 2y - 1)x2 + (2y2 + y + 2)x - 3 - (5y2 + 2y - 1)x2 - (2y2 + y + 2)x + 5 = (5y2 + 2y - 1)x2 - (5y2 + 2y - 1)x2 + (2y2 + y + 2)x - (2y2 + y + 2)x - 3 + 5 = 5 - 3 = 2In this post we're going to tackle the full "this is not easy" solution to the problem. However, as you'll see, doing so is going to require us to reconsider the decision we made about the interface for term-list representations we made back in exercise 2.90. Let's discuss what we need to do to see why...
Expanding and Rearranging Terms
In order to convert a polynomial into "canonical" form (i.e. "with the highest-priority variable dominant and the lower-priority variables buried in the coefficients") we need to perform a recursive expand and rearrange of the polynomial. Given a polynomial p we first ensure that all of the coefficients of p that are themselves polynomials are expressed in canonical form, then we "expand and collapse" p. Our example above shows how the expand and collapse works when its performed manually. Let's try to state the steps involved.Given a polynomial p in y whose highest-priority variable is x, we can convert this into an equivalent polynomial in x with coefficients in y by:
- Iterating through the terms of p and, for each term:
- If the coefficient of the term is itself a polynomial then recursively expand and rearrange its terms to ensure that it is itself in canonical form. This is necessary as there may be a polynomial in x, or indeed in y buried somewhere in coefficients and these need to be raised to the top-level.
- Multiply the term's coefficient by yn, where n is the order of the term for which this is the coefficient. We can achieve this programmatically by creating a polynomial in y with a single term with order n and a coefficient of 1, and using this as the multiplicand representing yn.
- Convert the result of this multiplication into a polynomial in x. The process for this is identical to the one implemented by the procedure
express-inwhich we developed in the naïve approach. I.e. If the result of the multiplication is not already polynomial in x then create a polynomial in x using the result of the multiplication as the coefficient of its zero-order term.
- Add the converted coefficients together.
polynomial package. As a result, we'd have a choice between:
- Passing both the principal and original variables to the term-list packages in order that they could both perform the multiplication and create the resulting polynomial in x.
- Passing the original variable to the term-list packages in order that they could perform the multiplication and return a list of the resulting coefficients, which the
polynomialpackage could turn into the resulting polynomial in x.
So what do we do?
Time for a Rewrite
In the previous exercise we noted that we could have chosen an alternative, lower-level, interface to our term-list packages. If we had exposed an interface at the level offirst-term, rest-terms, adjoin-term, the-empty-termlist and empty-termlist? then the terms (and so the coefficients) would not be hidden to the polynomial package, and so would mean that expanding and rearranging terms could be performed within the polynomial package itself. It would also allow us to replace a lot of duplicate (or very similar) operations from the term-list packages (i.e. add-terms, etc.) with a single implementation of each operation in the polynomial package.We also noted in the previous exercise that if we'd made this choice of API then various issues would arise. We noted that the
first-term operation would need to return a term, which would lead to a lot of term creation for dense term-lists. We also noted that, adjoin-term would need to take a tagged representation of a term whose tag would be stripped off when the actual operations were applied, meaning that term-list representations would need to be able to manipulate the internal representation of a term, destroying the encapsulation. A third issue we didn't raise is that of the-empty-termlist. This operation does not have any arguments, so it would not be possible for apply-generic to determine which of the installed versions of the operation to invoke.So how can we address these issues?
Well the
terms that get created by first-term for dense term-lists are normally going to be short-lived. So let's ignore this issue and assume that Scheme's garbage collector will take care of it efficiently.As for the other two issues we can simply state that
apply-generic is not the appropriate calling mechanism to use. We've defined the interface, so any valid implementation of a term-list must have implementations of adjoin-term and the-empty-termlist (as well as first-term, rest-terms and empty-termlist?). As a result we can implement the former by getting the operation installed under the operation key 'adjoin-term and the type tag of the term-list, then invoking it with the term we want to adjoin and the contents of the term-list that we want to adjoin to. Note that this way we don't lose the encapsulation of term. As for the-empty-termlist, we can simply select a default representation (I went for a sparse term-list) and get and use this instance of the operation.In fact we can go further and remove
'sparse-terms and 'dense-terms from the tower-of-types entirely. They're internal representation details of the polynomial package, so it can be argued that they don't really belong in the tower. I know, I put them there in the first place. Hey, I'm allowed to change my mind, aren't I?
Exercise 2.90 Revisited
Okay, with that in mind, we can rewrite thesparse, dense and polynomial packages with this new interface. I.e. let's do exercise 2.90 all over again! We'll also include the changes necessary to support div-terms from exercise 2.91.I'm not going to go through the rewrite step-by-step - I want to get onto the expansion and rearrangement of terms necessary to perform the full solution for this exercise. I will, however, provide a running commentary as we go through the code.
Sparse Term-Lists
So let's begin with thesparse package. We can basically keep the implementations of adjoin-term, the-empty-termlist, first-term, rest-terms and empty-termlist? as they are. However, I chose to rewrite ajoin-term so that it checks that we don't violate the invariants of the representation.
;;;
;;; Sparse
;;;
(define (install-sparse-terms-package)
;; internal procedures
;; representation of terms and term lists
(define (adjoin-term term term-list)
(cond ((=zero? (coeff term)) term-list)
((or (empty-termlist? term-list)
(> (order term) (order (first-term term-list))))
(cons term term-list))
(else (error
"Cannot adjoin term of lower order than term list -- ADJOIN-TERM"
(list term term-list)))))
(define (the-empty-termlist) '())
(define (first-term term-list) (car term-list))
(define (rest-terms term-list) (cdr term-list))
(define (empty-termlist? term-list) (null? term-list))
Creation of sparse term lists is pretty much identical to before...
;; creation
(define (insert-term term terms)
(if (empty-termlist? terms)
(adjoin-term term terms)
(let* ((head (first-term terms))
(head-order (order head))
(term-order (order term)))
(cond ((> term-order head-order) (adjoin-term term terms))
((= term-order head-order)
(adjoin-term (make-term term-order (add (coeff term) (coeff head)))
(rest-terms terms)))
(else (adjoin-term head (insert-term term (rest-terms terms))))))))
(define (build-terms terms result)
(if (null? terms)
result
(build-terms (cdr terms) (insert-term (car terms) result))))
(define (make-from-terms terms)
(build-terms terms (the-empty-termlist)))
(define (convert-to-term-list coeffs)
(if (null? coeffs)
(the-empty-termlist)
(adjoin-term (make-term (- (length coeffs) 1) (car coeffs))
(convert-to-term-list (cdr coeffs)))))
(define (make-from-coeffs coeffs)
(convert-to-term-list coeffs))
We'll also retain an implementation of sparse-terms->dense-terms for coercion purposes. However this is much simpler than before, as we're going to move the decision of when to coerce up into the polynomial package.
;; Coercion
(define (sparse-terms->dense-terms L)
((get 'make-from-terms 'dense-terms) L))
And that's it for the sparse term-list operation implementations. We throw out all the higher-level term-list manipulation procedures (or rather we promote them up into the polynomial package). All that remains is to install these operations appropriately. Note when tagging is used. We don't tag the results of first-term, as this returns a term, or of empty-termlist?, as it's a predicate. However, we need to tag the results of the others as they return sparse term-lists.
;; interface to rest of the system
(define (tag tl) (attach-tag 'sparse-terms tl))
(put 'adjoin-term 'sparse-terms
(lambda (t tl) (tag (adjoin-term t tl))))
(put 'the-empty-termlist 'sparse-terms
(lambda () (tag (the-empty-termlist))))
(put 'first-term '(sparse-terms)
(lambda (tl) (first-term tl)))
(put 'rest-terms '(sparse-terms)
(lambda (tl) (tag (rest-terms tl))))
(put 'empty-termlist? '(sparse-terms)
(lambda (tl) (empty-termlist? tl)))
(put 'make-from-terms 'sparse-terms
(lambda (terms) (tag (make-from-terms terms))))
(put 'make-from-coeffs 'sparse-terms
(lambda (coeffs) (tag (make-from-coeffs coeffs))))
(put-coercion 'sparse-terms 'dense-terms sparse-terms->dense-terms)
'done)
Dense Term-Lists
Dense term-lists require a bit more work. We still reduce the package down to the low-level operations only. However, previously these operations dealt with coefficients and orders separately. Now our term-list interface stipulates that these should operate on the higher-levelterm encapsulation. So adjoin-term splits a term into its components up front in order to perform the adjoining, while first-term has to construct a term of the appropriate order, using the head of the internal representation as the coefficient.I've also taken an additional step here. I've provided a guarantee that
first-term will always return the first non-zero term in the term-list, or a zero-order term with a coefficient of 0 if the term-list is empty. Similarly I've provided a guarantee that either the head of rest-terms will be a non-zero term, or there will be no more terms.
;;;
;;; Dense
;;;
(define (install-dense-terms-package)
;; internal procedures
;; representation of term lists
(define (adjoin-term term term-list)
(let ((term-order (order term))
(term-coeff (coeff term)))
(cond ((=zero? term-coeff) term-list)
((= term-order (+ 1 (term-list-order term-list)))
(cons term-coeff term-list))
((> term-order (term-list-order term-list))
(adjoin-term term (cons zero term-list)))
(else (error
"Cannot adjoin term of lower order than term list -- ADJOIN-TERM"
(list term term-list))))))
(define (the-empty-termlist) '())
(define (first-term term-list)
(if (empty-termlist? term-list)
(make-term 0 zero)
(let ((head (car term-list)))
(if (=zero? head)
(first-term (cdr term-list))
(make-term (term-list-order term-list) (car term-list))))))
(define (rest-terms term-list)
(let ((tail (cdr term-list)))
(cond ((empty-termlist? tail) tail)
((=zero? (car tail)) (rest-terms tail))
(else tail))))
(define (empty-termlist? term-list) (null? term-list))
(define (term-list-order term-list)
(- (length term-list) 1))
The same thing occurs with the creation procedures. These are similar to before. However, we can take advantage of first-term returning a term and so bring the implementation into line with the sparse term-list implementation. Note that we retain the two separate implementations here though, rather than promoting it up to the polynomial package, as the orderings imposed upon the terms are internal details of the two representations. It just so happens that they use the same ordering.
;; Creation
(define (strip-leading-zeros coeffs)
(cond ((empty-termlist? coeffs) (the-empty-termlist))
((not (=zero? (first-term coeffs))) coeffs)
(else (make-from-coeffs (rest-terms coeffs)))))
(define (make-from-coeffs coeffs) coeffs)
(define (insert-term term terms)
(if (empty-termlist? terms)
(adjoin-term term terms)
(let* ((head (first-term terms))
(head-order (order head))
(term-order (order term)))
(cond ((> term-order head-order) (adjoin-term term terms))
((= term-order head-order)
(adjoin-term (make-term term-order (add (coeff term) (coeff head)))
(rest-terms terms)))
(else (adjoin-term head (insert-term term (rest-terms terms))))))))
(define (build-terms terms result)
(if (null? terms)
result
(build-terms (cdr terms) (insert-term (car terms) result))))
(define (make-from-terms terms)
(build-terms terms (the-empty-termlist)))
We retain the coercion procedure unchanged from before, although you'll note the lack of to-best-representation. As explained in the sparse term-list implementation we're going to push the decision about representation up to the polynomial package.
;; Coercion
(define (dense-terms->sparse-terms L)
((get 'make-from-coeffs 'sparse-terms) L))
;; interface to rest of the system
(put 'adjoin-term 'dense-terms
(lambda (t tl) (tag (adjoin-term t tl))))
(put 'the-empty-termlist 'dense-terms
(tag (the-empty-termlist)))
(put 'first-term '(dense-terms)
(lambda (tl) (first-term tl)))
(put 'rest-terms '(dense-terms)
(lambda (tl) (tag (rest-terms tl))))
(put 'empty-termlist? '(dense-terms)
(lambda (tl) (empty-termlist? tl)))
(put 'make-from-terms 'dense-terms
(lambda (terms) (tag (make-from-terms terms))))
(put 'make-from-coeffs 'dense-terms
(lambda (coeffs) (tag (make-from-coeffs coeffs))))
(put-coercion 'dense-terms 'sparse-terms dense-terms->sparse-terms)
'done)
Having completed the sparse and dense term-list packages we can move onto the polynomial package itself. The basic creation representation and variable manipulation procedures remain as before.
;;;
;;; Polynomial wrapper package
;;;
(define (install-polynomial-package)
;; internal procedures
;; representation of poly
(define (make-poly variable term-list)
(cons variable term-list))
(define (make-from-coeffs variable coeffs)
(make-poly variable
((get 'make-from-coeffs 'dense-terms) coeffs)))
(define (make-from-terms variable terms)
(make-poly variable
((get 'make-from-terms 'sparse-terms) terms)))
(define (variable p) (car p))
(define (term-list p) (cdr p))
;; variable tests and selection
(define (variable? x) (symbol? x))
(define (same-variable? v1 v2)
(and (variable? v1)
(variable? v2)
(or (eq? v1 v2)
(eq? v1 'unbound)
(eq? v2 'unbound))))
(define (select-variable p1 p2)
(let ((v1 (variable p1)))
(if (eq? v1 'unbound)
(variable p2)
v1)))
Next we add in the term-list manipulation operations here. As noted above we're making the assumption that 'adjoin-term must be installed for any valid term-list so we can get and call it directly, unbundling the contents of the term-list as we do so. We also stated that we'd use the empty term-list for sparse term-lists as our default empty term list. We'll just use apply-generic for the others to keep the code a bit cleaner, even though we'll not be taking advantage of any coercion.
;; Term-list manipulation
(define (first-term L)
(apply-generic 'first-term L))
(define (rest-terms L)
(apply-generic 'rest-terms L))
(define (empty-termlist? L)
(apply-generic 'empty-termlist? L))
(define (adjoin-term term term-list)
((get 'adjoin-term (type-tag term-list)) term (contents term-list)))
(define (the-empty-termlist)
((get 'the-empty-termlist 'sparse-terms)))
Now we provide the implementations of the arithmetic operations. To do this we need to bring the term-list portions of the operations back into the polynomial package. We can use the sparse term-list implementations from before as the interface we've changed to is the lower-level interface that sparse term-lists were using.
;; procedures used by add-poly
(define (add-poly p1 p2)
(make-poly (select-variable p1 p2)
(add-terms (term-list p1)
(term-list p2))))
(define (add-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 (add-terms (rest-terms L1) L2)))
((< (order t1) (order t2))
(adjoin-term
t2 (add-terms L1 (rest-terms L2))))
(else
(adjoin-term
(make-term (order t1)
(add (coeff t1) (coeff t2)))
(add-terms (rest-terms L1)
(rest-terms L2)))))))))
;; procedures used by mul-poly
(define (mul-poly p1 p2)
(make-poly (select-variable p1 p2)
(mul-terms (term-list p1)
(term-list p2))))
(define (mul-terms L1 L2)
(if (empty-termlist? L1)
(the-empty-termlist)
(add-terms (mul-term-by-all-terms (first-term L1) L2)
(mul-terms (rest-terms L1) L2))))
(define (mul-term-by-all-terms t1 L)
(if (empty-termlist? L)
(the-empty-termlist)
(let ((t2 (first-term L)))
(adjoin-term
(make-term (+ (order t1) (order t2))
(mul (coeff t1) (coeff t2)))
(mul-term-by-all-terms t1 (rest-terms L))))))
;; procedures used by div-poly
(define (div-poly p1 p2)
(let ((variable (select-variable p1 p2))
(result (div-terms (term-list p1) (term-list p2))))
(list (make-poly variable (car result))
(make-poly variable (cadr result)))))
(define (div-terms L1 L2)
(if (empty-termlist? L1)
(list (the-empty-termlist) (the-empty-termlist))
(let ((t1 (first-term L1))
(t2 (first-term L2)))
(if (> (order t2) (order t1))
(list (the-empty-termlist) L1)
(let* ((new-c (div (coeff t1) (coeff t2)))
(new-o (- (order t1) (order t2)))
(new-t (make-term new-o new-c))
(rest-of-result
(div-terms
(add-terms L1
(negate-terms (mul-term-by-all-terms new-t L2)))
L2)))
(list (adjoin-term new-t (car rest-of-result))
(cadr rest-of-result)))))))
;; Subtraction
(define (sub-poly p1 p2)
(add-poly p1 (negate-poly p2)))
;; zero test
(define (=zero-poly? p)
(=zero-all-terms? (term-list p)))
(define (=zero-all-terms? L)
(cond ((empty-termlist? L) #t)
((not (=zero? (coeff (first-term L)))) #f)
(else (=zero-all-terms? (rest-terms L)))))
;; Negation
(define (negate-poly p)
(make-poly (variable p)
(negate-terms (term-list p))))
(define (negate-terms L)
(if (empty-termlist? L)
(the-empty-termlist)
(let ((term (first-term L)))
(adjoin-term (make-term (order term)
(negate (coeff term)))
(negate-terms (rest-terms L))))))
;; Equality
(define (equ-poly? p1 p2)
(and (same-variable? (variable p1) (variable p2))
(equ-terms? (term-list p1) (term-list p2))))
(define (equ-terms? L1 L2)
(cond ((=zero-all-terms? L1) (=zero-all-terms? L2))
((empty-termlist? L2) #f)
(else (and (equ? (first-term L1) (first-term L2))
(equ-terms? (rest-terms L1) (rest-terms L2))))))
As we noted above, our term-lists no longer exist within the type hierarchy, and so we'll perform any necessary coercions ourselves. If you remember, back in exercise 2.90 we introduced to-best-representation to the dense term-list package. We expand it somewhat here...First, we can perform the calculation of zero-terms within the polynomial package generically, so we put an appropriate implementation here (i.e. the sparse term-list's implementation from before). Next, we can move the selection of which representation to use in here as well, as this is the only place where we need to make such a decision. Previously we used
store-as-sparse?, which just told us whether or not sparse term-list representation should be used. I've replaced this with select-representation, which performs a similar calculation, but returns the representation to use. This then allows us to provide an implementation of to-best-representation which uses the current and desired type tags to look up the appropriate coercion operation to use.
(define (calculate-zero-terms first rest)
(if (empty-termlist? rest)
(order first)
(let ((next (first-term rest)))
(+ (- (order first) (order next) 1)
(calculate-zero-terms next (rest-terms rest))))))
(define (select-representation highest-order zero-terms)
(if (or (and (>= highest-order 10) (> (/ zero-terms highest-order) 0.1))
(and (< highest-order 10) (> zero-terms (/ highest-order 5))))
'sparse-terms
'dense-terms))
(define (to-best-representation L)
(if (empty-termlist? L)
L
(let* ((first (first-term L))
(current (type-tag L))
(desired (select-representation (order first)
(calculate-zero-terms first
(rest-terms L)))))
(if (eq? desired current)
L
(let ((raiser (get-coercion current desired)))
(if raiser
(raiser (contents L))
(error "Missing coercion -- TO-BEST-REPRESENTATION"
(list current desired))))))))
Coercion between polynomial and complex types and variable coercion remain unchanged from before...
;; Coercion
(define (get-constant L)
(cond ((empty-termlist? L) zero)
((= (order (first-term L)) 0) (coeff (first-term L)))
(else (get-constant (rest-terms L)))))
(define (polynomial->complex p)
(let ((constant (get-constant (term-list p))))
(if (is-lower? constant 'complex)
(raise-to 'complex constant)
constant)))
;; Variable coercion
(define (select-principal-variable v1 v2)
(cond ((eq? v1 'unbound) v2)
((eq? v2 'unbound) v1)
(else (let ((s1 (symbol->string v1))
(s2 (symbol->string v2)))
(if (string<=? s1 s2)
v1
v2)))))
(define (express-in principal-variable p)
(cond ((eq? principal-variable (variable p)) p)
((eq? 'unbound (variable p)) (make-poly principal-variable (term-list p)))
(else (make-from-coeffs principal-variable (list (tag p))))))
(define (coerce-and-call p1 p2 op)
(let* ((principal (select-principal-variable (variable p1) (variable p2)))
(new-p1 (express-in principal p1))
(new-p2 (express-in principal p2)))
(op new-p1 new-p2)))
...however, we now make use of to-best-representation to ensure that we select the best term-list representation for the results of arithmetic operations.
;; interface to rest of the system
(define (tag p)
(attach-tag 'polynomial
(make-poly (variable p)
(to-best-representation (term-list p)))))
(put 'add '(polynomial polynomial)
(lambda (p1 p2) (tag (coerce-and-call p1 p2 add-poly))))
(put 'mul '(polynomial polynomial)
(lambda (p1 p2) (tag (coerce-and-call p1 p2 mul-poly))))
(put 'div '(polynomial polynomial)
(lambda (p1 p2)
(let ((result (coerce-and-call p1 p2 div-poly)))
(list (drop (tag (car result)))
(drop (tag (cadr result)))))))
(put 'equ? '(polynomial polynomial) equ-poly?)
(put '=zero? '(polynomial) =zero-poly?)
(put 'negate '(polynomial)
(lambda (p) (tag (negate-poly p))))
(put 'sub '(polynomial polynomial)
(lambda (p1 p2) (tag (coerce-and-call p1 p2 sub-poly))))
(put 'make 'polynomial
(lambda (var terms) (tag (make-poly var terms))))
(put 'make-from-terms 'polynomial
(lambda (variable terms) (tag (make-from-terms variable terms))))
(put 'make-from-coeffs 'polynomial
(lambda (variable coeffs) (tag (make-from-coeffs variable coeffs))))
(put-coercion 'polynomial 'complex polynomial->complex)
'done)
All that remains is to install the top-level creation procedures and install the packages.
(define (make-polynomial-from-coeffs variable coeffs) ((get 'make-from-coeffs 'polynomial) variable coeffs)) (define (make-polynomial-from-terms variable terms) ((get 'make-from-terms 'polynomial) variable terms)) (define (make-zero-order-polynomial-from-coeff coeff) ((get 'make-from-coeffs 'polynomial) 'unbound (list coeff))) (install-term-package) (install-sparse-terms-package) (install-dense-terms-package) (install-polynomial-package)
Retesting
Now all that remains is to re-run the tests we ran in exercise 2.90:
> (define dense
(make-polynomial-from-coeffs 'x
(list (make-integer 4)
(make-integer 3)
(make-integer 2)
(make-integer 1)
zero)))
> (define dense-with-many-zeros
(make-polynomial-from-coeffs 'x
(list (make-integer 42)
zero
zero
zero
zero
zero
(make-integer -1))))
> (define sparse
(make-polynomial-from-terms 'x
(list (make-term 5 (make-integer 5))
(make-term 3 (make-integer 3))
(make-term 1 (make-integer 1)))))
> (define another-sparse
(make-polynomial-from-terms 'x
(list (make-term 5 (make-integer 5))
(make-term 3 (make-integer 3))
(make-term 1 (make-integer 1))
(make-term 0 (make-integer 3)))))
> (define very-sparse
(make-polynomial-from-terms 'x
(list (make-term 50 (make-integer 150))
(make-term 10 (make-integer 11))
(make-term 0 (make-integer 1)))))
> (define polypoly
(make-polynomial-from-coeffs
'x
(list (make-polynomial-from-coeffs 'y
(list (make-integer 2)
(make-integer 1))))))
> (add polypoly dense)
(polynomial x
dense-terms
(integer . 4)
(integer . 3)
(integer . 2)
(integer . 1)
(polynomial y
dense-terms
(integer . 2)
(integer . 1)))
> (add polypoly polypoly)
(polynomial x
dense-terms
(polynomial y
dense-terms
(integer . 4)
(integer . 2)))
> (add (add polypoly polypoly) (make-integer 3))
(polynomial x
dense-terms
(polynomial y
dense-terms
(integer . 4)
(integer . 5)))
> (add dense dense-with-many-zeros)
(polynomial x
dense-terms
(integer . 42)
(integer . 0)
(integer . 4)
(integer . 3)
(integer . 2)
(integer . 1)
(integer . -1))
> (add dense-with-many-zeros dense-with-many-zeros)
(polynomial x
sparse-terms
(term 6 (integer . 84))
(term 0 (integer . -2)))
> (add sparse sparse)
(polynomial x
sparse-terms
(term 5 (integer . 10))
(term 3 (integer . 6))
(term 1 (integer . 2)))
> (add sparse another-sparse)
(polynomial x
sparse-terms
(term 5 (integer . 10))
(term 3 (integer . 6))
(term 1 (integer . 2))
(term 0 (integer . 3)))
> (add very-sparse sparse)
(polynomial x
sparse-terms
(term 50 (integer . 150))
(term 10 (integer . 11))
(term 5 (integer . 5))
(term 3 (integer . 3))
(term 1 (integer . 1))
(term 0 (integer . 1)))
> (mul sparse dense)
(polynomial x
sparse-terms
(term 9 (integer . 20))
(term 8 (integer . 15))
(term 7 (integer . 22))
(term 6 (integer . 14))
(term 5 (integer . 10))
(term 4 (integer . 6))
(term 3 (integer . 2))
(term 2 (integer . 1)))
> (add dense sparse)
(polynomial x
dense-terms
(integer . 5)
(integer . 4)
(integer . 6)
(integer . 2)
(integer . 2)
(integer . 0))
> (sub sparse dense)
(polynomial x
sparse-terms
(term 5 (integer . 5))
(term 4 (integer . -4))
(term 2 (integer . -2)))
> (negate very-sparse)
(polynomial x
sparse-terms
(term 50 (integer . -150))
(term 10 (integer . -11))
(term 0 (integer . -1)))
> (sub (add dense (make-integer 1)) dense)
(integer . 1)
...and to re-run the tests we ran in exercise 2.91:
> (define sparse-numerator-1
(make-polynomial-from-terms 'x
(list (make-term 5 (make-integer 1))
(make-term 0 (make-integer -1)))))
> (define sparse-denominator-1
(make-polynomial-from-terms 'x
(list (make-term 2 (make-integer 1))
(make-term 0 (make-integer -1)))))
> (define sparse-numerator-2
(make-polynomial-from-terms 'x
(list (make-term 2 (make-integer 2))
(make-term 0 (make-integer 2)))))
> (define sparse-denominator-2
(make-polynomial-from-terms 'x
(list (make-term 2 (make-integer 1))
(make-term 0 (make-integer 1)))))
> (define sparse-numerator-3
(make-polynomial-from-terms 'x
(list (make-term 4 (make-integer 3))
(make-term 3 (make-integer 7))
(make-term 0 (make-integer 6)))))
> (define sparse-denominator-3
(make-polynomial-from-terms 'x
(list (make-term 4 (make-real 0.5))
(make-term 3 (make-integer 1))
(make-term 0 (make-integer 3)))))
> (define dense-numerator-1
(make-polynomial-from-coeffs 'x
(list (make-integer 1)
zero
zero
zero
zero
(make-integer -1))))
> (define dense-denominator-1
(make-polynomial-from-coeffs 'x
(list (make-integer 1)
zero
(make-integer -1))))
> (define dense-numerator-2
(make-polynomial-from-coeffs 'x
(list (make-integer 2)
zero
(make-integer 2))))
> (define dense-denominator-2
(make-polynomial-from-coeffs 'x
(list (make-integer 1)
zero
(make-integer 1))))
> (define dense-numerator-3
(make-polynomial-from-coeffs 'x
(list (make-integer 3)
(make-integer 7)
zero
zero
(make-integer 6))))
> (define dense-denominator-3
(make-polynomial-from-coeffs 'x
(list (make-real 0.5)
(make-integer 1)
zero
zero
(make-integer 3))))
> (div sparse-numerator-1 sparse-denominator-1)
((polynomial x sparse-terms (term 3 (integer . 1)) (term 1 (integer . 1)))
(polynomial x dense-terms (integer . 1) (integer . -1)))
> (div sparse-numerator-2 sparse-denominator-2)
((integer . 2)
(integer . 0))
> (div sparse-numerator-3 sparse-denominator-3)
((integer . 6)
(polynomial x sparse-terms (term 3 (integer . 1)) (term 0 (integer . -12))))
> (div dense-numerator-1 dense-denominator-1)
((polynomial x sparse-terms (term 3 (integer . 1)) (term 1 (integer . 1)))
(polynomial x dense-terms (integer . 1) (integer . -1)))
> (div dense-numerator-2 dense-denominator-2)
((integer . 2)
(integer . 0))
> (div dense-numerator-3 dense-denominator-3)
((integer . 6)
(polynomial x sparse-terms (term 3 (integer . 1)) (term 0 (integer . -12))))
> (div dense-numerator-1 sparse-denominator-1)
((polynomial x sparse-terms (term 3 (integer . 1)) (term 1 (integer . 1)))
(polynomial x dense-terms (integer . 1) (integer . -1)))
> (div sparse-numerator-1 dense-denominator-1)
((polynomial x sparse-terms (term 3 (integer . 1)) (term 1 (integer . 1)))
(polynomial x dense-terms (integer . 1) (integer . -1)))
Right, now we can get on to tackling the "not easy!" approach.
