「ゴールドバッハ予想」：関数型プログラミングの初級問題-38問目-（1分）
素数についての練習問題と答案です。問題は、OCaml公式ページのものを使いました。答案の作成時間は、約1分でした。
問題38.
ゴールドバッハ予想によれば、2を越える任意の偶数は二つの素数の和として表すことができる。
$${\vdots}$$
（出題者によるありがたい薀蓄）
$${\vdots}$$
所与の（4以上の）偶数nに対し、n=p+qを満たす素数p, qからなるタプルを生成する関数goldbachを書け。
※ 例えば、goldbach 34は、(3, 31)になります。
答案
本問の解き方
前回の答案で作成した関数all_primesにより力業で解きます。
具体的には、以下の処理1から4を行います。
1. 関数all_primesにより素数のリストを生成する
2. 素数リストの要素を一つずつ順番に選ぶと共に（外側ループ）、その要素と素数リストの各要素との和を求める（内側ループ）
3. 和が所与の偶数と一致するまで2の処理を繰り返す
4. 一致した場合は、和を構成する要素からなるタプルを返し、全て一致しない場合は例外を発生させる
コード
let all_primes a b =
let rec sweep m p = function [] -> []
| head::tail ->
if m = head then sweep (m+p) p tail
else head::(sweep (if m < head then m+p else m) p tail) in
let rec sieve = function [] -> []
| head::tail -> head::(sieve (sweep head head tail)) in
let rec seq a b = if a < b then a::(seq (a+1) b) else [b] in
sieve (seq a b)
----------------------------------------------------------------------------
let goldbach n =
let rec loop2 =
let rec loop1 m = function [] -> []
| head::tail -> if n = m+head then [(m, head)] else loop1 m tail in
function
| [] -> raise (Failure "goldbach")
| head::tail as lst -> match loop1 head lst with
| [] -> loop2 tail
| head::_ -> head in
loop2 (all_primes 2 n)
点線から下が今回の答案で書いたコードです。
感想
今回の問題を解くのは簡単でしたが、関数に名前を付けるのに苦労しました。
関数型プログラミングでは、繰り返し処理は必ず関数として書かなければなりません。
しかし、単なる繰り返し処理に名前など付けようがありません。プログラミングスタイルの都合で関数にしているだけで本来は分割すべき処理ではないのですから。
結局は、意味のある名前を付けるのは諦めて'loopN'にしました。気持ち悪いですが仕方ありません。
次回は、第39問です。算数の問題もいよいよ大詰めです。算数は苦手ですがあと少しだけなら頑張れなくもないです。
古往今来得ざれば即ち書き得れば即ち飽くは筆の常也。と云うわけで御座います、この浅ましき乞食めに何卒皆々様のご慈悲をお願い致します。