関数型プログラミングの初級問題-33問目- 「素因数分解」
プログラミング初級者が挑戦する関数型プログラミングによる算数の練習問題の第33問です。問題は、OCaml公式ページのものを使いました。
内容は、問題と答案です。答案の作成時間は、約15+5分でした。
問題33.
与えられた正の整数を素因数分解してなるリストを生成する関数factorsを書け。
※ 例えば、factors 18は、[2; 3; 3]になります。
答案
本問の解き方
力業で解きます。
まず、問題29で作成したエラストテネスのふるいにより所与の正の整数以下の素数を求めます。
その際に、所与の正の整数が素数の倍数であるか否かも判定し、倍数であるなら素数をリストに加えます。
これにより、素因数からなるリストが生成されます。
後は、その素因数のリストを基に指数の数だけ素因数を加えて素因数の"flat"リストを生成します。
コード
let factors n =
let rec is_mul m p = if m < n then is_mul (m+p) p else n = m in
let rec exp m p =
if m < n then let l = exp (m*p) p in if is_mul m m then p::l else l
else [] in
let rec sweep m p = function [] -> ((if n != m then [] else exp p p), [])
| head::tail ->
if m = head && n != m then sweep (m+p) p tail
else let (t, rest) = sweep (if m < head then m+p else m) p tail in (t, head::rest) in
let rec sieve = function [] -> []
| head::tail -> let (factor, rest) = sweep head head tail in factor@(sieve rest) in
let rec seq a b = if a < b then a::(seq (a+1) b) else [b] in
match sieve (seq 2 (n-1)) with
| [] -> [n]
| _ as l -> l
関数is_mulは、nがpの倍数であるか否か判定する関数です。
関数expは、指数の数だけ素因数を持つリストを生成する関数です。
関数sweep、関数sieveはエラストテネスのふるいを実装した関数です。
関数seqは、$${[a, b] \subset \Z}$$のリストを生成する関数です。
このアルゴリズムでは、所与の正の整数nをふるい落とさないので、そのnは関数sieveに渡す数列に含めていません。
ただこれだと、所与の正の整数が素数である場合に、factorsの返り値が空リストになってしまいます。
そこで、空リストの場合には(n, 1)のタプルを返すことで帳尻を合わせています。
感想
勘違い
問題を読み間違ってました。
本問は「素因数からなるリスト（重複を許さない）」を生成するものだと思い込んでプログラムを作成してしまいました。
しかし、作成後に、所与の正の整数を素因数分解してなるリスト、つまり「所与の正の整数を素因数の積で表した場合に列挙される素因数からなるリスト」を作成しなければならないことに気がつきました。
その場しのぎ
そこで、急遽、素因数の指数を求めて、その数だけ素因数を列挙する関数is_mulおよび関数expを追加しました。
そのため、関数is_mulと関数sweepとで処理の内容が被っており、気持ちが悪いコードになっています。
言い訳
言い訳をすれば、プログラミングの分野においては、一般に"flat list"と言えば「入れ子になっていないリスト」を指すのではないでしょうか？
べき乗を基数の積で表すことを"flat"と呼ぶとは聞いたことがありませんでした。
（みっともない言い訳です。どんな戦後教育を受けてきたのでしょうか？大人しく上の言うこと聞くようでないと立派な奴隷にはなれませんよ！）
花鏡
次回は、第34問です。
前回から前書きの「初心者が挑戦…」を「初級者が挑戦…」に変えました。何ら向上がみられなくとも時間が経てば人は初心を忘れるものです。なので、もう初心者ではありません。
古往今来得ざれば即ち書き得れば即ち飽くは筆の常也。と云うわけで御座います、この浅ましき乞食めに何卒皆々様のご慈悲をお願い致します。