練習問題
休み突入モードです。ピアソンの scheme 本の練習問題をやってみた。
練習問題 2.4.3 (隠蔽される変数がなくなるように式を書き直す)
a)
(let ((x 'a) (y 'b)) (list (let ((x 'c)) (cons x y)) (let ((y 'd)) (cons x y)))) (let ((x 'a) (y 'b)) (list (let ((new-x 'c)) (cons new-x y)) (let ((new-y 'd)) (cons x new-y))))
b) #これはこれは ...
(let ((x '((a b) c))) (cons (let ((x (cdr x))) (car x)) (let ((x (car x))) (cons (let ((x (cdr x))) (car x)) (cons (let ((x (car x))) x) (cdr x)))))) (let ((x '((a b) c))) (cons (let ((x-1 (cdr x))) (car x-1)) (let ((x-2 (car x))) (cons (let ((x-3 (cdr x-2))) (car x-3)) (cons (let ((x-4 (car x-2))) x-4) (cdr x-2))))))
b は無理矢理な感じもしますなぁ。
練習問題 2.5.2 (list はどのように定義されているか)
答えが別な頁に記述されているのですが、意味不明なので検討してみる。
(define (list . x) x)
他の書き方として
(define list (lambda ( . x) x))
とか (これ、微妙だなぁ)
(define list (lambda x x))
とか??
書き換え可能なナニが列挙されているので実例にあてはめてみる。
まず一つ目のパターン。
guile> (define aaa (lambda (x y z) (+ x y z))) guile> (aaa 3 4 5) 12 guile> (define (aaa2 x y z) (+ x y z)) guile> (aaa2 3 4 5) 12 guile>
次は上記リストなパターンだな。
guile> (define bbb (lambda x (apply + x))) guile> (bbb 5 6 7) 18 guile> (define (bbb2 . x) (apply + x)) guile> (bbb2 5 6 7) 18 guile>
最後のパターン。
guile> (define ccc (lambda (x y . z) (apply + x y z))) guile> (ccc 1 2) 3 guile> (ccc 1 2 3 4 5) 15 guile> (define (ccc2 x y . z) (apply + x y z)) guile> (ccc2 1 2) 3 guile> (ccc2 1 2 3 4 5) 15 guile>
練習問題 2.7.1 (引数がペアであれば偽を返し、ペアでなければ真を返す atom? を定義)
(define (atom? x) (not (pair? x)))
あるいは
(define atom? (lambda (x) (not (pair? x))))
正解なのかどうか不明。試験は以下のような感じ。足りてない感満載かも。
guile> (atom? 5) #t guile> (atom? #\a) #t guile> (atom? '(5)) #f guile> (atom? '(1 2 3)) #f guile> (atom? '()) #t guile> (atom? '(a . b)) #f guile>
練習問題 2.7.2 (リストを二つ引数に取って短い方を返す shorter を書け)
以下が実行例
guile> (shorter (a b) (c d e)) (a b) guile>
って、上記はあり得んなぁ。違うかなぁ。引数は quote しねぇと駄目なんじゃね??
それを前提に考えてみます。(弱
(define (shorter l1 l2)
(if (< (length l1) (length l2))
l1
l2))なんか微妙。cond 使うとこんな感じですか。
(define (shorter n m) (cond ((< (length n) (length m)) n) (else m)))
一応 quote すれば動くな。
guile> (shorter '(a b) '(c d e)) (a b) guile> (shorter '(a b c) '(d e)) (d e) guile>
練習問題 2.8.1 (tree-copy の定義中にある cons の順を逆にしたらどうなるか)
tree-copy の定義は以下。
(define tree-copy
(lambda (tr)
(if (not (pair? tr))
tr
(cons (tree-copy (car tr))
(tree-copy (cdr tr))))))どうもリストなナニが微妙だな。別途整理の必要あり??
とりあえず手トレースしてみる。(tree-copy '((a . b) . c)) で。
- まず、(tree-copy '(a . b)) される
- (tree-copy a) と (tree-copy b) が cons される → (a . b)
- 1. の結果と (tree-copy c) の結果が cons される → ((a . b) . c)
纏めると (cons (cons 'a 'b) 'c) か。→ ((a . b) . c)
で、cons を逆にしたのが以下。
(define tree-copy
(lambda (tr)
(if (not (pair? tr))
tr
(cons (tree-copy (cdr tr))
(tree-copy (car tr))))))再度、手動トレースを (tree-copy '((a . b) . c)) で。
- まず、(tree-copy c) される
- 次に (tree-copy '(a . b)) が呼び出される
- (tree-copy b) と (tree-copy a) が cons される → (b . a)
- 1. の結果と 2. の結果が cons される
纏めると (cons 'c (cons 'b 'a)) になる。→ (c b . a)
練習問題 2.8.2 (6.2 項の append の解説を元に append の 2 引数バージョンを定義。又、定義中の再帰呼び出しへの引数の順を逆にしたら何が起きるか)
解説には append のサンプルが出ております。
(define append2
(lambda args
(let f ((ls '()) (args args))
(if (null? args)
ls
(let g ((ls ls))
(if (null? ls)
(f (car args) (cdr args))
(cons (car ls) (g (cdr ls)))))))))手でトレイスしてみる。最初は (append2 '()) から。
args が '() なんで ls の初期値 ('()) を返却して終了 (早次も単純なナニを。(append2 '(a b c)) ではイカガか。ちなみに append2 で引数を受領した時点でこの例では args の状態は ((a b c)) となる。(← これ、忘れててサバクをさまよっておりました)
最初は ls が '() なので
(f (car '((a b c))) (cdr '((a b c))))
→ (f '(a b c) '())
args は '() なんで ls ('(a b c)) を返却して終了次はちょっとヒネッてみる。(append '(a b c) '(d e) '(f g)) で。引数 args には ((a b c) (d e) (f g)) が渡されるはず。
(f (car '((a b c) (d e) (f g))) (cdr '((a b c) (d e) (f g))))
→ (f '(a b c) '((d e) (f g)))
(cons (car '(a b c)) (g (cdr '(a b c))))
→ (cons 'a (g '(b c)))
(cons (car '(b c)) (g (cdr '(b c))))
→ (cons 'b (g '(c)))
(cons (car '(c)) (g (cdr '(c))))
→ (cons 'c (g '()))
(f (car '((d e) (f g))) (cdr '((d e) (f g))))
→ (f '(d e) '(f g))む。順番にカワをむいで先頭から要素を取り出しつつ cons してるな。最終的に
(cons 'a (cons 'b (cons 'c (cons 'd '()))))
後を略しましたが、こんな感じになるのか。
で、引数二つ限定にするとしたらアタマのへんはこんな感じ?? ってかこんなの思い付いたんだけど駄目だろうなぁ。
(define (append3 n m)
(let f ((ls '()) (args (cons n m)))
(if (null? args)
ls
(let g ((ls ls))
(if (null? ls)
(f (car args) (cdr args))
(cons (car ls) (g (cdr ls))))))))ちょっと eazy 杉だった模様。うーむ。args に渡すのを list にしてみたらどうか。
(define (append3 n m)
(let f ((ls '()) (args (list n m)))
(if (null? args)
ls
(let g ((ls ls))
(if (null? ls)
(f (car args) (cdr args))
(cons (car ls) (g (cdr ls))))))))あら、動いた。とりあえず検証は別途。(眠
# ぢつはここまでの作業、12/25 深夜実施ッス。(を
しかしパクりバージョンではなくて、きちんと考えたいなぁ。
上記 append2 のポイントは引数か。シンボルでうけとる場合リストになって渡ってくるのがナニ。
guile> ((lambda args (p args)) '(a b c) '(d e) '(f g h)) ((a b c) (d e) (f g h)) guile> ((lambda args (p args)) 1 2 3 4 5) (1 2 3 4 5) guile> ((lambda args (p args)) 1 2 '(3 4 5) 6 7) (1 2 (3 4 5) 6 7) guile>
ので、list しちゃえばいいじゃん、ってのはある意味ビンゴかも。(を
guile> ((lambda (n m) (p (list n m))) '(a b c) '(d e f)) ((a b c) (d e f)) guile>
letrec 使ってみた。がしかし焼き直しやっさ (駄目
(define (append5 n m)
(letrec ((f (lambda (ls args)
(if (null? args)
ls
(let g ((ls ls))
(if (null? ls)
(f (car args) (cdr args))
(cons (car ls) (g (cdr ls)))))))))
(f '() (list n m))))あ、g が名前付き let だな。こうなってくると名前付き let と letrec のどっちが可読性が良いか微妙。(今の印象では名前付きの方がポイント高いかも)
(define (append6 n m)
(letrec ((f (lambda (ls args)
(if (null? args)
ls
(letrec ((g (lambda (ls)
(if (null? ls)
(f (car args) (cdr args))
(cons (car ls) (g (cdr ls)))))))
(g ls))))))
(f '() (list n m))))とりあえず、自分で作成、は一旦アキラメ。忘れた頃に考えた方が良さげ。append2 のコードは見れば見るほど興味深い。あ、append2 の letrec 版を以下に。
(define append2
(lambda args
(letrec ((f (lambda (ls args)
(if (null? args)
ls
(letrec ((g (lambda (ls)
(if (null? ls)
(f (car args) (cdr args))
(cons (car ls) (g (cdr ls)))))))
(g ls))))))
(f '() args))))段々再帰じゃなくって繰り返しに見えてきてるから不思議だ。
