SICP 読み (86) 2.5.3 例: 記号代数
問題 2.90 の実装と試験を以下に。
lib/2.5.3.scm
(require "2.5.1")
(define (install-term-package)
(define (make-term order coeff) (list order coeff))
(define (order term) (car term))
(define (coeff term) (cadr term))
(define (tag t) (attach-tag 'term t))
(put 'make 'term
(lambda (order coeff) (tag (make-term order coeff))))
(put 'order '(term)
(lambda (t) (order t)))
(put 'coeff '(term)
(lambda (t) (coeff t)))
'done)
(define (make-term order coeff)
((get 'make 'term) order coeff))
(define (order term) (apply-generic 'order term))
(define (coeff term) (apply-generic 'coeff term))
(define (install-sparse-termlist)
(define (first-term term-list)
(if (null? term-list)
term-list
(make-term (- (length term-list) 1) (car term-list))))
(define (rest-terms term-list) (cdr term-list))
(define (empty-termlist? term-list)
(define (all-zero? term-list)
(cond ((null? term-list) #t)
((not (=zero? (car term-list))) #f)
(else
(all-zero? (cdr term-list))))
)
(or (null? term-list) (all-zero? term-list)))
(define (the-empty-termlist) '())
(define (adjoin-term term-list)
(lambda (term)
(let f ((term-list term-list))
(if (> (order term) (length term-list))
(f (cons 0 term-list))
(tag (cons (coeff term) term-list))))))
(define (tag t) (attach-tag 'sparse t))
(put 'first-term '(sparse)
(lambda (t) (first-term t)))
(put 'rest-terms '(sparse)
(lambda (t) (tag (rest-terms t))))
(put 'empty-termlist? '(sparse)
(lambda (t) (empty-termlist? t)))
(put 'the-empty-termlist 'sparse
(lambda () (tag (the-empty-termlist))))
(put 'adjoin-term '(sparse)
(lambda (t) (adjoin-term t)))
'done)
(define (install-dense-termlist)
(define (adjoin-term term-list)
(lambda (term)
(if (=zero? (coeff term))
(tag term-list)
(tag (cons (list (order term) (coeff term)) term-list)))))
(define (first-term term-list) (make-term (car (car term-list))
(cadr (car term-list))))
(define (rest-terms term-list) (cdr term-list))
(define (the-empty-termlist) '())
(define (empty-termlist? term-list) (null? term-list))
(define (tag t) (attach-tag 'dense t))
(put 'first-term '(dense)
(lambda (t) (first-term t)))
(put 'rest-terms '(dense)
(lambda (t) (tag (rest-terms t))))
(put 'empty-termlist? '(dense)
(lambda (t) (empty-termlist? t)))
(put 'the-empty-termlist 'dense
(lambda () (tag (the-empty-termlist))))
(put 'adjoin-term '(dense)
(lambda (t) (adjoin-term t)))
'done)
(define (install-polynomial-package)
(define (first-term term-list) (apply-generic 'first-term term-list))
(define (rest-terms term-list) (apply-generic 'rest-terms term-list))
(define (empty-termlist? term-list)
(apply-generic 'empty-termlist? term-list))
(define (adjoin-term term-list) (apply-generic 'adjoin-term term-list))
(define (sparse-empty-termlist) ((get 'the-empty-termlist 'sparse)))
(define (make-poly variable term-list)
(cons variable term-list))
(define (variable p) (car p))
(define (term-list p) (cdr p))
(define (variable? x) (symbol? x))
(define (same-variable? v1 v2)
(and (variable? v1) (variable? v2) (eq? v1 v2)))
(define (add-poly p1 p2)
(if (same-variable? (variable p1) (variable p2))
(make-poly (variable p1)
(add-terms (term-list p1)
(term-list p2)))
(error "Polys not in same var --- ADD-POLY"
(list p1 p2))))
(define (add-terms L1 L2)
(cond ((empty-termlist? L1) L2)
((empty-termlist? L2) L1)
(else
(let ((t1 (first-term L1)) (t2 (first-term L2)))
(cond ((> (order t1) (order t2))
((adjoin-term (add-terms (rest-terms L1) L2)) t1))
((< (order t1) (order t2))
((adjoin-term (add-terms L1 (rest-terms L2))) t2))
(else
((adjoin-term (add-terms (rest-terms L1)
(rest-terms L2)))
(make-term (order t1)
(add (coeff t1) (coeff t2))))))))))
(define (mul-poly p1 p2)
(if (same-variable? (variable p1) (variable p2))
(make-poly (variable p1)
(mul-terms (term-list p1)
(term-list p2)))
(error "Polys not in same var --- MUL-POLY"
(list p1 p2))))
(define (mul-terms L1 L2)
(if (empty-termlist? L1)
L1
(add-terms (mul-term-by-all-terms (first-term L1) L2)
(mul-terms (rest-terms L1) L2))))
(define (mul-term-by-all-terms t1 L)
(if (empty-termlist? L)
L
(let ((t2 (first-term L)))
((adjoin-term (mul-term-by-all-terms t1 (rest-terms L)))
(make-term (+ (order t1) (order t2))
(mul (coeff t1) (coeff t2)))))))
(define (neg-poly p)
(make-poly (variable p)
(neg-terms (term-list p))))
(define (neg-terms L)
(if (empty-termlist? L)
L
(let ((t (first-term L)))
((adjoin-term (neg-terms (rest-terms L)))
(make-term (order t) (- (coeff t))))))
)
(define (tag p) (attach-tag 'polynomial p))
(put '=zero? '(polynomial)
(lambda (p) (empty-termlist? (term-list p))))
(put 'neg '(polynomial)
(lambda (p) (tag (neg-poly p))))
(put 'add '(polynomial polynomial)
(lambda (p1 p2) (tag (add-poly p1 p2))))
(put 'mul '(polynomial polynomial)
(lambda (p1 p2) (tag (mul-poly p1 p2))))
(put 'make 'polynomial
(lambda (var terms f) (tag (make-poly var (attach-tag f terms)))))
'done)
(define (make-sparse-polynomial var terms)
((get 'make 'polynomial) var terms 'sparse))
(define (make-dense-polynomial var terms)
((get 'make 'polynomial) var terms 'dense))
(define (neg x) (apply-generic 'neg x))lib/2.5.1.scm
(define (assoc key records)
(cond ((null? records) #f)
((equal? key (caar records)) (car records))
(else (assoc key (cdr records)))))
(define (make-table)
(let ((local-table (list '*table*)))
(define (lookup key-1 key-2)
(let ((subtable (assoc key-1 (cdr local-table))))
(if subtable
(let ((record (assoc key-2 (cdr subtable))))
(if record
(cdr record)
#f))
#f)))
(define (insert! key-1 key-2 value)
(let ((subtable (assoc key-1 (cdr local-table))))
(if subtable
(let ((record (assoc key-2 (cdr subtable))))
(if record
(set-cdr! record value)
(set-cdr! subtable
(cons (cons key-2 value) (cdr subtable)))))
(set-cdr! local-table
(cons (list key-1
(cons key-2 value))
(cdr local-table)))))
'ok)
(define (dispatch m)
(cond ((eq? m 'lookup-proc) lookup)
((eq? m 'insert-proc!) insert!)
(else (error "Unknown operation -- TABLE" m))))
dispatch))
(define operation-table (make-table))
(define get (operation-table 'lookup-proc))
(define put (operation-table 'insert-proc!))
(define (attach-tag type-tag contents)
(cons type-tag contents))
(define (type-tag datum)
(cond ((number? datum) 'scheme-number)
((pair? datum) (car datum))
(else
(error "Bad tagged datum -- TYPE TAG" datum))))
(define (contents datum)
(cond ((number? datum) datum)
((pair? datum) (cdr datum))
(else
(error "Bad tagged datum -- CONTENTS" datum))))
(define (apply-generic op . args)
(let ((type-tags (map type-tag args)))
(let ((proc (get op type-tags)))
(if proc
(apply proc (map contents args))
(error
"No method for these types -- APPLY-GENERIC"
(list op type-tags))))))
(define (add x y) (apply-generic 'add x y))
(define (sub x y) (apply-generic 'sub x y))
(define (mul x y) (apply-generic 'mul x y))
(define (div x y) (apply-generic 'div x y))
(define (=zero? x) (apply-generic '=zero? x))
(define (install-scheme-number-package)
(put 'add '(scheme-number scheme-number) +)
(put 'sub '(scheme-number scheme-number) -)
(put 'mul '(scheme-number scheme-number) *)
(put 'div '(scheme-number scheme-number) /)
(put '=zero? '(scheme-number) zero?)
(put 'make 'scheme-number
(lambda (x) x))
'done)
(define (make-scheme-number n)
((get 'make 'scheme-number) n))あと、試験が以下。
test/test-2.5.3.scm
#!/usr/bin/env gosh
(use test.unit)
(require "2.5.3")
(define-test-suite "2.5.3"
("install package"
(setup (lambda () (install-scheme-number-package)))
("polynomial package"
(assert-equal 'done (install-polynomial-package))
)
("sparse termlist"
(assert-equal 'done (install-sparse-termlist))
)
("dense termlist"
(assert-equal 'done (install-dense-termlist))
)
("term"
(assert-equal 'done (install-term-package))
)
)
("term"
("make-term"
(assert-equal 'term (car (make-term 1 2)))
(assert-equal 1 (cadr (make-term 1 2)))
(assert-equal 2 (caddr (make-term 1 2)))
)
("order"
(assert-equal 2 (apply-generic 'order '(term 2 1)))
)
("coeff"
(assert-equal 1 (apply-generic 'coeff '(term 2 1)))
)
)
("make polynomial"
("make-sparse-polynomial"
(assert-equal '(polynomial x sparse 1 2 3 4 5)
(make-sparse-polynomial 'x '(1 2 3 4 5)))
)
("make-dense-polynomial"
(assert-equal '(polynomial x dense (10 1) (0 1))
(make-dense-polynomial 'x '((10 1) (0 1))))
)
)
("sparse-termlist (first-term)"
("no element"
(assert-equal '()
(apply-generic 'first-term '(sparse)))
)
("1 element"
(assert-equal '(term 0 5)
(apply-generic 'first-term '(sparse 5)))
)
("6 elements"
(assert-equal '(term 5 3)
(apply-generic 'first-term '(sparse 3 4 5 6 7 8)))
)
)
("sparse-termlist (rest-terms)"
("1 element"
(assert-equal '(sparse) (apply-generic 'rest-terms '(sparse 5)))
)
("6 elements"
(assert-equal '(sparse 4 5 6 7 8)
(apply-generic 'rest-terms '(sparse 3 4 5 6 7 8)))
)
)
("sparse-termlist (empty-termlist?)"
("empty sparse-termlist"
(assert-true (apply-generic 'empty-termlist? '(sparse)))
)
("all zero"
(assert-true (apply-generic 'empty-termlist? '(sparse 0 0 0)))
)
("no empty"
(assert-false (apply-generic 'empty-termlist? '(sparse 1)))
)
)
("sparse-termlist (the-empty-termlist) -- no use"
("..."
(assert-true (apply-generic 'empty-termlist?
((get 'the-empty-termlist 'sparse))))
)
("..."
(assert-equal '(sparse) ((get 'the-empty-termlist 'sparse)))
)
)
("sparse-termlist (adjoin-term)"
("3x+4 + 2x^2"
(assert-equal '(sparse 2 3 4)
((apply-generic 'adjoin-term '(sparse 3 4)) '(term 2 2)))
)
("0 + 2x^2"
(assert-equal '(sparse 2 0 0)
((apply-generic 'adjoin-term '(sparse)) '(term 2 2)))
)
("x + 2x^3"
(assert-equal '(sparse 2 0 1 0)
((apply-generic 'adjoin-term '(sparse 1 0)) '(term 3 2)))
)
)
("sparse polynomial operation (add)"
("different variable"
(assert-error (lambda () (add (make-sparse-polynomial 'x '(0 5))
(make-sparse-polynomial 'y '(0 5)))))
)
("add 0 to 5 (1)"
(let ((test (add (make-sparse-polynomial 'x '(0))
(make-sparse-polynomial 'x '(5)))))
(assert-equal 'polynomial (car test))
(assert-equal 'x (cadr test))
(assert-equal '(sparse 5) (cddr test)))
)
("add 0 to 5 (2)"
(let ((test (add (make-sparse-polynomial 'x '())
(make-sparse-polynomial 'x '(5)))))
(assert-equal 'polynomial (car test))
(assert-equal 'x (cadr test))
(assert-equal '(sparse 5) (cddr test)))
)
("add 5 to 0 (1)"
(let ((test (add (make-sparse-polynomial 'x '(5))
(make-sparse-polynomial 'x '(0)))))
(assert-equal 'polynomial (car test))
(assert-equal 'x (cadr test))
(assert-equal '(sparse 5) (cddr test)))
)
("add 5 to 0 (2)"
(let ((test (add (make-sparse-polynomial 'x '(5))
(make-sparse-polynomial 'x '()))))
(assert-equal 'polynomial (car test))
(assert-equal 'x (cadr test))
(assert-equal '(sparse 5) (cddr test)))
)
("normal"
(assert-equal '(polynomial x sparse 3 2 4)
(add (make-sparse-polynomial 'x '(2 1 2))
(make-sparse-polynomial 'x '(1 1 2))))
)
("x+2 + 2x^2+2x+2 -> 2x^2+3x+4"
(assert-equal '(polynomial x sparse 2 3 4)
(add (make-sparse-polynomial 'x '(1 2))
(make-sparse-polynomial 'x '(2 2 2))))
)
("2x^2+2x+2 + x+2 -> 2x^2+3x+4"
(assert-equal '(polynomial x sparse 2 3 4)
(add (make-sparse-polynomial 'x '(2 2 2))
(make-sparse-polynomial 'x '(1 2))))
)
("0x^3+0x^2+0x+0 + x^3+2x^2+3x+4 -> x^3+2x^2+3x+4"
(assert-equal '(polynomial x sparse 1 2 3 4)
(add (make-sparse-polynomial 'x '(0 0 0 0))
(make-sparse-polynomial 'x '(1 2 3 4))))
)
("x^3+2x^2+3x+4 + 0x^3+0x^2+0x+0 -> x^3+2x^2+3x+4"
(assert-equal '(polynomial x sparse 1 2 3 4)
(add (make-sparse-polynomial 'x '(1 2 3 4))
(make-sparse-polynomial 'x '(0 0 0 0))))
)
("0 + x^3+2x^2+3x+4 -> x^3+2x^2+3x+4"
(assert-equal '(polynomial x sparse 1 2 3 4)
(add (make-sparse-polynomial 'x '())
(make-sparse-polynomial 'x '(1 2 3 4))))
)
("x^3+2x^2+3x+4 + 0 -> x^3+2x^2+3x+4"
(assert-equal '(polynomial x sparse 1 2 3 4)
(add (make-sparse-polynomial 'x '(1 2 3 4))
(make-sparse-polynomial 'x '())))
)
("1 - 1 -> 0"
(assert-equal '(polynomial x sparse 0)
(add (make-sparse-polynomial 'x '(1))
(make-sparse-polynomial 'x '(-1))))
)
)
("sparse polynomial operation (mul)"
("different variable"
(assert-error (lambda () (mul (make-sparse-polynomial 'x '(5))
(make-sparse-polynomial 'y '(5)))))
)
("p1 is not variable"
(assert-error (lambda () (mul (make-sparse-polynomial 1 '(5))
(make-sparse-polynomial 'x '(5)))))
)
("p2 is not variable"
(assert-error (lambda () (mul (make-sparse-polynomial 'x '(5))
(make-sparse-polynomial 2 '(5)))))
)
("1 * 1 -> 1"
(assert-equal '(polynomial x sparse 1)
(mul (make-sparse-polynomial 'x '(1))
(make-sparse-polynomial 'x '(1))))
)
;; !! it's not _the-empty-termlist_ !!
;; mmmm....
("0 * 1 -> 0"
(assert-equal '(polynomial x sparse 0)
(mul (make-sparse-polynomial 'x '(0))
(make-sparse-polynomial 'x '(1))))
)
("1 * 0 -> 0"
(assert-equal '(polynomial x sparse)
(mul (make-sparse-polynomial 'x '(1))
(make-sparse-polynomial 'x '(0))))
)
("0 * 1 -> 0"
(assert-equal '(polynomial x sparse)
(mul (make-sparse-polynomial 'x '())
(make-sparse-polynomial 'x '(1))))
)
("1 * 0 -> 0"
(assert-equal '(polynomial x sparse)
(mul (make-sparse-polynomial 'x '(1))
(make-sparse-polynomial 'x '())))
)
("6x+5 * 2x^2+3 -> 12x^3+10x^2+18x+15"
(assert-equal '(polynomial x sparse 12 10 18 15)
(mul (make-sparse-polynomial 'x '(6 5))
(make-sparse-polynomial 'x '(2 0 3))))
)
)
("sparse polynomial operation (=zero?)"
("() is zero"
(assert-true (=zero? (make-sparse-polynomial 'x '())))
)
("() is zero (2)"
(assert-true (=zero? '(polynomial x sparse)))
)
("(0 0 0 0) is zero"
(assert-true (=zero? '(polynomial x sparse 0 0 0 0)))
)
("(y + 1)x + (-y - 1)x is zero"
(let ((py1 (make-sparse-polynomial 'y '(1 1)))
(py2 (make-sparse-polynomial 'y '(-1 -1))))
(assert-true (=zero? (add (make-sparse-polynomial 'x (list py1 0))
(make-sparse-polynomial 'x (list py2 0))))))
)
)
("sparse polynomial operation (neg)"
("first (1x - 1x = 0)"
(assert-true (=zero? (add (make-sparse-polynomial 'x '(1 0))
(neg (make-sparse-polynomial 'x '(1 0))))))
)
("2nd (1x - 0 = 1x)"
(let ((p (make-sparse-polynomial 'x '(1 0))))
(assert-equal p (add p (neg (make-sparse-polynomial 'x '())))))
)
("3rd (1x - 0x = 1x)"
(let ((p1 (make-sparse-polynomial 'x '(1 0)))
(p2 (make-sparse-polynomial 'x '(0 0))))
(assert-equal p1 (add p1 (neg p2))))
)
("4th polynomial neg"
(let ((p1 (make-sparse-polynomial 'x '(1 2 3 4)))
(p2 (make-sparse-polynomial 'x '(-1 -2 -3 -4))))
(assert-equal p1 (neg p2))
(assert-equal p2 (neg p1)))
)
)
("dense-termlist (first-term)"
("1 element"
(assert-equal '(term 0 5)
(apply-generic 'first-term '(dense (0 5))))
)
("6 elements"
(assert-equal '(term 5 3)
(apply-generic 'first-term
'(dense (5 3) (4 4) (3 5) (2 6) (1 7) (0 8))))
)
)
("dense-termlist (rest-terms)"
("1 element"
(assert-equal '(dense) (apply-generic 'rest-terms '(dense (2 5))))
)
("6 elements"
(assert-equal '(dense (7 4) (6 5) (4 6) (2 7) (0 8))
(apply-generic 'rest-terms
'(dense (9 3) (7 4) (6 5) (4 6) (2 7) (0 8))))
)
)
("dense-termlist (empty-termlist?)"
("empty dense-termlist"
(assert-true (apply-generic 'empty-termlist? '(dense)))
)
("no empty"
(assert-false (apply-generic 'empty-termlist? '(dense (0 1))))
)
)
("dense-termlist (the-empty-termlist) -- no use"
("..."
(assert-true (apply-generic 'empty-termlist?
((get 'the-empty-termlist 'dense))))
)
("..."
(assert-equal '(dense) ((get 'the-empty-termlist 'dense)))
)
)
("dense-termlist (adjoin-term)"
("3x+4 + 2x^2"
(assert-equal '(dense (2 2) (1 3) (0 4))
((apply-generic 'adjoin-term '(dense (1 3) (0 4))) '(term 2 2)))
)
("0 + 2x^2"
(assert-equal '(dense (2 2))
((apply-generic 'adjoin-term '(dense)) '(term 2 2)))
)
("x + 2x^3"
(assert-equal '(dense (3 2) (1 1))
((apply-generic 'adjoin-term '(dense (1 1))) '(term 3 2)))
)
)
("dense polynomial operation (add)"
("different variable"
(assert-error (lambda () (add (make-dense-polynomial 'x '((0 5)))
(make-dense-polynomial 'y '((0 5))))))
)
("add 0 to 5 (1)"
(let ((test (add (make-dense-polynomial 'x '((0 0)))
(make-dense-polynomial 'x '((0 5))))))
(assert-equal 'polynomial (car test))
(assert-equal 'x (cadr test))
(assert-equal '(dense (0 5)) (cddr test)))
)
("add 0 to 5 (2)"
(let ((test (add (make-dense-polynomial 'x '())
(make-dense-polynomial 'x '((0 5))))))
(assert-equal 'polynomial (car test))
(assert-equal 'x (cadr test))
(assert-equal '(dense (0 5)) (cddr test)))
)
("add 5 to 0 (1)"
(let ((test (add (make-dense-polynomial 'x '((0 5)))
(make-dense-polynomial 'x '((0 0))))))
(assert-equal 'polynomial (car test))
(assert-equal 'x (cadr test))
(assert-equal '(dense (0 5)) (cddr test)))
)
("add 5 to 0 (2)"
(let ((test (add (make-dense-polynomial 'x '((0 5)))
(make-dense-polynomial 'x '()))))
(assert-equal 'polynomial (car test))
(assert-equal 'x (cadr test))
(assert-equal '(dense (0 5)) (cddr test)))
)
("normal"
(assert-equal '(polynomial x dense (5 3) (2 2) (0 4))
(add (make-dense-polynomial 'x '((5 2) (2 1) (0 2)))
(make-dense-polynomial 'x '((5 1) (2 1) (0 2)))))
)
("x+2 + 2x^2+2x+2 -> 2x^2+3x+4"
(assert-equal '(polynomial x dense (5 2) (3 3) (1 4))
(add (make-dense-polynomial 'x '((3 1) (1 2)))
(make-dense-polynomial 'x '((5 2) (3 2) (1 2)))))
)
("2x^2+2x+2 + x+2 -> 2x^2+3x+4"
(assert-equal '(polynomial x dense (2 2) (1 3) (0 4))
(add (make-dense-polynomial 'x '((2 2) (1 2) (0 2)))
(make-dense-polynomial 'x '((1 1) (0 2)))))
)
("0x^3+0x^2+0x+0 + x^3+2x^2+3x+4 -> x^3+2x^2+3x+4"
(assert-equal '(polynomial x dense (3 1) (2 2) (1 3) (0 4))
(add (make-dense-polynomial 'x '((3 0) (2 0) (1 0) (0 0)))
(make-dense-polynomial 'x '((3 1) (2 2) (1 3) (0 4)))))
)
("x^3+2x^2+3x+4 + 0x^3+0x^2+0x+0 -> x^3+2x^2+3x+4"
(assert-equal '(polynomial x dense (3 1) (2 2) (1 3) (0 4))
(add (make-dense-polynomial 'x '((3 1) (2 2) (1 3) (0 4)))
(make-dense-polynomial 'x '((3 0) (2 0) (1 0) (0 0)))))
)
("0 + x^3+2x^2+3x+4 -> x^3+2x^2+3x+4"
(assert-equal '(polynomial x dense (3 1) (2 2) (1 3) (0 4))
(add (make-dense-polynomial 'x '())
(make-dense-polynomial 'x '((3 1) (2 2) (1 3) (0 4)))))
)
("x^3+2x^2+3x+4 + 0 -> x^3+2x^2+3x+4"
(assert-equal '(polynomial x dense (3 1) (2 2) (1 3) (0 4))
(add (make-dense-polynomial 'x '((3 1) (2 2) (1 3) (0 4)))
(make-dense-polynomial 'x '())))
)
("1 - 1 -> 0"
(assert-equal '(polynomial x dense)
(add (make-dense-polynomial 'x '((0 1)))
(make-dense-polynomial 'x '((0 -1)))))
)
)
("dense polynomial operation (mul)"
("different variable"
(assert-error (lambda () (mul (make-dense-polynomial 'x '((0 5)))
(make-dense-polynomial 'y '((0 5))))))
)
("p1 is not variable"
(assert-error (lambda () (mul (make-dense-polynomial 1 '((0 5)))
(make-dense-polynomial 'x '((0 5))))))
)
("p2 is not variable"
(assert-error (lambda () (mul (make-dense-polynomial 'x '((0 5)))
(make-dense-polynomial 2 '((0 5))))))
)
("1 * 1 -> 1"
(assert-equal '(polynomial x dense (0 1))
(mul (make-dense-polynomial 'x '((0 1)))
(make-dense-polynomial 'x '((0 1)))))
)
;; !! it's not _the-empty-termlist_ !!
;; mmmm....
("0 * 1 -> 0"
(assert-equal '(polynomial x dense)
(mul (make-dense-polynomial 'x '())
(make-dense-polynomial 'x '((0 1)))))
)
("1 * 0 -> 0"
(assert-equal '(polynomial x dense)
(mul (make-dense-polynomial 'x '((0 1)))
(make-dense-polynomial 'x '())))
)
("0 * 1 -> 0"
(assert-equal '(polynomial x dense)
(mul (make-dense-polynomial 'x '((0 0)))
(make-dense-polynomial 'x '((0 1)))))
)
("1 * 0 -> 0"
(assert-equal '(polynomial x dense)
(mul (make-dense-polynomial 'x '((0 1)))
(make-dense-polynomial 'x '((0 0)))))
)
("6x+5 * 2x^2+3 -> 12x^3+10x^2+18x+15"
(assert-equal '(polynomial x dense (3 12) (2 10) (1 18) (0 15))
(mul (make-dense-polynomial 'x '((1 6) (0 5)))
(make-dense-polynomial 'x '((2 2) (0 3)))))
)
)
("dense polynomial operation (=zero?)"
("() is zero"
(assert-true (=zero? (make-dense-polynomial 'x '())))
)
("() is zero (2)"
(assert-true (=zero? '(polynomial x dense)))
)
("(y + 1)x + (-y - 1)x is zero"
(let ((py1 (make-dense-polynomial 'y '((1 1) (0 1))))
(py2 (make-dense-polynomial 'y '((1 -1) (0 -1)))))
(assert-true (=zero? (add (make-dense-polynomial 'x (list (list 1 py1)
'(0 0)))
(make-dense-polynomial 'x (list (list 1 py2)
'(0 0)))))))
)
)
("dense polynomial operation (neg)"
("first (1x - 1x = 0)"
(assert-true (=zero? (add (make-dense-polynomial 'x '((1 1)))
(neg (make-dense-polynomial 'x '((1 1)))))))
)
("2nd (1x - 0 = 1x)"
(let ((p (make-dense-polynomial 'x '((1 1)))))
(assert-equal p (add p (neg (make-dense-polynomial 'x '())))))
)
("3rd (1x - 0x = 1x)"
(let ((p1 (make-dense-polynomial 'x '((1 1))))
(p2 (make-dense-polynomial 'x '())))
(assert-equal p1 (add p1 (neg p2))))
)
("4th polynomial neg"
(let ((p1 (make-dense-polynomial 'x '((5 1) (3 2) (1 3) (0 4))))
(p2 (make-dense-polynomial 'x '((5 -1) (3 -2) (1 -3) (0 -4)))))
(assert-equal p1 (neg p2))
(assert-equal p2 (neg p1)))
)
)
)微妙なままサラしてしまう、というのも無責任というか ....
