kb84tkhrのブログ

何を書こうか考え中です

Scheme手習い (4) 計算

第4章「数あそび」では四則演算や比較などを定義しつつ数や数のリストの使い方を学びます

この本で使うSchemeは非常に限定されていて、なんと足し算や引き算も比較もできません
数に関してできるのは1を足す(add1)、1を引く(sub1)、0かどうかを調べる(zero?)だけです 1
関数の構造はいままでとかわりなく、使う関数が変わるだけです

今回は、計算に関する部分をまとめてやってしまいます
本に出てくる順番とは少し変わります

+という関数は普通のSchemeでは定義済みですので、重複を避けてo+という名前で定義します

(define o+
  (lambda (n m)
    (cond ((zero? m) n)
          (else (add1 (o+ n (sub1 m)))))))

null?の代わりにzero?が、consの代わりにadd1が、cdrの代わりにsub1が使われていると思えば
これまでの関数とそっくりの構造です

実行の様子です

(o+ 3 2)
(add1 (o+ 3 (sub1 2)))
(add1 (o+ 3 1))
(add1 (add1 (o+ 3 (sub1 1)))
(add1 (add1 (o+ 3 0)))
(add1 (add1 3))
(add1 4)
5

引き算も同様

(define o-
  (lambda (n m)
    (cond ((zero? m) n)
          (else (sub1 (o- n (sub1 m)))))))

実行の様子

(o- 3 2)
(sub1 (o- 3 (sub1 2)))
(sub1 (o- 3 1))
(sub1 (sub1 (o- 3 (sub1 1))))
(sub1 (sub1 (o- 3 0)))
(sub1 (sub1 3))
(sub1 2)
1

初めて見た時はなんとなく意外な進み方と感じたんですが
考えてみるとこれしかないですね

かけ算

(define o*
  (lambda (n m)
    (cond ((zero? m) 0)
          (else (o+ n (o* n (sub1 m)))))))

途中は少しずつ省略していきます

(o* 12 3)
(o+ 12 (o* 12 2))
(o+ 12 (o+ 12 (o* 12 1)))
(o+ 12 (o+ 12 (o+ 12 (o* 12 0))))
(o+ 12 (o+ 12 (o+ 12 0)))
(o+ 12 (o+ 12 12))
(o+ 12 24)
36

本ではこんな書き方がしてあります

  (o* 12 3)
= 12 + (o* 12 2)
= 12 + 12 + (o* 12 1)
= 12 + 12 + 12 + (o* 12 0)
= 12 + 12 + 12 + 0

数式寄りの書き方ですが言ってることは同じ

この技法は、上のような数を使うものだけでなく、すべての再帰関数に使えます。

これまでもすべて同じようにやってきました

このアプローチを使って正しさを証明するだけでなく、関数を書くこともできます。

どういうアプローチで関数を書こうというのかよくわかりません
数学ぽく正しさを証明するなら数学的帰納法がぴったりですね

(o* n m) が n * m に等しいことを示す。
i) m = 0 のとき、明らかに (o* n m) = n * m = 0
ii) m = k - 1 のとき成り立つとすると (o* n (sub1 k)) = n * (k - 1)
両辺に k を加えると
左辺 = (o+ k (o* n (sub1 k)))
これは o* の定義と見比べると (o* n k) に等しい。
右辺 = k + n * (k - 1) = n * k
したがって (o* n k) = n * k
i)、ii)から 0 以上のすべての m について (o* n m) = n * m が成り立つ。

プログラム書く前にこれを書いてたら
(o* n k) が (o+ k (o* n (sub1 k)))に等しいはず、ってことがわかりますね
そういうアプローチ、ってことでしょうか

さてここで

o*でなぜ0が最終条件行に対する値となるのですか。
0が+に影響しないからです。つまり、n + 0 = nだからです。

0でなければならないのはわかるんですが
「n + 0 = nだからです」というのはいまひとつわかった気がしません

第5の戒律
o+で値を作らんとせしときは、行を終えるときに常に値として0を用うべし。なんとなれば、0を加うるは加算の値を変えぬからなり。
o*で値を作らんとせしときは、行を終えるときに常に値として1を用うべし。なんとなれば、1を掛けるは乗算の値を変えぬからなり。
consで値を作らんとせしときは、行を終えるときに常に値として()を考えるべし。

単位元とかモノイドとか、ほとんど言葉を知ってるだけですがそういう関係なんでしょうね
モノイドだったらどううれしいのか
モノイドクラスが作れるから、とか?
誰か教えてください

ところでconsだけ「考えるべし」となっているのはなんでしょうね
consのときは例外もありうるとか?

さらにべき乗

(define o^
  (lambda (n m)
    (cond ((zero? m) 1)
          (else (o* n (o^ n (sub1 m)))))))

構造は o* とまったく同じ
o* で値を作るときは1からですからね

勢いに乗って o^^ なんてものも定義してみましょうか
o^の値を変えないのは1ですからこうですかね

(define o^^
  (lambda (n m)
    (cond ((zero? m) 1)
          (else (o^ n (o^^ n (sub1 m)))))))

でもべき乗は結合法則が成り立たないからモノイドじゃなかった(無念

> (o^^ 3 0)
1

> (o^^ 3 1)
3

> (o^^ 3 2)
27

> (o^^ 3 3)
7625597484987

たいへんよい増えっぷりです
実際やってみると(o^^ 3 3)は計算が終わりません
なにしろadd1を7625597484987回実行するわけですから
そこでo^の代わりにexptを使いました
これなら一瞬
しかし(o^^ 3 4)はメモリ不足で終了
巨大数の世界の入り口をほんのちょっと垣間見た気がします

次は比較です
二つの数について再帰します

(define o<
  (lambda (n m)
    (cond ((zero? m) #f)
          ((zero? n) #t)
          (else (o< (sub1 n) (sub1 m))))))

(define o>
  (lambda (n m)
    (cond ((zero? n) #f)
          ((zero? m) #t)
          (else (o> (sub1 n) (sub1 m))))))

o=は2通りの書き方で。

(define o=
  (lambda (n m)
    (cond ((zero? m) (zero? n))
          ((zero? n) #f)
          (else (o= (sub1 n) (sub1 m))))))

(define oo=
  (lambda (n m)
    (cond ((o> n m) #f)
          ((o< n m) #f)
          (else #t))))

ほとんど同じですのでo<についてやってみます

(o< 3 2)
(o< 2 1)
(o< 1 0)
#f

(o< 2 2)
(o< 1 1)
(o< 0 0)
#f

(o< 2 3)
(o< 1 2)
(o< 0 1)
#t

正しい結果を出すには(zero? m)と(zero? n)の順番に気をつける必要があります

次は少し趣向を変えて

この関数にふさわしい名前は何ですか。

(define ???
  (lambda (n m)
    (cond ((o< n m) 0)
          (else (add1 (??? (o- n m) m))))))

再帰の仕方も趣向が変わっていますがよく見るとo/です

(o/ 38 12)
(add1 (o/ 26 12))
(add1 (add1 (o/ 14 12)))
(add1 (add1 (add1 (o/ 2 12))))
(add1 (add1 (add1 0)))
3

これで0以上の整数については四則演算・べき乗・大小比較がすべてできるようになりました
部品としては0とzero?、add1とsub1が増えただけです
面白いですね(人によっては


  1. 逆に、add1、sub1は普通のSchemeには定義されていないので別途定義してやる必要があります