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] 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)
|
カテゴリ
新型コロナウイルス 主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude Ocaml ボーカロイド 圏論 jQuery デモ HTML Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker ed と sed HTML Raspberry Pi C 言語 命題論理 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||