bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

小学生に戻って旅人算(内包表記、遅延評価)

1.旅人算

流水算と似た問題に旅人算がある。旅人算には、①出会うときを求める問題と②追いつくときを求める問題の二種類がある。前者は、離れたところから二人の旅人が相手の方向に歩く場合である。後者は、一人の旅人が先に出発し、別の旅人が先の旅人を追いかける場合である。

ここでは、追いかける場合を考えることとする。また、ここで取り上げる旅人算は、問題も答えも整数となる簡単なものとする。

問題:2分前に出かけた旅人を別の旅人が追いかけるものとする。両者の速度は、先に行った旅人が毎分32メートルで、追いかけている旅人が毎分40メートルであった。(相当にのんびりした旅人である。)

例によって、図を書いてこの問題の本質をつかむ。
f:id:bitterharvest:20141005002954p:plain
上の図で横軸は距離、縦軸は時間を表す。赤の実線は先に出発した旅人がどこにいるかを示す。また、緑の実線は追いかけている旅人がどこにいるかを示す。この二つの線が交わった点が追いついた地点と時間である。時間ごとにどれだけ追いついているのかを示すために、赤の実線を原点に平行移動する。これを赤の破線で示した。縮めた距離は、緑の実線と赤の破線の間であることが分かる。

それでは、この問題の解を求めることとする。問題も答えも整数と制限しているので、時間を1から増やしていって、追いついた距離が最初に離れていた距離と同じになる時間tを内包表記で求める。プログラムは、次のようになる。

[t | t <- [1,2..], 40 * t - 32 * t == 32 * 2]

上記のプルグラムでtは1,2,3,4….と無限に続く数である。その中で、解となる値は一つだけである。しかし、このプログラムは、解が見つかったとしても、無限の整数に対して繰り返すことになる。

そこで、解が一つ見つかったら、それ以上は繰り返さないようにするためには、遅延評価を利用する。遅延評価はHaskellの強力な武器である。これがあるのでHaskellを使っている人も多いのではないかと思う。ここでは、take nという関数を利用する。これはn個を取りだす。今回は1つだけ取り出すので、次のようにする。

take 1 [t | t <- [1,2..], 40 * t - 32 * t == 32 * 2]

この関数を利用すると、「1」以降にある関数、この場合は内包表記、に対して一つだけ値を渡すように要求する。この結果、この内包表記は一つだけ答えを見つけるために計算をし、答えが見つかると計算をやめてしまう。

以下は実行結果である。
f:id:bitterharvest:20141005003038p:plain
この記述は羽田からパリに向かう飛行機の中です。無線LANを用いれば、ブログにできるのだが、無料ではないので、パリでの待ち合わせ時間に無料WIFIを利用して投稿した。世の中、便利になり過ぎて、どこまでも日常が追いかけてきて困ることも多い。