読者です 読者をやめる 読者になる 読者になる

bitterharvest’s diary

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

Haskellで最大公約数、最小公倍数を求める

1.重要な概念

Haskellの良いところは、簡単にプログラムが書けること。実現するプログラムの意味するところが分かれば、そのまま記述すればよい。JavaやCなどの命令型プログラミング言語ではそうはいかない。意味するところを分析しそれを手順として示さなけらばならない。そのため、プログラム化する価値が見いだせない場合には、プログラムを書こうという気にはなかなかなれない。

それに反して、Haskellはその意味をそのまま書けばいいので、大抵のものはほんの数行で表すことができる。このため、書き留めるつもりでプログラム化できる。今回の話題は、最大公約数と最小公倍数である。中学校の時に学んだので、数学の概念としては、それほど大したことではないと感じられていると思うが、実はそうではない。現代数学の中で最先端を行く圏論(Category Theory)の入門書では、最大公約数、最小公倍数という言葉ではなく、Limit,Colimitという専門用語で表現されているものの、この概念の説明にかなりのページを割いている。

そこで、数学の概念として、とても重要な最大公約数と最小公倍数を求めることを考える。

2.最大公約数

二つの整数\(a,b\)があったとき、両方を割る整数の中で最大のものが最大公約数である。従って、整数\(a,b\)の中から小さいほうの整数を取り出し、その整数から始めて1までの整数の中で、最初に両方の整数\(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の時、割り切れることを意味する。

3.最小公倍数

二つの整数\(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のプログラムはとても書きやすくなっている。