2006/03/05

こういう働きをするフィルタがほしい。
((a 1) (b 2) (a 3) (c 1) (d 0) (a 4) (c 5) (b 6))

((a 8) (b 8) (c 6) (d 0))

ようするに、同じタグを持つ要素をまとめ(この場合は加算)させたい。その心は、タグ=>多項式の各項の変数、要素=>多項式の各項の係数とみなして、リスト全体で多項式を定義すれば、こういうフィルタを使って多変数多項式の代数演算システムが構築できるはず。つまり、SICPのex.2.92が解けるはず。
(define (M-filter equ? proc ls)
(let ((L (merge-if-equ-with-car equ? proc ls)))
(if (null? (cdr L))
(merge-if-equ-with-car equ? proc L)
(cons (car L)
(M-filter equ? proc (cdr L))))))

(define (merge-if-equ-with-car equ? proc ls)
(letrec
((head (car ls))
(foot
(let M ((a (car ls))
(rest (cdr ls)))
(cond ((null? rest)
'())
((equ? a (car rest))
(let ((a (proc a (car rest))))
(set! head a)
(M a (cdr rest))))
(else
(cons (car rest)
(M a (cdr rest))))))))
(cons head foot)))
うまくないなあ。つーか、このex.2.92の時点で set! を使うのは、問題の回答としていけないような気もする。でも、"The Seasoned Schemer" の 16th Commmandment(set!はletで束縛している名前にだけは使ってもいい)は破ってないので、よしとすることにしよう。ちっとも先に進まないし。
(M-filter (lambda (a b) (equal? (car a) (car b)))
(lambda (a b) (list (car a) (+ (cadr a) (cadr b))))
'((x 1) (xy 2) (x 3) (y 4) (z 5) (y 6) (xy 5)))

=>((x 4) (xy 7) (y 10) (z 5))

このリストをもってして 4x + 7xy + 10y + 5z を定義するということ。多項式どうしの加算は append して M-filter、積は car 同士および cadr 同士かけたものを combination して M-filter すればいいっしょ。あとは、x^2*y と y*x^2 とかがちゃんと #t になるように変数と equ? を定義して、それらをまとめて代数演算パッケージと連係するようにパッケージ化するだけ。


やあ、ようやく佐川急便が来たよ。これで会社にいける。
佐川のWebにある「お荷物問い合わせ24時間サービス」では、今ごろ大阪から札幌に転送されていることになっている荷物なんだけど、なんとか無事に届いたね。

No comments :