Project Euler というウェブサイトを知りました。プログラムで数学の問題を解こうというものです。問題文を和訳しているサイトもあります。
せっかく見つけたので最初の 10 問を解いてみました。数学と名乗るので Haskell を使ってみました。 Haskell なら無限桁扱えるので簡単です。 C# でも解いていますが桁数が多い問題があるので int だったり long だったり鬱陶しいです。
検索してみると挑戦しているサイトがいくつかあって，自分の回答を公開しているので私もそれに倣って回答を公開してみます。とりあえず最初の 5 問だけ。
回答の前に汎用性の大きいと思われる関数はモジュール化してあります。とりあえず今のところフィボナッチ数列と素数の無限リストと素因数分解，おまけに素数判定関数です。
fibonacci :: (Integral a) => a -> a -> [a]
fibonacci a b = map (fibonacci' a b) [0 ..]
where
fibonacci' a b n
| n == 0 = a
| otherwise = fibonacci' b (a + b) (n - 1)
primes :: (Integral a) => [a]
primes = 2 : filter isPrime [3, 5 ..]
isPrime :: (Integral a) => a -> Bool
isPrime n = all[A] primes
factorize :: (Integral a) => a -> [a]
factorize n
| n == 1 = []
| otherwise = let p = head [q | q <- primes, n `mod` q == 0]
in p : factorize (n `div` p)
特に変わった実装はしていません。 C# でもほとんどそのまま LINQ で実装可能です。
Problem 1
answer = sum [n | n <- [0 .. 999], n `mod` 3 == 0 || n `mod` 5 == 0]
こういう問題は Haskell の得意分野ですね。とはいえ単純な手続きでも記述できます。
Problem 2
answer = sum $ takeWhile (< 4000000) [n | n <- fibonacci 1 2, even n]
これも簡単ですね。
Problem 3
answer = maximum $ factorize 600851475143
factorize は小さい順に素因数が格納されているので maximum でなく last でも同じ結果になります。
ちなみに C# だと 600851475143 は int に収まりきらないので long を使うことになります。
Problem 4
isPalindromic :: (Eq a) => [a] -> Bool
isPalindromic [] = True
isPalindromic [x] = True
isPalindromic [x, y] = x == y
isPalindromic (x:xs) = x == (last xs) && isPalindromic (init xs)
toDigits :: (Integral a) => a -> [a]
toDigits n
| n == 0 = []
| n < 10 = [n]
| otherwise = (toDigits $ n `div` 10) ++ [n `mod` 10]
-- x, y は対称なので x <= y として良い。
answer = maximum [x * y | x <- [100 .. 999], y <- [x .. 999], isPalindromic . toDigits $ x * y]
toDigits で各桁を格納したリストを作成しています。最初 toDigits の型を
toDigits :: (Integral a, Eq b) => a -> [b]
という風に定義していたのですが，型エラーだったので上記のようにしました。 Integral 同士や Int 同士だと比較できるけど相互には比較できないからですかね。
ちなみに toDigits の代わりに show でも動作します。各桁の数字のリストではなく，各桁の文字のリストで回文チェックを行います。
Problem 5
answer = foldl lcm 1 [1 .. 20]
最小公倍数を求める関数が最初から定義されているのは Haskell ならではですね。ゆえに瞬殺です。
こうやって見るといかにも Haskell 向きの問題でしたね。今後回答を続けていったらまた回答をアップするかもしれませんし，あるいは他の言語や別解をアップするかもしれません。とりあえず第 10 問までは解いているので記事にする予定です。それ以降は未定です。
脚注
- /= 0) . mod n) $ takeWhile ((<= n) . (^ 2 [↩]