練習問題 (5)
3.1 はスルーで。別途きちんと読んだ方が良さげではありますが。練習問題は 3.2 さらに再帰 の部分から。
練習問題 3.2.2 (素因数計算サンプルの letrec による書き直し)
サンプルは以下。
(define factor
(lambda (n)
(let f ((n n) (i 2))
(cond
((> i n) '())
((integer? (/ n i))
(cons i (f (/ n i) i)))
(else (f n (+ i 1)))))))実行例も。
guile> (factor 12) (2 2 3) guile> (factor 3628800) (2 2 2 2 2 2 2 2 3 3 3 3 5 5 7) guile> (factor 9239) (9239) guile>
書き直したのが以下。
(define factor
(lambda (n)
(letrec ((f
(lambda (n i)
(cond
((> i n) '())
((integer? (/ n i))
(cons i (f (/ n i) i)))
(else (f n (+ i 1)))))))
(f n 2))))動作は同じでした。あんまコード読んでないな。ちょっと機械的になってるな。
練習問題 3.2.3 (even? や odd? が名前付き let で書き直せるか)
できると思う、根拠はないけど。まずサンプル。
(letrec ((even? (lambda (x) (or (= x 0) (odd? (- x 1))))) (odd? (lambda (x) (and (not (= x 0)) (even? (- x 1)))))) (list (even? 20) (odd? 20)))
上記は (#t #f) が返却される、との事。やってみた。
guile> (letrec ((even?
(lambda (x)
(or (= x 0)
(odd? (- x 1)))))
(odd?
(lambda (x)
(and (not (= x 0))
(even? (- x 1))))))
(list (even? 20) (odd? 20)))
(#t #f)
guile> うーん。letrec は複数シンボルへのバインドが可能なんか。名前付き let は単発っぽい。でも独習 scheme 三週間の 6.2 名前つき let の項によれば
名前つきletは letrecフォームに展開されるマクロ(8章参照)のひとつであると考えてさしつかえありません。
6.2 名前つき letより引用
とある。
けど、ぱっと見無理っぽいな。上記引用によれば完全に互換があるような言い方ではないし。R5RS からは複数 OK な記述は探せない。別途、根拠を調べます。
練習問題 3.2.4 (fibonacci の定義書き直し)
テキストで出てきているサンプルは以下。
その一
(define fibonacci
(lambda (n)
(let fib ((i n))
(cond
((= i 0) 0)
((= i 1) 1)
(else (+ (fib (- i 1)) (fib (- i 2))))))))その二
(define fibonacci
(lambda (n)
(if (= n 0)
0
(let fib ((i n) (a1 1) (a2 0))
(if (= i 1)
a1
(fib (- i 1) (+ a1 a2) a1))))))設問ではこれらを_グローバルな呼び出しカウンタ_を使って数え上げをして、呼び出し回数をチェックしてみれ、というもの。で件の呼び出しカウンタを使った cons のサンプルを以下に。
(define cons-count 0)
(set! cons
(let ((old-cons cons))
(lambda (x y)
(set! cons-count (+ cons-count 1))
(old-cons x y))))その二はナニですがその一は微妙。あまりエレガントではないと思うがとりあえず実装。
(define fibonacci
(lambda (n)
(let fib ((i n))
((lambda ()
(set! fib-counter (+ fib-counter 1))
(display "fib ")
(display i)
(newline)
))
(cond
((= i 0) 0)
((= i 1) 1)
(else (+ (fib (- i 1)) (fib (- i 2))))))))大丈夫だよな。試験を。
guile> (set! fib-counter 0) guile> (fibonacci 5) fib 5 fib 4 fib 3 fib 2 fib 1 fib 0 fib 1 fib 2 fib 1 fib 0 fib 3 fib 2 fib 1 fib 0 fib 1 5 guile> fib-counter 15 guile>
えーと、手トレイスか。どうやって表現するか微妙だな。
(fib 5)
~~~~~~~
(+ (fib 4) (fib 3))
~~~~~~~
(+ (+ (fib 3) (fib 2)) (fib 3))
~~~~~~~
(+ (+ (+ (fib 2) (fib 1)) (fib 2)) (fib 3))
~~~~~~~
(+ (+ (+ (+ (fib 1) (fib 0)) (fib 1)) (fib 2)) (fib 3))
~~~~~~~
(+ (+ (+ (+ 1 (fib 0)) (fib 1)) (fib 2)) (fib 3))
~~~~~~~
(+ (+ (+ (+ 1 0) (fib 1)) (fib 2)) (fib 3))
~~~~~~~
(+ (+ (+ (+ 1 0) 1) (fib 2)) (fib 3))
~~~~~~~
(+ (+ (+ (+ 1 0) 1) (+ (fib 1) (fib 0))) (fib 3))
~~~~~~~
(+ (+ (+ (+ 1 0) 1) (+ 1 (fib 0))) (fib 3))
~~~~~~~
(+ (+ (+ (+ 1 0) 1) (+ 1 0)) (fib 3))
~~~~~~~
(+ (+ (+ (+ 1 0) 1) (+ 1 0)) (+ (fib 2) (fib 1)))
~~~~~~~
(+ (+ (+ (+ 1 0) 1) (+ 1 0)) (+ (+ (fib 1) (fib 0)) (fib 1)))
~~~~~~~
(+ (+ (+ (+ 1 0) 1) (+ 1 0)) (+ (+ 1 (fib 0)) (fib 1)))
~~~~~~~
(+ (+ (+ (+ 1 0) 1) (+ 1 0)) (+ (+ 1 0) (fib 1)))
~~~~~~~
(+ (+ (+ (+ 1 0) 1) (+ 1 0)) (+ (+ 1 0) 1))とりあえず呼び出されるナニにアンダーラインを入れとります。順番的にも回数的にもセイフかな。しかし面倒やっさ。こんなトレイスできるユーティリティーが (以下略
ではその二を同じ手法で。
(define fibonacci
(lambda (n)
(if (= n 0)
0
(let fib ((i n) (a1 1) (a2 0))
((lambda ()
(set! fib-counter (+ fib-counter 1))
(display "fib ")
(display i)
(display " ")
(display a1)
(display " ")
(display a2)
(newline)))
(if (= i 1)
a1
(fib (- i 1) (+ a1 a2) a1))))))で、実行。
guile> (fibonacci 5) fib 5 1 0 fib 4 1 1 fib 3 2 1 fib 2 3 2 fib 1 5 3 5 guile>
を。繰り返しだ。
デカい引数でどの位違うかね。
guile> (fibonacci 20) fib 20 1 0 fib 19 1 1 fib 18 2 1 fib 17 3 2 fib 16 5 3 fib 15 8 5 fib 14 13 8 fib 13 21 13 fib 12 34 21 fib 11 55 34 fib 10 89 55 fib 9 144 89 fib 8 233 144 fib 7 377 233 fib 6 610 377 fib 5 987 610 fib 4 1597 987 fib 3 2584 1597 fib 2 4181 2584 fib 1 6765 4181 6765 guile>
20 で 20 回。その一は display をコメントアウトで。
guile> (set! fib-counter 0) guile> (fibonacci 20) 6765 guile> fib-counter 21891 guile>
これはこれは。(としか言いようがない
