人気ブログランキング | 話題のタグを見る

State モナドと素因数分解

Stateモナドで素因数分解プログラムを作ってみた。まずは素数生成器の primes をプログラムした。

Prelude> primes = sieve [2..] where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
Prelude> take 10 primes
[2,3,5,7,11,13,17,19,23,29]

次に、整数を割り切る一番小さい素数を求める関数 factor を定義した。

Prelude> factor x = head $ dropWhile (\y -> x `mod` y /= 0) primes
Prelude> factor 35
5

factor で次々に整数を割っていけば素因数分解ができるので、素因数分解をする関数 factorize を作ってみた。末尾再帰にすれば、第2引数を状態代わりに使うことができる。

Prelude> {factorize 1 xs = xs; factorize x xs = let y = factor x in factorize (x `div` y) (y:xs)}
Prelude> factorize 35 []
[7,5]

これで素因数分解のコツがわかったので、State モナドを使った素因数分解プログラムに挑戦してみた。

Prelude Control.Monad.State> {mfactorize :: Int -> State [Int] Int; mfactorize 1 = return 0; mfactorize x = let y = factor x in do z <- get; put (y:z); do mfactorize (x `div` y)}
Prelude Control.Monad.State> runState (mfactorize 215) []
(0,[43,5])

この程度のプログラムなら状態を保存するのにわざわざ State モナドを使わなくても末尾再帰の引数に状態をもたせたほうがわかりやすいプログラムになる。

上のプログラムはコンソールで対話的に開発したので少々見づらい。ファイルに作成して整形してみた。

import Control.Monad.State

primes = sieve [2..]
    where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

factor x = head $ dropWhile (\y -> x `mod` y /= 0) primes

factorize' 1 xs = xs
factorize' x xs =
    let y = factor x
    in factorize' (x `div` y) (y:xs)

factorize x = factorize' x []

mfactorize' :: Int -> State [Int] Int
mfactorize' 1 = return 0
mfactorize' x =
    let y = factor x
    in do
        zs <- get
        put (y:zs)
        do mfactorize' (x `div` y)

mfactorize x = execState (mfactorize' x) []


by tnomura9 | 2018-11-15 01:13 | Haskell | Comments(0)
<< モナドの制御構造 List モナド >>