A polynomial package turns algebra into operations on tagged data.
Sparse term lists keep powers and coefficients explicit. Generic add and multiply methods merge equal orders, omit zero coefficients, preserve the polynomial variable, and reject incompatible variables.
How can a generic arithmetic system manipulate polynomial structure without scattering term-list details through client code?
- Represent a sparse polynomial as a variable plus descending terms
- Merge equal powers while adding two term lists
- Distribute one term across a polynomial during multiplication
- Remove zero-coefficient terms at the representation boundary
- Dispatch polynomial add and multiply through type-tagged methods
- Reject operations whose polynomial variables do not match
The first program represents each term as an order and coefficient and stores terms from highest order to lowest. add-terms performs the same ordered merge used earlier for sets: the larger order is copied, equal orders are combined, and adjoin-term omits a zero result. The polynomial package owns that representation and exposes one tagged add method. Adding x² + 2x + 1 to x² − 1 therefore produces 2x² + 2x without leaving an explicit zero constant term. A y polynomial returns different-variables instead of silently combining unrelated indeterminates.
The second program multiplies one term by every term in the other polynomial, shifts orders by addition, multiplies coefficients, and merges the partial products through add-terms. Multiplying x + 1 by x − 1 creates two middle terms that cancel, leaving x² − 1. A separate evaluator consumes only the package selectors and reports 8 at x = 3. This lesson models sparse univariate integer-coefficient polynomials; it does not implement dense representations, multivariate normalization, polynomial gcd, rational functions, or a complete computer algebra system.
(begin
(define (attach-tag type contents) (cons type contents))
(define (type-tag object) (car object))
(define (contents object) (cdr object))
(define (make-term order coefficient)
(list order coefficient))
(define (order term) (car term))
(define (coefficient term) (cadr term))
(define (adjoin-term term terms)
(if (= (coefficient term) 0)
terms
(cons term terms)))
(define (add-terms left right)
(cond ((null? left) right)
((null? right) left)
(else
(let ((left-term (car left))
(right-term (car right)))
(cond ((> (order left-term) (order right-term))
(adjoin-term
left-term
(add-terms (cdr left) right)))
((< (order left-term) (order right-term))
(adjoin-term
right-term
(add-terms left (cdr right))))
(else
(adjoin-term
(make-term
(order left-term)
(+ (coefficient left-term)
(coefficient right-term)))
(add-terms (cdr left) (cdr right)))))))))
(define (make-polynomial variable terms)
(attach-tag 'polynomial (cons variable terms)))
(define (variable polynomial-contents)
(car polynomial-contents))
(define (term-list polynomial-contents)
(cdr polynomial-contents))
(define (add-polynomial-contents left right)
(if (eq? (variable left) (variable right))
(make-polynomial
(variable left)
(add-terms (term-list left) (term-list right)))
'different-variables))
(define operation-table
(list
(cons (list 'add 'polynomial 'polynomial)
add-polynomial-contents)))
(define (lookup-entry key table)
(cond ((null? table) #f)
((equal? key (car (car table)))
(cdr (car table)))
(else (lookup-entry key (cdr table)))))
(define (apply-generic operation left right)
(let ((method
(lookup-entry
(list operation (type-tag left) (type-tag right))
operation-table)))
(if method
(method (contents left) (contents right))
'no-method)))
(define p
(make-polynomial
'x
(list (make-term 2 1)
(make-term 1 2)
(make-term 0 1))))
(define q
(make-polynomial
'x
(list (make-term 2 1)
(make-term 0 -1))))
(define y
(make-polynomial 'y (list (make-term 1 1))))
(list (apply-generic 'add p q)
(apply-generic 'add p y)))- Output
- —
- Value
- —
- Diagnostic
- —
The addition program returns ((polynomial x (2 2) (1 2)) different-variables). The multiplication program returns ((polynomial x (2 1) (0 -1)) 8).
In addition, follow the descending-order comparison and locate the equal-order coefficient sum that drops the zero constant term. In multiplication, follow each order shift, coefficient product, recursive partial product, and add-terms merge that cancels the two order-1 terms. The variable check happens before either representation operation proceeds.
Change the program before you read the hint.
Multiply x² + x + 1 by x − 1, predict the sparse term list, and evaluate the result at x = 2.
Show one hint
Generate one partial product for each left term, then merge equal orders. The order-1 and order-0 cancellations happen at different stages.