１．重要な概念
Haskellの良いところは、簡単にプログラムが書けること。実現するプログラムの意味するところが分かれば、そのまま記述すればよい。JavaやCなどの命令型プログラミング言語ではそうはいかない。意味するところを分析しそれを手順として示さなけらばならない。そのため、プログラム化する価値が見いだせない場合には、プログラムを書こうという気にはなかなかなれない。
それに反して、Haskellはその意味をそのまま書けばいいので、大抵のものはほんの数行で表すことができる。このため、書き留めるつもりでプログラム化できる。今回の話題は、最大公約数と最小公倍数である。中学校の時に学んだので、数学の概念としては、それほど大したことではないと感じられていると思うが、実はそうではない。現代数学の中で最先端を行く圏論(category theory)の入門書では、最大公約数、最小公倍数という言葉ではなく、limit,colimitという専門用語で表現されているものの、この概念の説明にかなりのページを割いている。
そこで、数学の概念として、とても重要な最大公約数と最小公倍数を求めることを考える。
２．最大公約数
二つの整数\(a,b\)があったとき、両方を割る整数の中で最大のものが最大公約数である。従って、整数\(a,b\)の中から小さいほうの整数を取り出し、その整数から始めて１までの整数の中で、最初に両方の整数\(a,b\)を割る整数が求めるものである。従って、プログラムは次のようになる。
gcd' a b = head [ x | let c = min a b, x <- [c,c-1..1], mod a x == 0 && mod b x ==0]
ここで、mod a xはaをxで割った時の剰余を示す。従って、剰余が0の時、割り切れることを意味する。
３．最小公倍数
二つの整数\(a,b\)があったとき、両方の倍数の中で最小のものが公倍数である。従って、整数\(a,b\)の中から大きいほうの整数を取り出し、その整数から始めて大きいほうに進め、最初に両方の整数\(a,b\)の倍数となっている整数が求めるものである。従って、プログラムは次のようになる。
lcm' a b = head [ x | let c = max a b, x <- [c,c+1..], mod x a == 0 && mod x b ==0]
上記のプログラムは、もし、headがないとすると大変なことが起こる。headがないと、両方の数の倍数をずっと出し続ける。しかし、headがあると最初の部分しか計算しないので、答えがすぐに得られ、プログラムは瞬時に終了することになる。必要になるまで計算しないことを遅延評価と呼んでいるが、この遅延評価があるおかげでHaskellのプログラムはとても書きやすくなっている。
