星田さんの記事に関するコメント。
Vectorの入れ子内を探索して（ｘ．ｙ）という形で返す関数作成に取り掛かる。(vector-ref深 (vector-ref浅) k)という形で入れ子にアクセスできるということだから・・なんとなくdo構文を使ったら行けるのでは？と。
うん、まずは最初にフツーに再帰で考える。
doは場合によっては強力なんだけど、この問題の場合には適さない、と考えた方が良い。
何故なら最終的に得られる結果が二種類あるから、だ。
- 座標が見つかった場合
- 座標が見つからなかった場合
そう、必ずしも値が二次元ベクタ上にある、とは限らないからだ。
その場合の「エラー」をどう記述するのか、と言うのを考えておかないとならない。
doは原則的に状況によって返り値を分けられない。
従ってまずはフツーに再帰する、方が式の組み立て法としてはフォーマットに頼らないから柔軟なのだ。
そして次に材料を考える。
二次元ベクタを扱う以上、「外側のベクタ」の長さ、そして「内側のベクタ」の長さは情報として必要になるだろう。
従って、関数dsv(deep-search-vectorの略?)は次のようにして書き始める。
(define (dsv x vec)
(let ((m (vector-length vec))
(n (vector-length (vector-ref vec 0))))
そして再帰する。名前付きletの出番だ。
(define (dsv x vec)
(let ((m (vector-length vec))
(n (vector-length (vector-ref vec 0))))
(let loop ((i 0) (j 0))
座標をiとjとする。そしてここで分かるのはiの最大値がm、jの最大値がnだと言う事だ。
まず目的とする値が与えられた二次元ベクタに含まれなかった場合を考えよう。
その時、一体どういう状態になっているのか?
クソマジメに考えるとiがmになり、jがnになる場合である。要するに、iとjが与えられた二次元ベクタのサイズを超えた場合、検索が失敗した、と言う事になる。
しかしこれは半分はクソマジメ過ぎる。iが外側のベクタの要素番号、jが内側のベクタの要素番号だとすれば、注目すればいいのは外側のiだけになる。
従って、終了条件その1を考察すれば次のようになる。
(define (dsv x vec)
(let ((m (vector-length vec))
(n (vector-length (vector-ref vec 0))))
(let loop ((i 0) (j 0))
(cond ((= i m) #f) ; 失敗
取り敢えず失敗したら偽値の #f を返してみる。
次は成功パターンを考える。(list-ref (list-ref vec i) j)が引数xと一致すればイイわけで、これは簡単である。
(define (dsv x vec)
(let ((m (vector-length vec))
(n (vector-length (vector-ref vec 0))))
(let loop ((i 0) (j 0))
(cond ((> i m) #f)
((= x (vector-ref (vector-ref vec i) j)) `(,i ,j)) ;性交成功
さて、二次元配列が一般にプログラミング初心者を混乱させる、っつーのはどの言語でも同じであり、Lispも例外ではない。
結局、外側のループと内側のループの「関連性」がピンと来ないから、である。
原則的な話をすると、大体のケースとしては、
- 内側のカウンタが最大値に到達して初めて外側のカウンタが1増える(そして内側のカウンタが0に戻る)
となる。
そしてこれを初心者用教科書は全く丁寧に説明しない。っつーか説明してるのを見た事がない。
殆ど全部が全部、「単一のfor」は丁寧に説明するんだが、二次元配列に関しては全く説明せず、「既に所与の知識」として流す。
だからプログラミング初心者の50％以上はここで蹴躓くのだ。
プログラミング初心者が勘違いするのは大体のケースで、
- 内側のカウンタと外側のカウンタが同時に更新される
かどうか知らんのだ。答えは「更新されない」のだが、大体がどっちだか分からず混乱する。そして勘が良いヤツは残り半分いて「流す」。真に「動き」をこの時点で理論的に理解出来るヤツは初学者の25％にも満たないだろう。
そして「内側のカウンタと外側のカウンタが同時に」更新されるのが必要になるケースも当然あるし、その時の二次元平面上の「点の動き」がどうなるのか、あるいはそれをどう書くのか、真にこの時点で理解出来るヤツは恐らく初学者の5%にも満たない。それが実態である。
ハッキリ言うと、この時点での事を教科書でキチンと説明すれば済む話なんだけど、それをやらない。やらない上で「論理立てて考えれば〜」とか寝言言ってるのがプログラミング教育、及びプログラマである。
こんなもん、教科書で教えとけば済む話であって、論理性もクソも関係ないのだ。
枠を配列に見立てた時「走査」をどうするか図示したもの。二次元配列を対象とする場合、こういう「イメージ」を持つことが大事である。殆どのケースでは「虱潰しに」探して行く事が要求され、つまり横を全部調べてから縦が「更新」される。その時点で横の座標が0にリセットされるわけだ。一方、縦と横が「同時に」更新されると全座標虱潰しではなく、単純に対角線上を走査して行く事になる。これも「必要になるケースはある」けど初心者用テキストではまず出てこないケースである。
幸い、Schemeにはforがない。従って、上の図での「走査の概念」を「理論的に」そのまま書かなアカン。結果forなんぞ使ってるクソグラミング言語(主にCだ)と違って、「どういう仕組みになってるのか」把握しやすい。
単純に「横が臨界値に達した時、縦が更新される(そして横が0になる)」である。これをLisp語(つまり神の言語だ・・・・・・・イッちゃったLisperに言わせれば・笑)に直すとcond節内だと
((= j n) (loop (+ i 1) 0))
となる・・・これだけ、だ。
つまり、ここまでで
(define (dsv x vec)
(let ((m (vector-length vec))
(n (vector-length (vector-ref vec 0))))
(let loop ((i 0) (j 0))
(cond ((= i m) #f) ; 失敗
((= j n) (loop (+ i 1) 0)) ; 横が臨界値に達した時、縦が更新される
((= x (vector-ref (vector-ref vec i) j)) `(,i ,j)) ;性交成功
となる。
なお、ここで順番が若干入れ変わってるのは、条件分岐の優先順位のせいである。
残りは「横が臨界値に達してない時」である。これは要するに素直に横を更新すれば良い、と言う事だ。上の図で言うと横の矢印の動きである。
Lisp語(イカれたLisperに言わせれば神の言葉)で翻訳すると、この場合、
(loop i (+ j 1))
である。これで全てのケースが列挙出来た。
従って、完成形は
(define (dsv x vec)
(let ((m (vector-length vec))
(n (vector-length (vector-ref vec 0))))
(let loop ((i 0) (j 0))
(cond ((= i m) #f)
((= j n) (loop (+ i 1) 0))
((= x (vector-ref (vector-ref vec i) j)) `(,i ,j))
(else (loop i (+ j 1)))))))
になる。
上の写真を見て分かる通り、
(define v1 (vector (vector 8 7 9) (vector 1 2 4)))
として、7を探すとその位置(0, 1)をリストとして返してくれてるのが分かる。
また、そこに含まれない3を渡すと
と、キチンと「失敗した」と教えてくれる。
でもやっぱdoを使いたい、って思うかもしれない。
しかしdoの問題点と言うのは、まずは終了条件を二つ用意出来ない事である。
上のnamed-letによる末尾再帰を見れば分かるが、終了条件が二種類必要になる。
では仮にdoを使うとすればどっちを「結果」として採用すればいいのだろうか。
実は「失敗」の方である。
と言うのも前提としてどっちみち二次元配列を「最後まで」走査するのが条件となるから、だ。
ロジックは取り敢えず再帰版を鑑みるとこうなる。
(define (dsv s vls)
(let ((m (vector-length vls))
(n (vector-length (vector-ref vls 0))))
(do ((i 0 (if (= j n)
(+ i 1)
i))
(j 0 (if (= j n)
0
(+ j 1))))
((= i m) #f))))
まず
- 受け取ったベクタのサイズを確定すること
これは脱出条件や何やを考えると必須になる。
もう二つも再帰版から伺えて、
- 二次元配列を相手にする限り、カウンタは二つ必要になること
- カウンタ二つの更新条件をしっかり考えること
なのだが、実はdoで書くと後者が面倒臭い。
doは極めて高機能なのだが、高機能であるが故の弱点がある。
そしてdoのカウンタの性質をキチンと知らないとならない。
doが極めて優秀なのは
- いくつでも好きなだけカウンタを作れる
- ただし、カウンタは互いに独立してて、言わば並列で回せる
と言う辺りだ。
前出の図で言うと「二次元配列の対角線移動」の方がむしろ得意な形式なのである。
従って、今回のような「二次元配列の要素を虱潰しに調べる」場合、カウンタの更新方法でひと工夫しなければならない(※1)。
そして実はまだポイントがある。
それはdoの「本体」と言われる部分だ。
doの「本体」は仕様で書かれてる<command>...の事。
通常、Scheme好きはdoを使っても「本体無しのdo」と言う形式を好む。大体、カウンタ「だけでの」処理を好むのだ。
大体、doの本体は通常「破壊的操作」や「副作用目的」の為に使用する。
しかし、今回のケースでは返り値に「成功のケース」を必要とする。
こういう場合どうするか。
一つの方法としては
- do本体で「成功」があるかどうかチェックする
- 「成功」が存在した場合、それをリスト化して全ての計算から「脱出」する
と言うテがある(※2)。
そしてSchemeで「計算からの脱出」を司るのが継続機能、つまりcall/ccである。
要するに目的としては、引数sが指定する数、が与えられた二次元ベクタvlsに含まれてた時、全計算を中断して脱出するのだ。
それはこうやって書く。
(define (dsv s vls)
(call/cc ; ここで脱出を予定する
(lambda (return) ; 継続を受け取る変数名をreturnとする
(let ((m (vector-length vls))
(n (vector-length (vector-ref vls 0))))
(do ((i 0 (if (= j n); カウンタの更新を工夫する
(+ i 1)
i))
(j 0 (if (= j n); カウンタの更新を工夫する
0
(+ j 1))))
((= i m) #f)
(when (and (< j n) (= s (vector-ref (vector-ref vls i) j)))
(return `(,i ,j)))))))) ; 条件を満たしたら全体から脱出する
こう言う「脱出と言う形式」はcall/ccを使いまくるパターンなんで、「形式」として覚えておいて良いと思う(※3)。
上のコードで注意事項は一つ。
先にも書いたがdoではカウンタ同士は現時点での互いの値を知りえない。しかし前回の値は知ることが出来る。
従って値jにはある意味「空白の時間帯」が存在する。そう、jには与えられた内側のベクタの「長さ(n)」を超える瞬間がどうしても生じるのである。
そして、それがiの更新タイミングを左右してるのでどーしよーもない。
従ってjがnを超えた一瞬だけ関数vector-refを無視したい。そのためだけに、do本体のwhen節に(and (< j n...と言う論理式を挿入している。= j nの瞬間だけ偽が返りその後ろのvector-refが動かないようになるのだ。
というのがdoを使う際の考え方やコツである。
※1: カウンタの並列更新が可能、と言う意味は「現時点でのカウンタ同士」ではお互いの値を知りようがない、と言う事である。参照出来るのは「前回の値」だけである。
こう考えると不便なように思えるが、一方、「カウンタ同士に優先順位がない」「全てのカウンタが平等である」と言う事である。つまり、「カウンタを置く順番を気にせずに良い」と言う事なのだ。
ANSI Common Lispでは「現時点のカウンタの値を参照出来る」do*と言うマクロが用意されている。しかし、「現時点の値を参照出来る」と言うのは順序に従う。つまりカウンタa、b、c、・・・と並んでた場合、aは「参照されるだけ」、bは「aを参照可能だがcは参照出来ない」、cは「aもbも参照可能」・・・となるが考え方は複雑化するかもしれない。しないかもしれない。
※2: お題としては「一意で決まったポジションを返す」と言う前提なので「計算中止」->「脱出」と言うプロセスを提案したが、「いくつでも良い」と言うのなら話が変わってくる。
と言うかLispではもっと簡単になるだろう。
(define (dsv s vls)
(let ((m (vector-length vls))
(n (vector-length (vector-ref vls 0))))
(do ((i 0 (if (= j n)
(+ i 1)
i))
(j 0 (if (= j n)
0
(+ j 1)))
(ls '() (if (and (< j n) (= s (vector-ref (vector-ref vls i) j)))
(cons `(,i ,j) ls)
ls)))
((= i m) ls))))
つまり、第3のカウンタとして初期条件が空リストであるカウンタlsを用意して、条件を満たした時に座標リストをconsする。
そうすれば、もし指定した数を持つ座標があった場合、いずれにせよ「座標リストのリスト」が返ってくるし、見つからなかった場合は単に空リストが返るだろう。
そしてこの形式が本文で触れた「本体が無い」doである。
※3: この「脱出」方法は高階関数なんかとも相性が良く、強力である。
例えばリストにゼロが含まれるかどうか判定するcontains-zero?と言う関数を書いてみる。
(define (contains-zero? ls)
(call/cc
(lambda (return)
(when (map (lambda (x)
(if (zero? x)
(return #t)
x)) ls)
#f))))
キモはmapだが、mapは原則、与えられたリストの最後まで走査する。
しかし、この関数は0がリスト内にあるかどうか調べるのが使命で、逆に言うと、1個でも0が見つかった時点で終了して構わないのである。
こういうケースの場合、与えられたリストのケツまで走査するのが吉、とはならない。要するに、0の1個目が見つかった時点で「#tを抱えて」脱出するのが吉なのである。そうすれば無駄な計算コストがかからない。
mapなんかの高階関数でもラムダ式に継続を仕込めば、条件さえ満たせば計算途中だろうと脱出が可能で、call/ccのパターンとしては本文中のパターンと全く同じである。
逆にここでは、mapでリストのケツまで走査した、と言うことはリストの中にゼロが無かったと言うこと。そしてmap自体がリストを形成するわけだが、Schemeでは基本、#f以外は全部#tなので当然mapが形成したリストも真偽値で言うと#tとなる、のがLispの論理学である。
結果when節が発動し、ゼロが見つからなかった場合は#f、と相成るのである。
