EoPL reading (43) 2.1 Specifying Data via Interfaces
Exercise.2-1
うーん。bigits って何だろ、ググッても微妙なナニしか出てこなかったんですが Method for data compression という所にて以下な記述があった。
"BIGIT" A place holder in the binary number system. For example, a byte is a binary number having a length of 8 bigits. A bigit is analogous to a digit in the base 10 number system.
上記を参考に手続きをでっち上げれば良いのか。
しかしどうしたものやら。こんなカンジで表現すりゃ良い?
0 = '() 1 = '(1) 2 = '(0 1) 3 = '(1 1) 4 = '(0 0 1)
これって 2 値だから #t と #f なリストでも良いのか。てーコトは
(define zero '()) (define iszero? null?)
で OK か。あるいはこう?
(define zero '(#f)) (define iszero? (lambda (x) (and (= 1 (length x)) (eq? #f (car x)))))
ちょっと試験書いて実装するか。以下な試験を書きました。
(use gauche.test)
(add-load-path ".")
(load "bigits")
(test-start "bigits")
(test-section "bigits")
(test* "zero should return '(#f)"
'(#f)
zero)
(test* "(iszero? zero) shuould return #t"
#t
(iszero? zero))
(test* "(not (iszero? zero)) should return #f"
#f
(not (iszero? zero)))
(test-end)試験はパス。
Compilation started at Fri Jul 31 22:22:33 make -k Testing bigits ... passed. Compilation finished at Fri Jul 31 22:22:33
あとは succ と pred の試験と実装か。とりあえずこんな試験を追加。
(test-section "succ")
(test* "(succ zero) should return '(#t)"
'(#t)
(succ zero))ええと、
- car が #f なら (cons #t (cdr l)) で OK
- car が #t なら (cons #f (succ (cdr l))) で OK?
とりあえず #f 前提で試験だけ通そう。実装は以下。
(define succ (lambda (x) (cons #t (cdr x))))
(cdr l) ってヤッちゃったのは秘密。もう一つのソレも試験。
(test* "(succ (succ zero)) should return '(#f #t)"
'(#f #t)
(succ (succ zero)))紆余曲折の末、以下の実装で上記の試験にパス。
(define succ (lambda (x) (cond ((null? x) '(#t)) ((eq? #f (car x)) (cons #t (cdr x))) (else (cons #f (succ (cdr x)))))))
もう一つヤッてみます。
Testing bigits ================================================================ <zero & iszero?>--------------------------------------------------------------- test zero should return '(#f), expects (#f) ==> ok test (iszero? zero) shuould return #t, expects #t ==> ok test (not (iszero? zero)) should return #f, expects #f ==> ok <succ>------------------------------------------------------------------------- test (succ zero) should return '(#t), expects (#t) ==> ok test (succ (succ zero)) should return '(#f #t), expects (#f #t) ==> ok test (succ (succ (succ zero))) should return '(#t #t), expects (#t #t) ==> ok passed.
一応試験パスな模様。次は pred ですか。テストデータは作れるので試験は楽ですが実装が微妙。とりあえず最初の試験が以下。
(test-section "pred")
(test* "(pred (succ zero)) should return zero"
zero
(pred (succ zero)))実装は負の値、というか zero が渡されない前提にて。上記試験をパスするだけの実装が以下。
(define pred (lambda (x) (cons #f (cdr x))))
一応パス。
Testing bigits ================================================================ <zero & iszero?>--------------------------------------------------------------- test zero should return '(#f), expects (#f) ==> ok test (iszero? zero) shuould return #t, expects #t ==> ok test (not (iszero? zero)) should return #f, expects #f ==> ok <succ>------------------------------------------------------------------------- test (succ zero) should return '(#t), expects (#t) ==> ok test (succ (succ zero)) should return '(#f #t), expects (#f #t) ==> ok test (succ (succ (succ zero))) should return '(#t #t), expects (#t #t) ==> ok test (succ (succ (succ (succ zero)))) should return '(#f #f #t), expects (#f #f #t) ==> ok <pred>------------------------------------------------------------------------- test (pred (succ zero)) should return zero, expects (#f) ==> ok passed.
で、以下の実装にしてみたら
(define pred (lambda (x) (cons ((eq? #t (car x)) (cons #f (cdr x))) (else (cons #t (pred (cdr x)))))))
失敗。
Compilation started at Fri Jul 31 23:02:44 make -k Testing bigits ... failed. discrepancies found. Errors are: test (pred (succ zero)) should return zero: expects (#f) => got #<error "invalid application: (#t (#f))"> Compilation finished at Fri Jul 31 23:02:44
げ。これは微妙だな。って cond を cons って書いてます。。修正したらパス。次に以下の試験を書いた。
(test* "(pred (succ (succ (succ (succ zero))))) should return '(#t #t)"
'(#t #t)
(pred (succ (succ (succ (succ zero))))))これが試験にパスしない。
test (pred (succ (succ (succ (succ zero))))) should return '(#t #t): expects (#t #t) => got (#t #t #f)
むむ。どうすりゃ良いのか。ええと、アタマが '(#f) になったらツブせば良い?
で、試験したら以下。
Compilation started at Fri Jul 31 23:26:58 make -k Testing bigits ... failed. discrepancies found. Errors are: test (pred '(#t)) should return zero: expects (#f) => got () test (pred (succ zero)) should return zero: expects (#f) => got () Compilation finished at Fri Jul 31 23:26:58
むむ。これはこれは。仕方が無いんで zero と iszero? の定義を以下に変更。
(define zero '()) (define iszero? null?)
で、pred の試験をもう少し追加。
(test* "(pred (pred (succ (succ (succ (succ zero)))))) should return '(#f #t)"
'(#f #t)
(pred (pred (succ (succ (succ (succ zero)))))))
(test* "(pred (pred (pred (succ (succ (succ (succ zero))))))) should return '(#t)"
'(#t)
(pred (pred (pred (succ (succ (succ (succ zero))))))))
(test* "(pred (pred (pred (pred (succ (succ (succ (succ zero))))))) should return zero"
zero
(pred (pred (pred (pred (succ (succ (succ (succ zero)))))))))いずれもパス。で、次は 10 の階乗ッスか。あるいは例示されてる plus が正常に動くかどうかも確認した方が良さげ。
(test-section "plus")
(test* "(plus (succ (succ zero)) (succ (succ (succ zero))))
should returns '(#t #f #t)"
'(#t #f #t)
(plus (succ (succ zero)) (succ (succ (succ zero)))))一応試験にはパス。plus の実装は以下です。
(define plus
(lambda (x y)
(if (iszero? x)
y
(succ (plus (pred x) y)))))では factorial なナニに着手。2 を掛けたり割ったりは得意なデータ構造なんだけどなぁ。ちょっと設問の意図も微妙に理解できてなかったりします。
日が変わりそうなので一旦投入。なんとなく階乗の答えは出そうにない気がします。
google 先生に聞いてみたら
2 進の乗算とか色々あるみたい。とりあえずココを参考にしつつ手続きをでっち上げてみます。
試験が以下。
(test-section "mul")
(test* "(mul (succ (succ zero)) (succ (succ (succ zero))))
should return '(#f #t #t)"
'(#f #t #t)
(mul (succ (succ zero)) (succ (succ (succ zero)))))カンニングしつつ作った実装が以下。
(define mul
(lambda (x y)
(let f ((R0 x) (Acc y) (rslt zero))
(cond ((null? Acc) rslt)
((car Acc) (f (cons 0 R0) (cdr Acc) (plus R0 rslt)))
(else
(f (cons 0 R0) (cdr Acc) rslt)))
)
))試験にはパスしてます。本当に大丈夫なんだろうか。とりあえず factorial は定義できそげなカンジですが、遅いのでもう寝る。
