第4章は数字に関する関数をどうやって再帰的に書くかという話が中心。
第４章：数字宛てゲーム
add1/sub1
(define (add1 n)
(+ n 1))
(define (sub1 n)
(- n 1))
数に 1 を足す関数と数から 1 をひく関数。
+/-
(define (+ n m)
(cond [(zero? m) n]
[else (add1 (+ n (sub1 m)))]))
(define (- n m)
(cond [(zero? m) n]
[else (sub1 (- n (sub1 m)))]))
足し算と引き算を add1、sub1 を使って再帰的に定義する。
「n に m 回だけ 1 を足す（または引く）」という考え方。
addtup
(define (addtup tup)
(cond [(null? tup) 0]
[else (+ (car tup) (addtup (cdr tup)))]))
tup は数字のみで構成されたリスト。
addtup は tup の要素を足し合わせる関数。
終了条件には null? を使って 0 を返す。
*
(define (* n m)
(cond [(zero? m) 0]
[else (+ n (* n (sub1 m)))]))
足し算を使って掛け算を定義する。
「n を m 回だけ足し合わせる」という考え方。
第１の戒律（改訂版）
【第１の戒律（改訂版）】
アトムのリスト lat を再帰するときは、２つの質問をすべし。すなわち、(null? lat) と else なり。
数 n を再帰するときは、２つの質問をすべし。すなわち、(zero? n) と else なり
第４の戒律
【第４の戒律（改訂版）】
再帰の間は少なくとも１つの引数を常に変化させるべし。
引数は終わりに向けて変化させることを要す。変化する引数は最終条件にてテストすべし。
すなわち、cdr を用いるときは、null? で最終テストし、sub1 を用いるときは、zero? で最終テストせよ
第５の戒律
【第５の戒律】
+ で値を作らんとせしときは、行を終える時に常に値として 0 を用うべし。なんとなれば、0 を加うるは加算の値を変えるぬからなり。
* で値を作らんとせしときは、行を終える時に常に値として 1 を用うべし。なんとなれば、1 を掛けるは乗算の値を変えぬからなり。
cons で値を作らんとせしときは、行を終えるときに常に値として () を考えるべし。
tup+
(define (tup+ tup1 tup2)
(cond [(null? tup1) tup2]
[(null? tup2) tup1]
[else (cons (+ (car tup1) (car tup2))
(tup+ (cdr tup1) (cdr tup2)))]))
両方の tup の要素を足し合わせて新しいリストにする関数。
片方が空リストの場合は、もう片方のリストを返すのがポイント。
>, <, =
(define (> n m)
(cond [(zero? n) #f]
[(zero? m) #t]
[else (< (sub1 n) (sub1 m))]))
(define (< n m)
(cond [(zero? m) #f]
[(zero? n) #t]
[else (< (sub1 n) (sub1 m))]))
(define (= n m)
(cond [(> n m) #f]
[(< n m) #f]
[else #t]))
大なり、小なりも sub1 と zero? のみを使って実装できる。
片方の引数が 0 になるまで 1 を引いていき、最終的には zero? を使って大小を判断する。
expt
(define (expt n m)
(cond [(zero? m) 1]
[else (* n (expt n (sub1 m)))]))
累乗を計算する関数。
/
(define (/ n m)
(cond [(< n m) 0]
[else (add1 (/ (- n m) m))]))
割り算も - を使って再帰的に定義できる。
「m で何回引き算できるか」を使って割り算を定義する。
これはなかなかおもしろい考え方。
length
(define (length lat)
(cond [(null? lat) 0]
[else (add1 (length (cdr lat)))]))
リストの長さを計算する関数。
pick/rempick
(define (pick a lat)
(cond [(zero? (sub1 a)) (car lat)]
[else (pick (sub1 a) (cdr lat))]))
(define (rempick n lat)
(cond [(zero? (sub1 n)) (cdr lat)]
[else (cons (car lat) (rempick (sub1 n) (cdr lat)))]))
リストから対象の要素を除去する関数。
no-nums/all-nums
(define (no-nums lat)
(cond [(null? lat) '()]
[(number? (car lat)) (no-nums (cdr lat))]
[else (cons (car lat) (no-nums (cdr lat)))]))
(define (all-nums lat)
(cond [(null? lat) '()]
[(number? (car lat)) (cons (car lat) (all-nums (cdr lat)))]
[else (all-nums (cdr lat))]))
リストから数を除去する関数と数だけを抽出する関数。
eqan?
(define (eqan? a1 a2)
(cond [(and (number? a1) (number?a2)) (= a1 a2)]
[(or (number? a1) (number? a2)) #f]
[else (eq? a1 a2)]))
同じアトムかどうかを調べる関数。
両方とも数字なら = で比較。片方だけが数字なら偽。それ以外なら eq? で比較する。
片方が数字の場合は eq? を使えないので注意（Eq? の掟）
occur
(define (occur a lat)
(cond [(null? lat) 0]
[(eqan? a (car lat)) (add1 (occur a (cdr lat)))]
[else (occur a (cdr lat))]))
リストの中の該当の要素の数を計測する関数。
one?
(define (one? n)
(cond [(zero? n) #f]
[else (zero? (sub1 n))]))
与えられた引数が 1 かどうかを調べる関数。
マイナスをケアするために、n がゼロかどうかを調べている（ゼロにsub1 するのは違反）
当然、次のようにも書ける
(define (one? n)
(= n 1))
感想
再帰のパターンがだいぶ身についてきた。
