ニューラル株式会社|ハイブリッドOS|File System|ARM|Android|Java|制御システム|オープンシステム

 

技術者コラム

 
フォーム
 
第11回目:Haskellで問題を解く (Part2)
2014-04-27
筆者:村田
 
こんにちは。
 
早速プログラムの続きを書いていきたいと思います。
 
[Haskellでループを書く]
前回のif式では素数で割り切れなかった時の処理が書きづらいので以下のように書き直しました。
 
largePrimeFactorOf x =
   if x `mod` prime == 0 then
     if x `div` prime == 1 then prime
     else undefined
   else undefined
   where prime = head primes
 
次に2つのundefinedの部分ですが最初の方から考えてみます。素数で割り切れたけど商は1でないので、まだ割れるかも?ってことで処理を「繰り返し」たいです。ここが一つ難所です。Haskellの変数は再代入できないので、forやwhileといった関数内で処理を繰り返す方法がありません。そこでHaskellでは再帰を使ってループを書きます。
 
再帰でループを書くとき、以下の2点を考えることがポイントになります。再帰は自分自身を呼ぶわけですが、ただ呼ぶだけなら無限ループになっちゃいますよね。
1. 呼ぶ際には引数の値が変わること。
2. 引数の変化を見てどこかでループを停止させること。(自分自身を呼ばない)
 
今回は素数で割った商を再帰時の引数に与えることで引数が変化します。また商が1の時、これ以上再帰呼び出しせず素数を返すので停止します。これで先程の2点をクリアしてますね。書いてみましょう。
 
largePrimeFactorOf x =
   if x `mod` prime == 0 then
     if x `div` prime == 1 then prime
     else largePrimeFactorOf (x `div` prime) -- 再帰呼び出し
   else undefined
   where prime = head primes
 
なお、この未完成状態でもundefinedのパスを通らないような数ならばテストできます。
 
> :r
> largePrimeFactorOf 8
2
 
[またもやループで悩む]
さて次はもう一つのundefinedです。ここは素数で割り切れなかったので次の素数で割ってみるという処理です。ここもまたループが必要ですね。次の素数を使って繰り返し処理を行いたいのです。ところが今のlargePrimeFactorOfは常に素数配列の先頭(head primes)の素数、つまり2でしか割れません。どげんかせんと・・
 
Hakellの関数は同じ引数で呼ぶと同じ結果しか返りません。「副作用が無いから」、「再代入が無いから」、といった細かい話は置いておいて、ともかく関数の動きを変えるには"外から引数で渡すしか無い"のです。
 
ということで、2以外の素数に変えて割っていくためには、素数を引数に持っていき関数の外から渡すようにしましょう。largePrimeFactorOfに引数を増やしてもいいですが、この関数は問題文に合わせて引数1個で呼びたいのでlargePrimeFactorOfから呼ぶ下請け関数を作りましょう。
 
またまた関数の型から考えます。割られる数と割る素数を引数に与えて、戻り値は問題の答えとなる最大素数でいいでしょう。
 
largePrimeFactorOf' :: Int -> Int -> Int
largePrimeFactorOf' = undefined
 
関数名は末尾にシングルクォート(プライム)を付けてみました。再帰ループのためだけの下請け関数のように、新しい名前のつけづらい関数によく使います。型は引数->引数->戻り値です。
 
元の関数からこの関数を呼び出す部分の処理を書いてみます。良く分からないところはundefinedにしておきましょう。
 
largePrimeFactorOf :: Int -> Int
largePrimeFactorOf x = largePrimeFactorOf' x undefiend --下請け関数を呼ぶ
 
largePrimeFactorOf' :: Int -> Int -> Int
largePrimeFactorOf' x undefined =
  if x `mod` prime == 0 then
    if x `div` prime == 1 then prime
    else undefined
  else undefined
  where prime = undefined
 
undefinedだらけになってしましいました。下請け関数の2つ目の引数は、素数配列のインデックスにしてうまくいきそうです。リストから先頭を取り出すには head primesとしていましたが任意のインデックスで取り出すには primes!!3 のように!!演算子が使えます。ちなみにインデックスは0から始まります。次は一気に書きます。
 
largePrimeFactorOf :: Int -> Int
largePrimeFactorOf x = largePrimeFactorOf' x 0 -- 最初の素数は0番目
 
largePrimeFactorOf' :: Int -> Int -> Int
largePrimeFactorOf' x primeidx =
  if x `mod` prime == 0 then
    if x `div` prime == 1 then prime -- ここが停止条件
    -- 素数で割った商を引数に再帰呼び出し
    else largePrimeFactorOf' (x `div` prime) primeidx
  -- 割られる数はそのままで次の素数インデックスを引数にして再帰呼び出し
  else largePrimeFactorOf' x (primeidx + 1)
  where prime = primes !! primeidx
 
ロードして試してみましょう
> :r
> largePrimeFactorOf 30
5  (2*3*5)
 
> largePrimeFactorOf 99
11 (3*3*11)
 
うまく動いていそうです。次回は素数のリストをちゃんと作りたいと思います。
 
以上