2520は1から10までの全ての数で割り切れる最小の数である。 1から20までの全ての数で割り切れる最小の数を求めよ。
問題文にそって考えていく。割り切れるということは答えの数の素因数には1か ら20の数の素因数が全て含まれている。また求めるのは最小の数ということで 答えの数には必要最低限しか素因数が含まれていない。よって1から20の数を全 て素因数分解し、必要な素因数の積を求めることで答えが求まることがわかる。
まず1から20までのリストを生成する。次に問題3で定義したprimeFactorizeを 用いて素因数のリストを求める。map関数はリストの全ての要素に指定した関数 を適用する関数である。map関数を用いてprimeFactorizeを適用するが、 primeFactorizeでは対象となる数を1番目の引数に、素数のリストを2番目の引 数に渡す必要がある。
ここでHaskell風のやり方としては、まずflip関数を用いてprimeFactorizeの引 数の順序を入れ替えることができる。次に変化しない引数である素数のリスト を先に渡してしまうことができる（関数の部分適用）。これをmapで適用するこ とで、1から20の数の素因数を求めることが出来る。なれてないと若干読みづら いかもしれない。同じ操作を無名関数を用いて書くとmap (\x -> primeFactorize x primes) [1..20]という風にかける。
リストの全ての要素の積はproduct関数で求められる。必要最低限の素因数を求 める部分はローカル関数mergeで定義する。whereという構文はその文で使って いる変数をローカルに定義できる。数学的な文章をイメージするとわかりやす い。例えばここではeuler005という関数でmergeというものを使用し、次に where構文を用いてmergeの内容を定義している。
関数の定義自体はパターンマッチを利用し、片方のリストが空の場合はもう一 方のリストのみを返している。空ではない場合は小さいほうから順番に比較し ていき、同じ数の場合その個数が多いほうと同じになるようになっている。例 えば素因数に2が一つずつ含まれるリストをmergeした場合結果のリストには2が 一つ含まれるが、2が一つ含まれるリストと2が二つ含まれるリストをmergeした 場合結果のリストには2が二つ含まれる。これで二つの素因数のリストから必要 最低限の素因数のリストが求まる。
foldlはリストの要素に左から順番に関数を適用していく関数である。ここでは 初期値として空リスト使い、素因数のリストに順番にmerge関数を適用し、最終 的にすべての素因数のリストをmergeしたものが得られる。
euler005 = product $ foldl merge [] $ map (flip primeFactorize primes) [1..20]
where merge x [] = x
merge [] y = y
merge (x:xs) (y:ys)
| x == y = x : merge xs ys
| x < y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys
上記のプログラムで答えを求めることはできるが、問題をもう一度見直してみ ると、問題文は回りくどい書き方をしているが、実際には1から20の最小公倍数 を求める問題であることがわかる。幸運にもHaskellには最小公倍数を求める 関数lcmがあるので、それを利用して次のように非常にシンプルにプログラムが かける。
euler005 = foldl lcm 1 [1..20]