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!)
In the
post covering the naïve approach to this exercise we noted that you could express a polynomial,
p, in one indeterminate as a polynomial in a different indeterminate by creating a new polynomial in the latter indeterminate with a single, zero-order, term that has the polynomial
p as its coefficient. We also outlined why this was flawed, showing how it would fail to correctly simplify polynomials. As a result, in
part 1 of the
"This is Not Easy!" approach, we covered the steps required to convert a polynomial into "canonical" form. We also rewrote our representation of term lists there as a necessary prerequisite for producing the better solution.
In this post we're going to go through this better solution.
Test Polynomials
Before we get into the solution itself, I'm going to give us some polynomials to test with...
Polynomial p1: 5x2 + (10x2 + 6x + 4)x + 3
Canonical form: 10x3 + 11x2 + 4x + 3
(define p1
(make-polynomial-from-coeffs
'x
(list (make-integer 5)
(make-polynomial-from-coeffs
'x
(list (make-integer 10)
(make-integer 6)
(make-integer 4)))
(make-integer 3))))
Polynomial p2: (10y2 + (10x2 + 6x + 4)y + 4)x2 + (10x2 + 6x + 4)x + 3
Canonical form: (10y)x4 + (6y + 10)x3 + (10y2 + 4y + 10)x2 + 4x + 3
(define p2
(make-polynomial-from-coeffs
'x
(list (make-polynomial-from-coeffs
'y
(list (make-integer 10)
(make-polynomial-from-coeffs
'x
(list (make-integer 10)
(make-integer 6)
(make-integer 4)))
(make-integer 4)))
(make-polynomial-from-coeffs
'x
(list (make-integer 10)
(make-integer 6)
(make-integer 4)))
(make-integer 3))))
Polynomial p3: (x2 + 5x - 3)y2 + (2x2 + 3x + 1)y - 5
Canonical form: (y2 + 2y)x2 + (5y2 + 3y)x + (-3y2 + y - 5)
(define p3
(make-polynomial-from-coeffs
'y
(list (make-polynomial-from-coeffs
'x
(list (make-integer 1)
(make-integer 5)
(make-integer -3)))
(make-polynomial-from-coeffs
'x
(list (make-integer 2)
(make-integer 3)
(make-integer 1)))
(make-integer -5))))
Polynomial p4: (5y2 + 2y - 1)x2 + (2y2 + y + 2)x - 3
Canonical form: (5y2 + 2y - 1)x2 + (2y2 + y + 2)x - 3
(define p4
(make-polynomial-from-coeffs
'x
(list (make-polynomial-from-coeffs
'y
(list (make-integer 5)
(make-integer 2)
(make-integer -1)))
(make-polynomial-from-coeffs
'y
(list (make-integer 2)
(make-integer 1)
(make-integer 2)))
(make-integer -3))))
Polynomial p5: (5x2 + 2x)y2 + (2x2 + x)y + (-x2 + 2x - 5)
Canonical form: (5y2 + 2y - 1)x2 + (2y2 + y + 2)x - 5
(define p5
(make-polynomial-from-coeffs
'y
(list (make-polynomial-from-coeffs
'x
(list (make-integer 5)
(make-integer 2)
zero))
(make-polynomial-from-coeffs
'x
(list (make-integer 2)
(make-integer 1)
zero))
(make-polynomial-from-coeffs
'x
(list (make-integer -1)
(make-integer 2)
(make-integer -5))))))
Polynomial p6: 42x0
Canonical form: 42unbound0 = 42
(define p6 (make-polynomial-from-coeffs 'x (list (make-integer 42))))
Note that
p4 and
p5 are the two polynomials shown in
the naïve approach to this exercise. Once we've completed this implementation we should be able to evaluate
(sub p4 p5) and get the result
(integer . 2). Note also
p6. This is a polynomial with only a single zero-order term. For such a polynomial the indeterminate is immaterial and so in canonical form its indeterminate is unbound (or it reduces to a constant if we
drop the polynomial).
Overview of the Steps
We can summarise the steps we'll use in order to convert a polynomial into a canonical form as follows:
- Expand: Recursively multiply out the terms in the polynomial whose coefficients are themselves polynomials. As part of this step we'll rearrange the indeterminates in each expanded term into canonical (i.e. alphanumeric) order. We'll also drop any zero-order terms as we go as this simplifies combining expanded terms in the next step. For example, the polynomial:
(10y2 + (10x2 + 6x + 4)y + 4)x2 + (10x2 + 6x + 4)x + 3
becomes:
10x2y2 + 10x4y + 6x3y + 4x2y + 4x2 + 10x3 + 6x2 + 4x + 3
- Rearrange: Iterate through the expanded terms and rearrange them such that the terms are sorted by decreasing order of the highest-priority indeterminate, then by decreasing order of the second-highest-priority indeterminate within that, and so on. We'll also combine expanded terms which have the same set of indeterminates and orders, adding their coefficients together, and dropping any whose coefficients become zero at this point. For example, the expansion:
10x2y2 + 10x4y + 6x3y + 4x2y + 4x2 + 10x3 + 6x2 + 4x + 3
becomes:
10x4y + 6x3y + 10x3 + 10x2y2 + 4x2y + 10x2 + 4x + 3
- Collapse: Iterate through the rearranged terms building a term-list for the highest-priority indeterminate and finally constructing a polynomial from this. The term-list is constructed by grouping together all terms for the highest-priority indeterminate that are of the same order, recursively processing these terms (with the highest-priority indeterminate stripped off) to produce coefficients, producing appropriate ordered terms from these and combining them. For example, the rearranged expansion:
10x4y + 6x3y + 10x3 + 10x2y2 + 4x2y + 10x2 + 4x + 3
becomes:
(10y)x4 + (6y + 10)x3 + (10y2 + 4y + 10)x2 + 4x + 3
Representing the Expansion
When we expand out a polynomial we produce an expression consisting of terms, each of which could be represented by a polynomial in its own right (a polynomial with only a single term, whose coefficient may be either a constant or another polynomial with a single term). So it initially seems as if we could just use our tagged polynomial representation to hold these terms and then use the existing polynomial addition to collapse the terms. Unfortunately, as we'll want to modify
coerce-and-call (see
here) so that it converts polynomials into canonical form before applying any operations we'd end up with an infinite recursion when we try to add the expanded terms together.
Instead of trying to deal with this via special-case code that prevents the recursion we'll produce a compressed intermediate representation of the expanded terms that we'll manipulate directly. We'll represent the expansion as a list, each element of which represents a single expanded term. Each expanded term will itself be a list, the first element of which will be a list of pairs of {indeterminate, order} ordered by indeterminate priority, and the second element of which will be the coefficient. For example, we'll represent the expansion 10x2y2 + 10x4y + 6x3y + 4x2y + 4x2 + 10x3 + 6x2 + 4x + 3 as:
((((x . 2) (y . 2)) integer . 10)
(((x . 4) (y . 1)) integer . 10)
(((x . 3) (y . 1)) integer . 6)
(((x . 2) (y . 1)) integer . 4)
(((x . 2)) integer . 4)
(((x . 3)) integer . 10)
(((x . 2)) integer . 6)
(((x . 1)) integer . 4)
(() integer . 3))
Note that the existing procedure for determining which indeterminate is of higher-priority, select-variable, deals with polynomial representations, not with the raw indeterminates themselves. Unfortunately we can't use this with our compressed representation. To address this we'll rename select-variable to select-variable-from-polys, as that's what it does, and then extract out a new implementation of select-variable that deals directly with the indeterminates:
(define (select-variable-from-polys p1 p2)
(select-variable (variable p1) (variable p2)))
(define (select-variable v1 v2)
(if (eq? v1 'unbound)
v2
v1))
We then update add-poly, mul-poly and div-poly to use select-variable-from-polys instead of select-variable and we're good to go!
Expanding Polynomials
Okay, so let's start with expanding out a polynomial to our intermediate representation. We know that this can be a recursive implementation, as we need to expand out any coefficient that is itself a polynomial. We also know that we'll be starting with the outer-most polynomial. Given this we can define the expansion process as iterating through all of the terms of the polynomial's term-list and, with each term:
- If the term's coefficient is itself a polynomial then recursively expand the coefficient. This produces an expansion using our intermediate representation.
- If the term's coefficient is not a polynomial then create an "expansion" in our intermediate representation that has a single expanded term consisting of an empty list of indeterminates and the coefficient. E.g. a term with the coefficient
(integer . 3) would expand out to ((() (integer . 3))).
- Iterate through the expansion generated for the coefficient and, for each element in that expansion, incorporate the
{indeterminate, order} pair corresponding to the polynomial and term being expanded. We need to remember that the indeterminates are to be kept in priority order in our intermediate representation. We also need to remember that a particular indeterminate may appear at different levels within the polynomial, in which case we need to update the indeterminate's order in the expanded term to be the sum of the orders involved. E.g. when expanding the representation of ((3x2)y3)x4 we need to spot that x appears not only as the indeterminate of the outermost polynomial, but also as the indeterminate of the innermost polynomial. As a result we need to generate the intermediate representation ((((x . 6) (y . 3)) integer . 3)) as opposed to ((((x . 2) (x . 4) (y . 3)) integer . 3))
- Finally, append the resulting expansion of this term onto the results of expanding the rest of the term-list.
Programmatically this can be expressed as:
(define (expand-poly p)
(expand-terms (variable p) (term-list p)))
(define (expand-terms var tl)
(if (empty-termlist? tl)
'()
(append (expand-term var (first-term tl))
(expand-terms var (rest-terms tl)))))
(define (expand-term var term)
(let* ((termcoeff (coeff term))
(termorder (order term))
(expanded (if (eq? (type-tag termcoeff) 'polynomial)
(expand-poly (contents termcoeff))
(list (cons '() termcoeff)))))
(if (= termorder 0)
expanded
(expand-by-indeterminate var termorder expanded))))
(define (expand-by-indeterminate var order expansion)
(if (null? expansion)
'()
(let ((head (car expansion)))
(cons (cons (accumulate-indeterminate var order (car head)) (cdr head))
(expand-by-indeterminate var order (cdr expansion))))))
(define (accumulate-indeterminate var termorder il)
(if (null? il)
(cons (cons var termorder) '())
(let* ((head (car il))
(head-var (car head)))
(cond ((same-variable? var head-var)
(cons (cons (select-variable var head-var)
(+ termorder (cdr head)))
(cdr il)))
((stringstring var) (symbol->string head-var))
(cons (cons var termorder) il))
(else (cons head
(accumulate-indeterminate var termorder (cdr il))))))))
The entry point to the expansion operation is expand-poly. This takes an untagged polynomial representation, splits out the indeterminate and term-list and invokes expand-termlist, which does the actual iteration through the terms in the term list. Note that we need to pass the indeterminate along with the term-list or term being expanded through to all of the procedures here as the representation of terms that we've been using contains only the order of the term and its coefficient; it does not contain the indeterminate.
The procedure expand-term encapsulates the logic for expanding a single term, examining the term's coefficient and then either recursively expanding it if it's a polynomial or building a single-term expansion consisting of no indeterminates and the coefficient if it's not. Once it's built the expansion of the term's coefficient it then multiplies each of the terms in the expansion by the the term's indeterminate and coefficient via expand-by-indeterminate. We use a minor optimization here - if the term is of order 0 then we skip this step as the net result of this multiplication is an unchanged expansion.
expand-by-indeterminate multiplies each term in the expansion by the indeterminate and order by iterating through the expansion and rebuilding each expansi (make-integer 2)))te, order} pairs via accumulate-indeterminate. This in turn iterates through the list of {indeterminate, order} pairs to locate the correct (sorted) location for the indeterminate being accumulated and either inserting it if it's missing or updating its order if it's present.
We can give this a quick spin by temporarily installing expand-poly:
(put 'expand-poly '(polynomial) expand-poly)
...and then creating a top-level procedure that allows us to apply this as a generic operation:
(define (expand-poly p)
(apply-generic 'expand-poly p))
We can remove these when we're done with the exercise, as expansion is really an internal detail of the polynomial package. But in the meantime, let's try it out on our test polynomials:
> (expand-poly p1)
((((x . 2)) integer . 5)
(((x . 3)) integer . 10)
(((x . 2)) integer . 6)
(((x . 1)) integer . 4)
(() integer . 3))
> (expand-poly p2)
((((x . 2) (y . 2)) integer . 10)
(((x . 4) (y . 1)) integer . 10)
(((x . 3) (y . 1)) integer . 6)
(((x . 2) (y . 1)) integer . 4)
(((x . 2)) integer . 4)
(((x . 3)) integer . 10)
(((x . 2)) integer . 6)
(((x . 1)) integer . 4)
(() integer . 3))
> (expand-poly p3)
((((x . 2) (y . 2)) integer . 1)
(((x . 1) (y . 2)) integer . 5)
(((y . 2)) integer . -3)
(((x . 2) (y . 1)) integer . 2)
(((x . 1) (y . 1)) integer . 3)
(((y . 1)) integer . 1)
(() integer . -5))
> (expand-poly p4)
((((x . 2) (y . 2)) integer . 5)
(((x . 2) (y . 1)) integer . 2)
(((x . 2)) integer . -1)
(((x . 1) (y . 2)) integer . 2)
(((x . 1) (y . 1)) integer . 1)
(((x . 1)) integer . 2)
(() integer . -3))
> (expand-poly p5)
((((x . 2) (y . 2)) integer . 5)
(((x . 1) (y . 2)) integer . 2)
(((x . 2) (y . 1)) integer . 2)
(((x . 1) (y . 1)) integer . 1)
(((x . 2)) integer . -1)
(((x . 1)) integer . 2)
(() integer . -5))
> (expand-poly p6)
((() integer . 42))
You'll note that, as we've yet to perform the rearrangement, the expanded terms are not ordered in a way that's useful to us and, in some cases, there are multiple expanded terms with the same set of {indeterminate, order} values. We'll sort this next...
Rearranging the Expansion
As noted
above, rearranging the expansion means sorting the expanded terms by decreasing order of the highest-priority indeterminate, then by decreasing order of the second-highest-priority indeterminate within that, and so on. And we perform the combining of expanded terms with the same set of
{indeterminate, order} values at this stage.
This can be achieved by iterating through the expansion one term at a time, inserting that term appropriately into the results of rearranging the remainder of the expansion. In the implementation below we perform this iteration in rearrange-expansion, calling out to add-to-expansion-in-order to perform the insertion. This in turn simply iterates through the existing expansion, comparing the {indeterminate, order} set of the term to be inserted with {indeterminate, order} set of the head of the expansion. What happens next depends upon the results of the comparison:
- If the term should precede the head in our desired ordering then it prepends the term onto the expansion, ending the iteration at this point.
- If the term should follow the head in our desired ordering then it adds the head onto the results of recursively inserting the term into the tail of the expansion.
- If the
{indeterminate, order} set of the term matches the {indeterminate, order} set of the head then we need to combine the term and the head into a single new term. To do this we add the coefficients of the term and the head together. If the result is zero then we can eliminate the combined term from the result altogether, and so we just return the tail of the expansion. Otherwise we generate a new combined term with the term's {indeterminate, order} set and the results of the addition as the coefficient. This is prepended onto the expansion. Either way the iteration stops at this point.
The comparison of {indeterminate, order} sets is encapsulated in compare-expanded-vars. We follow the convention followed in many programming languages when comparing two values: return a negative value if the first value precedes the second value in the ordering, return zero if they are equivalent, and return a positive value if the first value should follow the second value in the ordering. As we're comparing two ordered sets of {indeterminate, order} values we simply iterate through the lists in parallel, looking for the first point at which the {indeterminate, order} values differ. When we find this point we decide which comes first based upon which has the principal variable of the two or, if they are the same value, which has the higher order. If we reach the end of either list during this process then we select the list which hasn't ended as the first in the ordering. If they've both ended then the two sets are identical.
Here's the code:
(define (rearrange-expansion expansion)
(if (null? expansion)
'()
(add-to-expansion-in-order (car expansion)
(rearrange-expansion (cdr expansion)))))
(define (add-to-expansion-in-order component expansion)
(if (null? expansion)
(cons component expansion)
(let* ((var (car component))
(compare (compare-expanded-vars var (caar expansion))))
(cond ((< compare 0)
(cons component expansion))
((> compare 0)
(cons (car expansion)
(add-to-expansion-in-order component (cdr expansion))))
(else
(let ((combined (add (cdr component) (cdar expansion))))
(if (=zero? combined)
(cdr expansion)
(cons (cons var combined) (cdr expansion)))))))))
(define (compare-expanded-vars vars1 vars2)
(cond ((null? vars1) (if (null? vars2) 0 1))
((null? vars2) -1)
((same-variable? (caar vars1) (caar vars2))
(let ((order-diff (- (cdar vars2) (cdar vars1))))
(if (= order-diff 0)
(compare-expanded-vars (cdr vars1) (cdr vars2))
order-diff)))
(else (let* ((var1 (caar vars1))
(var2 (caar vars2))
(principal (select-principal-variable var1 var2)))
(if (same-variable? principal var1)
-1
1)))))
Let's give this a quick test too. We follow a similar process, temporarily installing rearrange-expansion and a corresponding top-level procedure. Note that as this deals with an untagged value we'll just install it under the 'polynomial type tag, like the constructor, rather than under a type list, and access the table directly using get in the top-level procedure. Here's the installation:
(put 'rearrange-expansion 'polynomial rearrange-expansion)
...and, here's the top-level procedure:
(define (rearrange-expansion e)
((get 'rearrange-expansion 'polynomial) e))
Here's what happens when we apply it to the results of expanding our test polynomials:
> (rearrange-expansion (expand-poly p1))
((((x . 3)) integer . 10)
(((x . 2)) integer . 11)
(((x . 1)) integer . 4)
(() integer . 3))
> (rearrange-expansion (expand-poly p2))
((((x . 4) (y . 1)) integer . 10)
(((x . 3) (y . 1)) integer . 6)
(((x . 3)) integer . 10)
(((x . 2) (y . 2)) integer . 10)
(((x . 2) (y . 1)) integer . 4)
(((x . 2)) integer . 10)
(((x . 1)) integer . 4)
(() integer . 3))
> (rearrange-expansion (expand-poly p3))
((((x . 2) (y . 2)) integer . 1)
(((x . 2) (y . 1)) integer . 2)
(((x . 1) (y . 2)) integer . 5)
(((x . 1) (y . 1)) integer . 3)
(((y . 2)) integer . -3)
(((y . 1)) integer . 1)
(() integer . -5))
> (rearrange-expansion (expand-poly p4))
((((x . 2) (y . 2)) integer . 5)
(((x . 2) (y . 1)) integer . 2)
(((x . 2)) integer . -1)
(((x . 1) (y . 2)) integer . 2)
(((x . 1) (y . 1)) integer . 1)
(((x . 1)) integer . 2)
(() integer . -3))
> (rearrange-expansion (expand-poly p5))
((((x . 2) (y . 2)) integer . 5)
(((x . 2) (y . 1)) integer . 2)
(((x . 2)) integer . -1)
(((x . 1) (y . 2)) integer . 2)
(((x . 1) (y . 1)) integer . 1)
(((x . 1)) integer . 2)
(() integer . -5))
> (rearrange-expansion (expand-poly p6))
((() integer . 42))
All's looking good here. The terms are ordered as we need them in order to perform a simple collapse. Note in particular that the rearranged expansions of
p1 and
p2 differ only in their last terms, which are -3 and -5 respectively (and (-3) - (-5) = 2, so this looks very promising).
Compressing the Rearranged Expansion
All that remains in converting to canonical form is to collapse the rearranged expansion. The expansion is now ordered so that we can iterate through it, group together all terms of the same order in the principal variable, recursively collapse those to give a coefficient for a term of that order, and create a polynomial in the highest-priority indeterminate using the term-list that results from the iteration. So it should be straightforward then...
Our top-level procedure for performing the collapse basically has to identify the highest-priority indeterminate, collapse the expanded terms into a term-list and then create a polynomial from this. There are a couple of cases that need special treatment here:
- If the expanded terms list is empty then we want to create an "empty" polynomial. To do this we'll directly create a polynomial with an
'unbound indeterminate and a zero-order term with the coefficient of zero.
- If the expansion consists of a single expanded term which has an empty set of
{indeterminate, order} values then the expansion corresponds to a polynomial with only a zero-order term. Any polynomial with only a zero-order term is effectively a constant, so the indeterminate is immaterial (which is just as well as we don't know it!). So, similar to the previous case, we'll create a polynomial with an 'unbound indeterminate and only a zero-order term. However, in this case we'll set the coefficient to the coefficient of the expanded term.
Here's the top-level procedure, which I've called collapse-expansion:
(define (collapse-expansion expanded)
(cond ((null? expanded) (make-from-coeffs 'unbound (list zero)))
((null? (caar expanded)) (make-from-coeffs 'unbound (list (cdar expanded))))
(else (let* ((first (car expanded))
(principal (caaar first))
(start-order (cdaar first))
(collapsed-tl (to-collapsed-term-list expanded
principal
start-order
'())))
(make-poly principal collapsed-tl)))))
You'll note that we delegate the building of the collapsed term-list to another procedure, to-collapsed-term-list, which we'll move onto now. You'll also note that our procedure for doing this takes four operands:
- The list of expanded terms to be processed. We'll iterate through this list, grouping together all expanded terms for the highest-priority indeterminate that are of the same order.
- The indeterminate of the polynomial we're going to create with the collapsed term-list. We need this as not every expanded term may contain the highest-priority indeterminate. Such expanded terms, if present, will be at the end of the list and need to be grouped together to produce the coefficient for the zero-order term in the term-list.
- The current order we're grouping together. Initially this is the order associated with the highest-priority indeterminate in the first expanded term, which will be the highest order we'll encounter for this indeterminate. As we reach the start of each group we'll update this to be the order associated with the highest-priority indeterminate in the first expanded term in that group.
- A list in which to group (or accumulate) the expanded terms that have the same order for the highest-priority indeterminate. So long as the first expanded term in the remaining expansion belongs to the group we append it onto this accumulator. We strip off the
{indeterminate, order} for the highest-priority indeterminate prior to doing this so that the expanded terms in our accumulated group correspond directly to the expansion of the coefficient of the current order's term. When we reach the point where we encounter the start of the next group we then construct a term with a coefficient built by collapsing this group and add it onto the term-list produced by the remainder of the expansion. Obviously we reset the accumulator at this point.
Okay, so here are the cases we'll encounter and how we'll deal with them:
- If we've exhausted the expansion and there's nothing in the current group to convert into a term then we produce an empty term-list.
- If we've exhausted the expansion but the current group isn't empty then we collapse the current group, use this as a coefficient in a term with the order of the group and add this term to an empty term-list.
- If we're currently processing a non-zero term for the indeterminate of the polynomial we're constructing and we reach an expanded term which either has no list of
{indeterminate, order} values, or for which the first indeterminate does not match the indeterminate of the polynomial we're constructing then we've found the start of the zero-order term's coefficients. We create a term for the current group as above, which we append onto the results of collapsing the remainder of the expansion. Note that in this case we know that the remainder forms the zero-order term for the term-list and none of the expansions have terms in the polynomial's indeterminate so we can immediately group the remainder of the expansion together to construct a coefficient with without having to iterate it.
- The flip side of the previous case: if we're currently processing a zero term for the indeterminate of the polynomial we're constructing and we reach an expanded term which either has no list of
{indeterminate, order} values, or for which the first indeterminate does not match the indeterminate of the polynomial we're constructing then we're in the zero term's group already. We simply append the remainder of the expansion directly onto the group and construct a term-list containing the zero-term by collapsing the group.
- If we're currently processing a non-zero term for the indeterminate of the polynomial we're constructing and we reach an expanded term which has a different order for the indeterminate then we've found the start of next group. As above we create a term which we append onto the results of collapsing the remainder of the expansion. In this case, however, we can't short-cut the collapsing of the remaining expansion. We update the current order to be the order associated with the highest-priority indeterminate in the first expanded term in the expansion, reset the group and recursively process the expansion.
- Finally, if no other case has dealt with the head of the expansion then we're in the middle of a group, so we append the expanded term onto the group (stripping off the highest-priority indeterminate) and move on to processing the remainder of the expansion after this.
If you've followed all that then you'll appreciate it's not overly straightforward. I'm not overly happy with my implementation of this, but for what it's worth, here it is. You'll note the use of caaaar and cdaaar here. The former gets the indeterminate associated with the first expanded term in the expansion, while the latter gets the order associated with the first expanded term in the expansion. Ouch!
(define (to-collapsed-term-list expanded principal current-order current-group)
(cond ((and (null? expanded) (null? current-group)) (the-empty-termlist))
((null? expanded)
(adjoin-term (make-term current-order
(collapse-sub-expansion current-group))
(the-empty-termlist)))
((and (not (= current-order 0))
(or (null? (caar expanded))
(not (eq? principal (caaaar expanded)))))
(adjoin-term (make-term current-order
(collapse-sub-expansion current-group))
(to-collapsed-term-list '() principal 0 expanded)))
((or (null? (caar expanded))
(not (eq? principal (caaaar expanded))))
(to-collapsed-term-list '()
principal
current-order
(append current-group expanded)))
((and (not (= current-order 0))
(not (= current-order (cdaaar expanded))))
(adjoin-term (make-term current-order
(collapse-sub-expansion current-group))
(to-collapsed-term-list expanded
principal
(cdaaar expanded)
'())))
(else
(to-collapsed-term-list (cdr expanded)
principal
current-order
(append current-group
(list (cons (cdaar expanded)
(cdar expanded))))))))
Also, if you were really paying close attention, you'll have noted that we're not using collapse-expansion to collapse the groups, but a new procedure, collapse-sub-expansion. The two procedures are similar-ish to each other. They both have three identical cases to deal with: an empty expansion; a single element in the expansion with no {indeterminate, order} values; and an expansion in which at least the first expanded term has {indeterminate, order} values. The procedures have to deal with them slightly differently though:
- We noted already that
collapse-expansion generates a polynomial regardless of the expansion passed to it. This is necessary as the collapsed expansion is going to be passed to an arithmetic operation that is internal to the polynomial package. As they're internal arithmetic operations type coercion will not be applied to the arguments and our arithmetic operations require polynomial arguments.
- In the case of
collapse-sub-expansion the result will be used to form the coefficient of a collapsed term. As a result we want this to be expressed in as simple a form as possible. So in the first two cases, rather than generating polynomials in 'unbound with a single zero-order term, we'll generate a non-polynomial value. I.e. zero in the first case, and the coefficient of the expanded term in the second case. We also have to deal with the third case slightly differently: we have to tag it as a polynomial. This is necessary as coefficients of terms must be properly tagged types.
Here's collapse-sub-expansion:
(define (collapse-sub-expansion expanded)
(cond ((null? expanded) zero)
((null? (caar expanded)) (cdar expanded))
(else (let* ((first (car expanded))
(principal (caaar first))
(start-order (cdaar first))
(collapsed-tl (to-collapsed-term-list expanded
principal
start-order
'())))
(tag (make-poly principal collapsed-tl))))))
To put this to the test, let's put another piece of the puzzle into place. We'll need to be able to convert a given polynomial into canonical form within the polynomial package, so let's string together the expand, rearrange and collapse steps from above into a single procedure which produces an untagged polynomial:
(define (to-canonical-poly p)
(collapse-expansion (rearrange-expansion (expand-poly p))))
We can then expose this procedure externally by installing it such that it tags the produced polynomials and then drops them to reduce them to simplest form:
(put 'to-canonical '(polynomial)
(lambda (p) (drop (tag (to-canonical-poly p)))))
...and then create a top-level procedure that allows us to apply this as a generic operation:
(define (to-canonical p)
(apply-generic 'to-canonical p))
Finally we can apply this to our test polynomials:
> (to-canonical p1)
(polynomial x dense-terms (integer . 10) (integer . 11) (integer . 4) (integer . 3))
> (to-canonical p2)
(polynomial x
dense-terms
(polynomial y
sparse-terms
(term 1 (integer . 10)))
(polynomial y
dense-terms
(integer . 6)
(integer . 10))
(polynomial y
dense-terms
(integer . 10)
(integer . 4)
(integer . 10))
(integer . 4)
(integer . 3))
> (to-canonical p3)
(polynomial x
dense-terms
(polynomial y
sparse-terms
(term 2 (integer . 1))
(term 1 (integer . 2)))
(polynomial y
sparse-terms
(term 2 (integer . 5))
(term 1 (integer . 3)))
(polynomial y
dense-terms
(integer . -3)
(integer . 1)
(integer . -5)))
> (to-canonical p4)
(polynomial x
dense-terms
(polynomial y
dense-terms
(integer . 5)
(integer . 2)
(integer . -1))
(polynomial y
dense-terms
(integer . 2)
(integer . 1)
(integer . 2))
(integer . -3))
> (to-canonical p5)
(polynomial x
dense-terms
(polynomial y
dense-terms
(integer . 5)
(integer . 2)
(integer . -1))
(polynomial y
dense-terms
(integer . 2)
(integer . 1)
(integer . 2))
(integer . -5))
> (to-canonical p6)
(integer . 42)
These all correspond to the canonical forms listed for the test polynomials given
above, so we're nearly there!
Integrating into the System
The final piece of the puzzle is to add automatic conversion to canonical form to our system. We already have a procedure,
coerce-and-call which ensures that two polynomials are expressed in the same indeterminate before applying the operation which we used to implement
the naïve solution. To add conversion to canonical form to this we simply extend the
let* statement so that it firstly converts the two polynomials to canonical form. Note that we still need to ensure they're both expressed in the same indeterminate prior to applying the operation after we've converted them to canonical form!
Here's the updated coerce-and-call:
(define (coerce-and-call p1 p2 op)
(let* ((canonical-p1 (to-canonical-poly p1))
(canonical-p2 (to-canonical-poly p2))
(principal (select-principal-variable (variable canonical-p1)
(variable canonical-p2)))
(new-p1 (express-in principal canonical-p1))
(new-p2 (express-in principal canonical-p2)))
(op new-p1 new-p2)))
Finally, let's do some sums:
> (add p1 p2)
(polynomial x
dense-terms
(polynomial y
sparse-terms
(term 1 (integer . 10)))
(polynomial y
dense-terms
(integer . 6)
(integer . 20))
(polynomial y
dense-terms
(integer . 10)
(integer . 4)
(integer . 21))
(integer . 8)
(integer . 6))
> (add p4 p5)
(polynomial x
dense-terms
(polynomial y
dense-terms
(integer . 10)
(integer . 4)
(integer . -2))
(polynomial y
dense-terms
(integer . 4)
(integer . 2)
(integer . 4))
(integer . -8))
> (sub p4 p5)
(integer . 2)
> (add p6 p3)
(polynomial x
dense-terms
(polynomial y
sparse-terms
(term 2 (integer . 1))
(term 1 (integer . 2)))
(polynomial y
sparse-terms
(term 2 (integer . 5))
(term 1 (integer . 3)))
(polynomial y
dense-terms
(integer . -3)
(integer . 1)
(integer . 37)))
> (add p6 p6)
(integer . 84)
Cool - looks like we have a working solution! And phew! That took a while! Now onto exercise 2.93...
