星田さんの記事に付いて、です。
取り敢えずはジャブ。
While True のループが不思議だ・・これって無限ループだけど関数内で使った場合はReturnで結果を返した時点で自動で抜けられるって事なんだろうか？
その通り、です。
returnは基本的には関数から脱出する為の機能なので、whileが回ってる最中だろうと何だろうと関数外に値を持って脱出します。
とジャブを終えて。
今回は何つったってこれでしょう。
出先でちょっとSICPを読んでたけど例題の「両替問題」でいきなり分からない。これはムズいわ～・・
うん。ムズい。
ただ、誤解して欲しくないんだけど、これは「この問題がムズい」のであって、再帰がムズいのではない、と言う事だ。
以前書いたけど、
「難しい再帰はある。でもそれを反復で解こうとしたらもっと難しくなる。」
と言った例です。
大体、それをwhileやらforで書いたら簡単に解けるのか?とか言われれば「ちと待てよ」って話になるでしょう。反復で解けそう?
多分メチャクチャメンド臭いコードを「考案」でもしないと手も足も出ないと思う。
だからこれはむしろ再帰を肯定的に捉えるべき例なんです。
逆にこれを見て
「だから見ろよ。再帰は難しいんだ。」
なんつー反応になるなら、そいつは結局トンマなだけ、なんですよね。
ただ、ぶっちゃけて言うと、SICPが何でこんな例をこんな初期段階でぶっこもうと思ったのか分からん。学生を怯えさせるだけなんじゃないか。
そういう意味で言うと、以前言った通り、「SICPの構成のマズさ」を証明してる例になってるとは思います。
こんなのをここでぶっこむ必要なんてないんだ。
ちょっとSICPから問題の箇所を持ってきましょうか。
50セント, 25セント, 10セント, 5 セント, 1セントがあるとして1ドルの両替にはどのくらいの場合があるか. つまり, 金額に対して両替の場合の数を計算する手続きは書けるだろうか.
んでまたこの日本語訳がな〜(苦笑)。「どのくらいの場合があるか」とか一体どういう日本語なんだ、と(笑)。
こう、すんなり読める日本語になってない、ってのがだから「SICPの訳文はクソ」って言われる原因なんだ(笑)。東大の人間が訳したとは思えないわ(笑)。
(あるいは、以前指摘した通り、プログラマは言語中枢でも破壊されてるのか・笑)
いずれにせよ、問題にされてるのは「場合の数」と言う概念。
要するに「何通りあるのか」ってのを訊いています。
ここは日本なんで、次のように考えましょう。
日本だと硬貨の種類は次の6種類があります。
- 1円
- 5円
- 10円
- 50円
- 100円
- 500円
と。
例えば最初にバカバカしい例を考える。
1円硬貨を何円硬貨で両替出来るか、と。
当然1円になるよね。つまり1通り、だ。
- 1円 -> 1円で両替出来る
これは実はどんな貨幣に対する両替でも全く同じです。「全てを1円玉で両替する」なら1通りしか存在しない。
1,000円だったら1円玉1,000個の1パターンしかないし、10,000相手でも1円玉10,000個で両替する1パターンしかない。
次にくるのが5円だ。5円を両替するにはどう言うパターンがあるだろう、と。
- 5円 -> 5円で両替出来る
- 5円 -> 1円玉5枚で両替出来る
この2パターンしかない。2通りだ、と。
ここで2番のパターンを見てみます。これは実は先の「全てを1円で両替出来る」パターンそのもの、なんですね。
そして1番のパターン。実はこれも「どんな金額相手でも」5円玉だけ使おうとする限り1パターンしか存在しない。余りが出ようと何だろうと、1パターンしかないんです。
なんでかっつーと、余りはどっちにせよ1円玉を使うしか「あり得ない」でしょ?だから余りが出ようとどうだろうと「5円玉を中心に両替しよう」とする限り1パターンしかあり得ない。
つまり、ここでの「場合の数」と言うのは、
- 5円玉だけで両替出来る場合の数 + 1円玉だけで両替できる場合の数 = 1 + 1 = 2
になってる、って事なんです。
上の式をちょっと変えると、
- 5円を5円玉と1円玉で両替出来る場合の数 = 5円玉だけで両替出来る場合の数 + 1円玉だけで両替できる場合の数
って事になります。
まぁ、当たり前って言やぁ当たり前ですね。
さて次だ。今度は10円で考える。
10円を10円玉、5円玉、1円玉で両替するパターンを考えると、
- 10円 -> 10円玉で両替できる
- 10円 -> 5円玉二枚で両替出来る
- 10円 -> 5円玉一枚と1円玉5枚で両替出来る
- 10円 -> 1円玉10枚で両替できる
の4通りになる。
結果これは
- 10円玉だけで両替出来る場合の数 + 5円玉だけで両替出来る場合の数 + 5円玉と1円玉で両替出来る場合の数 + 1円玉だけで両替出来る場合の数
と言う事なんですが、次のような分岐に実はなっている。
つまり、形式的には自己再生的な木になってるんです。
次のようなパーツによって再帰的に組み立てられてる。
うむ、ダイアグラム描く方がメンド臭かったな(笑)。
まぁいずれにせよ、下の方で
5 セントと1セントを使って10セントの両替を作る場合を使い, 縮小規則の働きを詳細に調べよ.
ってのはこの事です。ダイアグラムを描いてみれば分かります。
また、
両替が, 最初の硬貨を使わないのと, 使うのの二つのグループに分けられる
ってのも上のダイアグラムを見てみると一発でしょう。
なお、正直言うと、与題のコードのこの部分、
(cond ((= amount 0) 1)
なんつーのは、ハックですよね(笑)。0円両替するなら0通りだろ、とか思うんですが(笑)、再帰を円滑にするためにこういうカタチにしてるみたい。
なお、SICPだとちょっと便利な関数とか使わないで、基本的なヤツだけで書いてる。
例えば
(= amount 0)
なんてのは
(zero? amount)
って書く方が個人的には好きだし、多分そっちの方が明解です。
まぁ、世の中には「とにかくタイピング量を減らしたい」って人もいるんで、完全には賛成を得られませんが、個人的には紛れが無い方が好きです(それがピーター・ノーヴィグ先生の教えです・笑)。
ゼロ判定なんざ良くあるんで、Schemeにはzero?が用意されています。
写経は良い勉強法ですが「ちょっとづつ変える」ように意識しておくと、ただボーッとして打ちっぱなし、って事が避けられるんで学習効果は高いんじゃないかしらん。
例えば件のコードは、日本円に直すと
(define (count-change amount)
(cc amount 6))
(define (cc amount kinds-of-coins)
(cond ((zero? amount) 1)
((or (negative? amount) (zero? kinds-of-coins)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(case kinds-of-coins
((1) 1)
((2) 5)
((3) 10)
((4) 50)
((5) 100)
((6) 500)))
みたいに書き換えられますね。
(< amount 0)
なんてのも
(negative? 0)
と書けますし、そっちの方がzero?と同じく明解でしょう。
あと、SICPにはどういうわけか一回も出てこないんですが、first-denomination内の条件分岐なんかはcase構文使った方が明解だし短く済むでしょう。
(case ⟨key⟩ ⟨clause1⟩ ⟨clause2⟩ . . . ) 構文
構文: ⟨key⟩ は任意の式を指定できます。それぞれの⟨clause⟩
は以下の形です。
((⟨datum1⟩ ...) ⟨expression1⟩ ⟨expression2⟩ ...)
ただしそれぞれの⟨datum⟩ は何らかのオブジェクトの外部
表現です。式の中に同じ⟨datum⟩ がふたつ以上ある場合は
エラーです。また⟨clause⟩ には以下の形も指定できます。
((⟨datum1⟩ ...) => ⟨expression⟩)
最後の⟨clause⟩ は以下のいずれかの形を持つ「else 節」にで
きます。
(else ⟨expression1⟩ ⟨expression2⟩ ...)
(else => ⟨expression⟩)
意味論: case 式は以下のように評価されます。⟨key⟩ が評
価され、その結果が各々の⟨datum⟩ と比較されます。⟨key⟩
の評価結果が⟨datum⟩ と等しい(eqv? の意味で; 6.1 節を
参照) 場合、対応する⟨clause⟩ 内の式が順番に評価され、そ
の⟨clause⟩ の最後の式の結果がcase 式の結果として返され
ます。
⟨key⟩ の評価結果がどの⟨datum⟩ とも異なる場合、else 節が
あればその式が評価され、その最後の結果がcase 式の結果
になります。そうでなければcase 式の結果は規定されてい
ません。
選択された⟨clause⟩ またはelse 節が => 代理形を使っている
場合、まず⟨expression⟩ が評価されます。その値がひとつの
引数を受け取る手続きでなければエラーです。⟨key⟩ の値に
対してその手続きが呼び出され、その手続きが返した値が
case 式から返されます。
(case (* 2 3)
((2 3 5 7) ’prime)
((1 4 6 8 9) ’composite)) =⇒ composite
(case (car ’(c d))
((a) ’a)
((b) ’b)) =⇒ 規定されていない
(case (car ’(c d))
((a e i o u) ’vowel)
((w y) ’semivowel)
(else => (lambda (x) x))) =⇒ c
なお、これで1,000円を両替すると、なんとそれは248,908通りもの両替方法がある、ってぇんでビックリする。
SICPだと1ドルの時、「292が計算されるまで, かなり時間がかかる.」って脅してるんだけど、それは80年代のタイムシェアリングのミニコンだとか、90年代のPCないしはワークステーションの話。
今のパソコンだと一瞬で計算が終わります。
反面、1,000円の両替は今でも結構時間がかかりますよ(笑)。
