SICP 読み (92) 2.5.3 例: 記号代数
全係数を最大公約数で割る (その 2)
あ、pseudoremainder-terms 呼び出しを wrap すりゃ良いの??
(define (gcd-terms L1 L2)
(if (empty-termlist? L2)
L1
(gcd-terms L2 (div-by-gcd (pseudoremainder-terms L1 L2)))))ってカンジ??
多分置き換えなソレを見るに上記で問題無いはず。(アマ
リストの中の gcd を得る手続きってどうすりゃ良いのか。
(define (gcd-list l)
(if (null? (cdr l))
(car l)
(gcd (car l) (gcd-list (cdr l)))))なんとなく動いている感じ。
div-by-gcd の実装は以下のような感じか。
(define (div-by-gcd L)
(define (get-coeff-gcd L)
(let f ((L L) (result (coeff (car L))))
(if (null? L)
result
(f (cdr L) (gcd result (coeff (car L)))))))
(let ((n (get-coeff-gcd L)))
(let f ((L L) (result '()))
(if (null? L)
result
(let ((top (car L)))
(f (cdr L) (cons (make-term (order top)
(/ (coeff top) n))
result)))))))で、試験してみたんですが動かない。ループしてる感じ。体調不良により中断。次の日になってよくよく見てみりゃ、gcd-terms ん中でやっちゃ駄目だろ、と。恥ずかしいんですが、以下のような実装になってマシタ。(とほほほ
(define (gcd-terms L1 L2)
(if (empty-termlist? L2)
L1
(div-by-gcd (gcd-terms L2 (pseudoremainder-terms L1 L2)))))で、以下の場所な形で修正。
(define (gcd-poly p1 p2)
(if (same-variable? (variable p1) (variable p2))
(make-poly (variable p1)
(div-by-gcd (gcd-terms (term-list p1)
(term-list p2))))
(error "Polys not in same var --- GCD-POLY"
(list p1 p2)))
)無論、gcd-terms ん中では div-by-gcd は呼ばない。全部終わって戻ってきてからやんねぇと駄目だろ。
で、試験してみたんですが NG。リストが逆になっている。(駄目
修正した div-by-gcd を以下に。
(define (div-by-gcd L)
(define (get-coeff-gcd L)
(let f ((L L) (result (coeff (car L))))
(if (null? L)
result
(f (cdr L) (gcd result (coeff (car L)))))))
(let ((n (get-coeff-gcd L)))
(let f ((L L) (result '()))
(if (null? L)
result
(let ((top (car L)))
(f (cdr L) (append result
(list (make-term (order top)
(/ (coeff top) n))))))))))どうも cons を適当に使ってしまう悪い癖があるなぁ。
このケースだと名前付き let は使わない方がわかりやすそげではある。それだと cons 使えて視覚的にも直感的になる、というか。
この状態で以下の試験にパスしています。
("2-95,96"
(setup (lambda ()
(install-rational-package)
(install-scheme-number-package)
(install-polynomial-package)))
("not equall"
(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)))
(assert-equal q1
'(polynomial x (4 11) (3 -22) (2 18) (1 -14) (0 7)))
(assert-equal q2
'(polynomial x (3 13) (2 -21) (1 3) (0 5)))
; (assert-not-equal p1 (greatest-common-divisor q1 q2))))
(assert-equal p1 (greatest-common-divisor q1 q2))))
)
("pseudoremainder-terms"
(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)))
; (assert-equal '(polynomial x (2 18954) (1 -37908) (0 18954))
; (greatest-common-divisor q1 q2))))
(assert-not-equal '(polynomial x (2 18954) (1 -37908) (0 18954))
(greatest-common-divisor q1 q2))))
)
)2 章終わりまであと一問。
追記
テキスト見るとやっぱり gcd-terms に、と書いてある。しかも昨晩のエントリでも (多分忘れないように) gcd-terms に、とある。悔しいので実装してみた。以下、変更部分のみ。
(define (gcd-poly p1 p2)
(if (same-variable? (variable p1) (variable p2))
(make-poly (variable p1)
(gcd-terms (term-list p1)
(term-list p2)))
(error "Polys not in same var --- GCD-POLY"
(list p1 p2)))
)gcd-poly は元に戻して
(define (gcd-terms L1 L2)
(define (gcd-terms-iter L1 L2)
(if (empty-termlist? L2)
L1
(gcd-terms L2 (pseudoremainder-terms L1 L2))))
(div-by-gcd (gcd-terms-iter L1 L2)))gcd-terms の中で wrap した。よく考えりゃ簡単じゃん、みたいな??
# ってか、ループの中に wrap カマす方が駄目スギ
あるいは、div-by-gcd を修正。
(define (div-by-gcd L)
(define (get-coeff-gcd L)
(let f ((L L) (result (coeff (car L))))
(if (null? L)
result
(f (cdr L) (gcd result (coeff (car L)))))))
(define (div-by-gcd-iter L n)
(if (null? L)
'()
(let ((top (car L)))
(cons (make-term (order top) (/ (coeff top) n))
(div-by-gcd-iter (cdr L) n)))))
(div-by-gcd-iter L (get-coeff-gcd L)))これはこれでどうなんだろう、という感じもするなぁ。
