Exercise 2.97. a. Implement this algorithm as a procedure reduce-terms that takes two term lists n and d as arguments and returns a list nn, dd, which are n and d reduced to lowest terms via the algorithm given above. Also write a procedure reduce-poly, analogous to add-poly, that checks to see if the two polys have the same variable. If so, reduce-poly strips off the variable and passes the problem to reduce-terms, then reattaches the variable to the two term lists supplied by reduce-terms.
b. Define a procedure analogous to reduce-terms that does what the original make-rat did for integers:
(define (reduce-integers n d)
(let ((g (gcd n d)))
(list (/ n g) (/ d g))))
and define reduce as a generic operation that calls apply-generic to dispatch to either reduce-poly (for polynomial arguments) or reduce-integers (for scheme-number arguments). You can now easily make the rational-arithmetic package reduce fractions to lowest terms by having make-rat call reduce before combining the given numerator and denominator to form a rational number. The system now handles rational expressions in either integers or polynomials. To test your program, try the example at the beginning of this extended exercise:
(define p1 (make-polynomial 'x '((1 1)(0 1))))
(define p2 (make-polynomial 'x '((3 1)(0 -1))))
(define p3 (make-polynomial 'x '((1 1))))
(define p4 (make-polynomial 'x '((2 1)(0 -1))))
(define rf1 (make-rational p1 p2))
(define rf2 (make-rational p3 p4))
(add rf1 rf2)
See if you get the correct answer, correctly reduced to lowest terms.
实现多项式约分
按照相关的步骤，我们可以如下写出 reduce-terms：
(define (reduce-terms n d)
(define (integerize factor L)
(map
(lambda (x)
(make-term (order x) (mul factor (coeff x)))) L))
(define (gcd-factor terms)
(apply gcd (map (lambda (x) (coeff x)) terms)))
(define (div-factor terms factor)
(map (lambda (term)
(make-term (order term) (div (coeff term) factor)))
terms))
(let* ((g (gcd-terms n d))
(c (coeff (first-term g)))
(o2 (order (first-term g)))
(o1 (max (order (first-term n))
(order (first-term d))))
(factor (expt c (+ 1 o1 (- 0 o2))))
(integerizing-n (integerize factor n))
(integerizing-d (integerize factor d)))
(let* ((result-n (car (div-terms integerizing-n g)))
; NOTE: use car to fetch the divisor
(result-d (car (div-terms integerizing-d g)))
(coeff-gcd (gcd-factor (append result-n result-d))))
(list (div-factor result-n coeff-gcd)
(div-factor result-d coeff-gcd)))))
其步骤遵循这样的过程：
- Compute the GCD of the numerator and denominator, using the version of gcd-terms from exercise 2.96.
- When you obtain the GCD, multiply both numerator and denominator by the same integerizing factor before dividing through by the GCD, so that division by the GCD will not introduce any noninteger coefficients. As the factor you can use the leading coefficient of the GCD raised to the power 1 + O1 - O2, where O2 is the order of the GCD and O1 is the maximum of the orders of the numerator and denominator. This will ensure that dividing the numerator and denominator by the GCD will not introduce any fractions.
- The result of this operation will be a numerator and denominator with integer coefficients. The coefficients will normally be very large because of all of the integerizing factors, so the last step is to remove the redundant factors by computing the (integer) greatest common divisor of all the coefficients of the numerator and the denominator and dividing through by this factor.
然后是 reduce-poly，与 add-poly 非常相似：
(define (reduce-poly p1 p2)
(if (same-variable? (variable p1) (variable p2))
(let ((g (reduce-terms (term-list p1)
(term-list p2))))
(list
(make-poly (variable p1) (car g))
(make-poly (variable p1) (cadr g))))
(error "Polys not in same var -- REDUCE-POLY"
(list p1 p2))))多项式分数约分的测试
rf1 与 rf2 以及它们的和的最简形式为：
我们可以非常简单的直接把 reduce-poly 放到全局表中（导出到包外部使用）。这样就可以在分数包中使用泛型的 reduce 了。
(put 'reduce '(polynomial polynomial)
(lambda (p1 p2)
(let ((result (reduce-poly p1 p2)))
(list (tag (car result))
(tag (cadr result))))))泛型的 reduce 与其他几个泛型的操作没有区别：
(define (reduce-integers n d)
(let ((g (gcd n d)))
(list (/ n g) (/ d g))))
(put 'reduce '(scheme-number scheme-number)
(lambda (n d)
(reduce-integers n d)))
(define (reduce n d)
(apply-generic 'reduce n d))
在分数包中，我们更改 make-rat：
(define (make-rat n d)
(reduce n d))最终我们的系统就完成了。相比起在 练习 2.93 中实现的多项式分数，现在的多项式分数已经可以处理约分的情况了：
(load "../testframe.scm")
(let ((p1 (make-polynomial 'x '((2 1) (1 -2) (0 1))))
(p2 (make-polynomial 'x '((2 11) (0 7))))
(p3 (make-polynomial 'x '((1 13) (0 5)))))
(let ((q1 (mul p1 p2))
(q2 (mul p1 p3)))
(assertequal? (reduce q1 q2)
(list p2 p3))))
(let ((p1 (make-polynomial 'x '((1 1)(0 1))))
(p2 (make-polynomial 'x '((3 1)(0 -1))))
(p3 (make-polynomial 'x '((1 1))))
(p4 (make-polynomial 'x '((2 1)(0 -1)))))
(let ((rf1 (make-rational p1 p2))
(rf2 (make-rational p3 p4)))
(asserttrue (or (equal? (add rf1 rf2)
(make-rational
(make-polynomial 'x '((3 1) (2 2) (1 3) (0 1)))
(make-polynomial 'x '((4 1) (3 1) (1 -1) (0 -1)))))
(equal? (add rf1 rf2)
(make-rational
(make-polynomial 'x '((3 -1) (2 -2) (1 -3) (0 -1)))
(make-polynomial 'x '((4 -1) (3 -1) (1 1) (0 1)))))))))
; previous: (rational (polynomial x (4 1) (3 1) (2 1) (1 -2) (0 -1)) (polynomial x (5 1) (3 -1) (2 -1) (0 1)))
; now: (rational (polynomial x (3 -1) (2 -2) (1 -3) (0 -1)) (polynomial x (4 -1) (3 -1) (1 1) (0 1)))