カテゴリ:Haskell( 740 )

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) []


[PR]
by tnomura9 | 2018-11-15 01:13 | Haskell | Comments(0)

List モナド

Haskell ではリストもモナドだ。その意味は、リストにも return 関数と >>= 演算子が適用できるということだ。return 関数の型は a -> M a だ。これは引数を一つ取りそれをモナド値にラッピングして返すことを意味している。例えば return 3 は整数 3 をリストにラッピングして [3] を返す。

Prelude Control.Monad.State> return 3 :: [Int]
[3]

このモナド値は >>= 演算子によって a -> [b] 型の関数に渡して処理することができる。

Prelude Control.Monad.State> return 3 >>= \x -> [x*x]
[9]

[x*x] でリストにするのではなく return (x*x) のように return 関数でモナドにラッピングすることもできる。

Prelude Control.Monad.State> return 3 >>= \x -> return (x*x) :: [Int]
[9]

しかし、これでは要素が1つだけのシングルトンリストしか扱えないように思える。複数の要素をもつリストをどのようにして return 関数で返すことができるだろうか。それは : 演算子を利用することで可能になる。

Prelude Control.Monad.State> 1:2:return 3
[1,2,3]

こうして返された複数要素のリストには >>= 演算子を使うことができる。

Prelude Control.Monad.State> 1:2:return 3 >>= \x -> return (x*x)
[1,4,9]

この場合2乗の操作はリストの全ての要素に対して行われる。これは map 関数と同じ動作だ。

[1,2,3] というリスト書式の値は直接に >>= 演算子に渡すことができる。

Prelude Control.Monad.State> [1,2,3] >>= \x -> return (x*x)
[1,4,9]

このように、リストがモナドであるという意味は return 関数と >>= 演算子が使えるということだ。do 記法はこれらの糖衣構文なので次のように使うことができる。

Prelude Control.Monad.State> do x <- [1,2,3]; return (x*x)
[1,4,9]

State モナドにしても、リストモナドにしてもそれがモナドであるという意味は return 関数と >>= 演算子が使えるという以外の意味はない。しかし、これはリストが IO モナドと同じように do 記法を用いてプログラムできることを意味している。この意味は軽いものではない。例えば次のようなプログラムを書くこともできるのだ。

Prelude Control.Monad.State> :{
Prelude Control.Monad.State| do
Prelude Control.Monad.State| x <- [1,2,3]
Prelude Control.Monad.State| y <- [4,5,6]
Prelude Control.Monad.State| return (x,y)
Prelude Control.Monad.State| :}
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

State モナドにしても、リストモナドにしても、それがモナドである限り do 記法でプログラムすることができる。ただ、それがどのような実際的な意味を持つのかはプログラムの実例をみて学ばないといけないが、なかなかそのような例に出会わない。

それは置いておいてもこれらのモナドを共通の観点から操作出るというのはなかなかおもしろい経験だ。

[PR]
by tnomura9 | 2018-11-13 22:00 | Haskell | Comments(0)

State モナドとモナド型関数

モナドのプログラミングにおいて、>>= 演算子の左右の項には厳しい制限がある。つまり >>= の左項は M a 型のモナド値であり、>>= の右項は a -> M a 型の関数でなくてはならない。このあたりの説明をスタックの pop 関数と push 関数を例にとってやってみる。

Prelude> import Control.Monad.State
Prelude Control.Monad.State> :{
Prelude Control.Monad.State| pop :: State [a] a
Prelude Control.Monad.State| pop = state (\s -> (head s, tail s))
Prelude Control.Monad.State| :}
Prelude Control.Monad.State> runState pop [1,2,3]
(1,[2,3])

つぎに、push 関数だが、これはスタックに積む値を引数に取るので型は push :: a -> State [a] a だ。

Prelude Control.Monad.State> :{
Prelude Control.Monad.State| push :: a -> State [a] a
Prelude Control.Monad.State| push x = state (\s -> (x, (x:s)))
Prelude Control.Monad.State| :}
Prelude Control.Monad.State> runState (push 5) [1,2,3]
(5,[5,1,2,3])

この push と pop を使ってスタックの先頭の要素を 10 倍にしてみる

Prelude Control.Monad.State> runState (pop >>= \x -> return (10*x) >>= push) [1,2,3]
(10,[10,2,3])

これは do 記法で記述したほうがわかりやすい。

Prelude Control.Monad.State> runState (do x <- pop; push (x * 10)) [1,2,3]
(10,[10,2,3])

>>= 演算子の右項に置くべき a -> State s a 型の関数の作り方をやってみた。やや技巧的だが、これがわかれば、State モナドを自由に操ることができるようになる。

State モナドのプログラミングでは上に述べた state 関数で関数をラッピングする方法より、return, get, put, modify 関数などを使って do 記法でプログラムする方法もある。むしろ、こちらのほうがわかりやすいかもしれない。

Prelude Control.Monad.State> :{
Prelude Control.Monad.State| pop :: State [a] a
Prelude Control.Monad.State| pop = do xs <- get; put (tail xs); return (head xs)
Prelude Control.Monad.State| :}

Prelude Control.Monad.State> runState pop [1,2,3]
(1,[2,3])

Prelude Control.Monad.State> :{
Prelude Control.Monad.State| push :: a -> State [a] a
Prelude Control.Monad.State| push x = do xs <- get; put (x:xs); return x
Prelude Control.Monad.State| :}

Prelude Control.Monad.State> runState (push 5) [1,2,3]
(5,[5,1,2,3])

Prelude Control.Monad.State> runState (do x <- pop; push (x*10)) [1,2,3]
(10,[10,2,3])

get, put 関数の動作は汎用的なので、State モナドのプログラミングはこちらを使うほうが王道だろう。


[PR]
by tnomura9 | 2018-11-11 20:50 | Haskell | Comments(0)

状態付き計算と State モナド

計算の結果が状態に依存するようなプログラムを考えてみよう。例えばカウンターの値を表示したあとカウンターを一つ増加させる関数 countUp 関数を考えてみる。countUp 関数が呼ばれると現在のカウンターの値が表示されると同時に状態としてのカウンターの値が一つ増加される。

irb(main):014:0> $count = 1
=> 1
irb(main):015:0> def countUp
irb(main):016:1> print $count
irb(main):017:1> $count += 1
irb(main):018:1> end

しかし、Haskell では破壊的代入ができないので、値と状態を同時に返す関数を作る必要がある。

Prelude> countUp s = (s, s+1)

そうして、countUp 関数を呼ぶたびに引数として状態の値を与えなくてはならない。

Prelude> countUp 1
(1,2)
Prelude> countUp 2
(2,3)
Prelude> countUp 3
(3,4)

State モナドを使えばこのような状態付き関数をもっとスマートに表記できる。この countUp 関数の型は次のようになる。

Prelude> :t countUp
countUp :: Num t => t -> (t, t)

これは State モナドのコンテナの s -> (a, s) と同じ形をしている。そこで state 関数を使ってこの countUp 関数を State モナドにラッピングする。

Prelude> import Control.Monad.State
Prelude Control.Monad.State> monadCount = state countUp

すると monad 化した monadCount 関数を使えばいちいち状態を入力しなくてもカウントアップの動作を行うことができる。

Prelude Control.Monad.State> runState (do monadCount; monadCount; monadCount) 1
(3,4)

不審に思うかもしれないが State モナドの >>= 演算子の動作がこれを可能にしている。State モナドでは >>= 演算子は、左辺のモナド値 State s a の a と現在の状態 s を使って右辺のモナド関数で計算を行い、新しい値と状態のペア (a,s) を State モナドにラッピングして戻り値として返す。したがって、暗黙に状態の値が渡されているのだ。monadCount 関数では明示的な引数の入力はなく状態 s の値だけを利用するので、上のように monadCount 関数を呼び出すたびにカウンタが増加する。

IO モナドの >>= 演算子には状態を利用する性質はないので、State モナドの >>= 演算子の動作は State モナド特有のものだ。モナド共通の >>= の性質に加えて State モナドの特有の >>= の性質が加えられている。このように階層的に演算子の性質をもたせることができるのが、Haskell に多くのモナドが存在する理由のひとつだ。

このように State モナドでは s -> (a, s) 型の関数があれば、state 関数で簡単に State モナドでラッピングすることができる。たとえばスタックの pop 関数は次のように定義できる。

Prelude Control.Monad.State> :{
Prelude Control.Monad.State| pop :: State [a] a
Prelude Control.Monad.State| pop = state $ \s -> (head s, tail s)
Prelude Control.Monad.State| :}
Prelude Control.Monad.State> runState (do pop) [1,2,3]
(1,[2,3])

State モナドの本領はこのような領域で発揮されるのではないだろうか。s -> (a,s) 型の状態のある計算の場合は State モナドを使うことを考えたほうがいいかもしれない。


[PR]
by tnomura9 | 2018-11-11 09:25 | Haskell | Comments(0)

State モナドと >>= (bind) 演算子

モナドの本質はデータ型 M a のデータのコンテナの値を a -> M b 型の関数の引数として >>= 演算子を介して渡すことができるということだけだ。この性質は IO モナドが一番わかり易い。ただし、IO モナドでは IO a のように IO をデータコンストラクタとして使うことができない。IO モナドで IO a 型のデータを作るためには return 関数を使わなければならない。

Prelude Control.Monad.State> :t (return 2)
(return 2) :: (Num a, Monad m) => m a

ここのところを押えておけば、a -> IO b 型の関数を定義するのは簡単だ。例えば次の関数 io1 は Int を引数にとりIO Int 型のデータを返す。

Prelude Control.Monad.State> io x = return (x*x)

この関数へは retrun 2 で作成したデータ IO 2 を>>= 演算子を介して io の引数として渡すことができる。

Prelude Control.Monad.State> return 2 >>= io
4

これは、ラムダ表記を使った無名関数の場合のほうがわかりやすいかもしれない。

Prelude Control.Monad.State> return 2 >>= \x -> return (x*x)
4

驚いたことに、全く同じプログラムが State モナドでも動いてしまう。

Prelude Control.Monad.State> runState (return 2 >>= \x -> return (x*x)) ()
(4,())

このとき、>>= を介して渡されるデータがどのデータかということだが、これは s -> (a, s) のペアの fst 要素だ。(a, s) の snd 要素は、return 2 >>= \x -> return (x*x) のプログラムには現れない。State モナドのプログラムでは状態 s は表に現れず隠蔽されている。

このあたりの事情は IO モナドの場合も同じだ。print x 関数はコンソールに引数 x の値を表示するが、戻り値は IO () だ。コンソールに値を印刷するというアクションは IO () には反映されない。

Prelude Control.Monad.State> return 2 >>= print
2
Prelude Control.Monad.State> :t (return 2 >>= print)
(return 2 >>= print) :: IO ()

IO モナドの print に当たるのが State モナドの put だ。put x 関数も引数 x を状態 s に格納し State s () を返す。

Prelude Control.Monad.State> runState (return 2 >>= put)
((),2)
Prelude Control.Monad.State> :t (return 2 >>= put)
(return 2 >>= put) :: (MonadState s m, Num s) => m ()

IO モナドで隠蔽されているのはコンソールのアクションだが、State モナドで隠蔽されているのは状態の値だ。IO モナドも State モナドもその操作性の上では全く同じ扱いができるのだ。伊達にどちらもモナドではない。

State モナドのプログラムは、IO モナドのプログラムとの類推で論じることができる。IO モナドの getLine 関数はコンソールから文字列を取り出すが、State モナドの get 関数は環境の値を取り出す。IO モナドの print 関数は引数の数値をコンソールに出力するが、State モナドの put 関数は引数の数値を状態に出力する。IO モナドのコンテナのデータは値で、State モナドのコンテナのデータは関数なのでデータの形式は全く異なるように見えるが、その働きを見ると驚くほど似通っている。

IOモナドのプログラムもStateモナドのプログラムも do 記法の中の1行はすべて a -> M b 型の関数でできている。モナドのプログラムとはこのような制限された関数だけを用いたプログラムの技法だ。しかし、その制限を満たせば、IO モナドと State モナドというような全く異なるデータや動作のプログラムを一律にモナドの枠組みでプログラムすることができる。

副作用を隔離した IO プログラムを書くために IO モナドを理解しようとしてきたが、実際はモナドというプログラムの枠組みを理解することのほうがプログラミング技術を考えるのにもっと大切なのではないだろうか。


[PR]
by tnomura9 | 2018-11-10 19:51 | Haskell | Comments(0)

State モナドとモナドの本質

State モナドを理解する前に、モナドの本質について述べてみたい。モナドは元々圏論の概念だが、これを数学者でないプログラマが理解するのは無理だ。そこで、数学者には叱られそうだが、モナドはこういうふうに扱えばプログラムできるというような操作的な理解でその本質を探ってみたいと思う。

モナドのデータはプログラマの立場からは、代数的データ型と捉えることができる。例えば IO モナドのデータ型は IO a である。データコンストラクタ IO のコンテナの中にデータ a が収められているとイメージできる。

また、IOモナドで利用できる関数は a -> IO b の形をしているもののみだ。つまり、a 型のデータ1個を引数としてとり、IO b 型のデータを返す関数だ。結構条件の厳しい関数で、適当な用語がないのでこれをモナド型の関数と呼ぶことにする。このモナド型の関数は bind 演算子 >>= を介して IO a 型のデータから、コンテナ内の a 型のデータを抜き出して受け取ることができる。モナド型の関数は1引数だから、この a 型のデータを処理した後 IO b としてIO b 型のデータを値として戻す。

たとえば IO モナドで retrun "hello" を実行すると IO "hello" が値として戻される。また、putStrLn cs は文字列 cs を引数として受取り、コンソールに cs を表示したあと IO () を値として返す。IO () は単に IO モナド型のデータだが、何らかのアクションを伴ったあとの結果なので、これを action と読んでいるようだ。別に I0() だけでなく、IO "hello" も action だ。要するに IO a 型のデータは全て action なのだ。なぜなら、そのデータは何らかのアクションの結果として戻されるからだ。

理屈はいいので、上の説明を実行してみよう。

Prelude> return "hello" >>= putStrLn
hello

モナドの本質とはこれで全てなのだ。IO a 型のデータを >>= (bind 演算子)を介して a -> IO b 型の関数に与えると、IO a の中から生の a が取り出されそれが a -> IO b 型の関数に渡されることで IO b 型の action が帰ってくる。これがモナドの全てだ。モナドの本質とは IO a と a -> IO b 型の関数が >>= を介して結合できるということだけなのだ。しかし、これは他のモナドにも共通している。Listモナドであれ、Stateモナドであれ、モナドである限りはその本質は M a 型のデータが a -> M b 型の関数に >>= 演算子を介して結合することができる。

したがって、State モナドも上の仕組みが例外なく当てはまる。return a の値である State モナド値 (action) は put x という a -> M b 型の関数と >>= を介して結合させることができる。

Prelude Control.Monad.State> runState (return "hello" >>= put) ""
((),"hello")

M "hello" が状態に格納されたことがわかるが、状態はモナドを扱う上では見えない存在なので、本来の出力は () (ユニット)である。

Prelude Control.Monad.State> evalState (return "hello" >>= put) ""
()

"hello" を値として戻したいときは get をもう一回使って次のようにする。

Prelude Control.Monad.State> evalState (return "hello" >>= put >> get) ""
"hello"

わかりやすい説明ではなかったかもしれないが、IO モナドと State モナドは操作的な点で全く同じなのである。State モナドを扱う際にもこれがモナドなのだという視点を常に持っておくと理解しやすくなる。

>>= 演算子を使ったモナドのプログラミングは少々面倒だ。しかし、>>= 演算子が使えるということは同時に do 記法による手続き型プログラムに似た形式のプログラムが書けることを意味している。つまり、次のようなプログラムが動く。

Prelude Control.Monad.State> do c <- return "hello"; putStrLn c
hello

ということは State モナドも do 記法でプログラムできるということだ。

Prelude Control.Monad.State> runState (do c <- return "hello"; put c; get) ""
("hello","hello")

State モナド関係のプログラムを普通に手続き型プログラムのように書くことができるというのは、便利なことではないだろうか。モナドは Haskell というプログラム言語の中の言語内言語なのだ。モナドのプログラミングは、副作用からの隔離などの議論をおいておいても Haskell という関数言語の中で手続き型言語のプログラムを導入できるという言語内言語だ。

モナドは単に数学的な理論でも、IO の副作用から隔離するためのだけの仕組みではない。それは、Haskell の表現力を飛躍的に拡大させる可能性のある言語内言語なのだ。


[PR]
by tnomura9 | 2018-11-08 23:28 | Haskell | Comments(0)

State モナドの過去記事

Stateモナドについては、このブログの過去記事でも書いていたが、すっかり忘れていた。今読んでも面白かったのでリンクした。


State モナドの使い方を Parsec の使い方の類推で説明している。Parsec を使ったことがなければ分かりにくいかもしれないが、State モナドの基本的な使い方が分かる。State モナドの使い方の例としてスタックを紹介している。また、スタックを使った、逆ポーランド記法のプログラムを紹介している。State モナドでスタックを記述すると、ややこしいことを考えないで済むので楽だ。


State モナド型のデータのデータコンストラクタの中身をのぞいている。そうして、return と >>= (bind 演算子)の実装がどうなっているかを説明している。Stateモナドも実装面から検討するとその動作がなるほどと納得できる。

過去の自分がこういうことをしていたのかとちょっとびっくりした。プログラミングの技術のようなものは、絶えず使い続けないと簡単に後退していくものだと今更ながら思った。

State モナドは使用目的があるはずだが、実例に乏しい。State モナドを利用した実例を集めればもっとよく理解できるかもしれない。

[PR]
by tnomura9 | 2018-11-08 18:13 | Haskell | Comments(0)

State モナド

Haskellで状態を操作するプログラムを作るときは State モナドを使うらしい。State モナドのデータ型は次のようになっている。

newtype State s a = State { runState :: s -> (a, s) }

State モナドのコンストラクタの中身は runState アクセサーのついた s -> (a, s) 型の関数だ。訳がわからないように見えるが、runState アクセサを使うと、データコンストラクタの中身の s -> (a,s) が表に出てくる。たとえば (return 2) モナドに runState アクセサを適用すると s -> (a, s) 型の関数が表に出てくるので状態 1 を与えると (2, 1) というペアが帰ってくる。ペアの fst 要素は return の引数で、snd 要素は s -> (a, s) に与える外部からの状態だ。

Prelude Control.Monad.State> runState (return 2) 1
(2,1)

State モナドの基本的な関数はこのリターン以外に get と put がある。get は snd 要素を取得して fst 要素にコピーする動作をする。

Prelude Control.Monad.State> runState get 1
(1,1)

put は引数を状態に設定する。最初の状態は、put の引数で置き換えられ、fst の値は () に初期化される。

Prelude Control.Monad.State> runState (put 5) 1
((),5)

また、modify 関数は1変数関数を引数にとり、その関数を状態に関数適用する。

Prelude Control.Monad.State> runState (modify (*2)) 5
((),10)

これらのプリミティブな関数は >>= (bind 演算子)で組み合わせることができるので、次のように出力するタプルを操作できる。

Prelude Control.Monad.State> runState (get >>= \x -> put (x*10)) 2-
((),20)

State モナドでは >>= を使うよりも素直に do 記法を使ったほうがわかりやすい。

Prelude Control.Monad.State> runState (do {x <- get; put (x*10)}) 2
((),20)

状態にデータを出し入れしたり、加工したりするコツがだいぶつかめてきたので、状態のリストの先頭の要素を取り出す monadHead モナドを定義してみる。

Prelude Control.Monad.State> :{
Prelude Control.Monad.State| monadHead :: State [Int] Int
Prelude Control.Monad.State| monadHead = do
Prelude Control.Monad.State|   x:xs <- get
Prelude Control.Monad.State|   put xs
Prelude Control.Monad.State|   return x
Prelude Control.Monad.State| :}
Prelude Control.Monad.State> runState monadHead [1,2,3,4,5]
(1,[2,3,4,5])

do 記法の中で、状態を操作するプログラムが手続き型プログラム風に記述できることがわかる。使ってみれば State モナドもそれほど不可思議なものではないような気がしてきた。

[PR]
by tnomura9 | 2018-11-06 22:25 | Haskell | Comments(0)

素因数分解

素因数分解するプログラムを作ってみた。プログラムは次のようになる。primes 関数は素数の列を作る関数で、pfact 関数は第1引数に素因数分解する数を、第2引数に primes を取ると、素因数分解の結果を素数で割る前の数と素数のペアのリストで出力する。

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

pfact 1 _ = []
pfact _ [] = []
pfact n xs =
  let
    p = head xs
  in
    if n `mod` p == 0
    then (n, p) : pfact (n `div` p) xs
    else pfact n (tail xs)

実行例は次のようになる。

*Main> pfact 56 primes
[(56,2),(28,2),(14,2),(7,7)]

56 を 2 で割ると 28 になる、これを2で割ると 14 になる、更に2で割ると7になる。7は prime のリストから 7 を検索してきてこれで割ると残りが1になる。このようにループの中で変化する値を取り扱うのは Haskell では難しい。変数への束縛は1回しかできないからだ。変数へ次々と値を代入して変数の値を変更することは Haskell ではできない。

このようなときは、変数の値を関数の引数として渡す、末尾回帰を利用すればいい。pfact はそのような末尾回帰の関数だ。変数 n の値の変更を、pfact を呼び出すときの第1引数の値の変更として伝えていく。末尾回帰を利用すれば、疑似代入を利用可能にするモジュールを使わなくても、ループの中の変数の代入ができる。

末尾回帰というと難しそうに聞こえるが、値を引数として渡すと考えると良い。次の階乗の計算は末尾回帰を用いている。

*Main> :{
*Main| fact 0 m = m
*Main| fact n m = fact (n-1) (m*n)
*Main| :}
*Main> fact 5 1
120

Haskell の末尾回帰はあまり格好良くはないが、使い勝手がいい場合もある。

[PR]
by tnomura9 | 2018-11-05 23:08 | Haskell | Comments(0)

素数

Haskell.org のホームページに素数を求める関数のコードが表示されていたので真似てみた。

Prelude> primes = filterPrime [2..] where filterPrime (p:xs) = p : filterPrime [x | x <- xs, x `mod` p /= 0]
Prelude> primes100 = take 100 primes
Prelude> primes100
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541]

しかし 541 が本当に素数かどうかわからなかったので、次のコードで約数を求めてみた。

Prelude> [x | x <- [1..42], 42 `mod` x == 0]
[1,2,3,6,7,14,21,42]

Prelude> [x | x <- [1..541], 541 `mod` x == 0]
[1,541]

確かに 541 は素数のようだ。

素数と素数の間隔がどのくらいか気になったので、調べてみた。

Prelude> dif = zipWith (-) (tail primes100) primes100
Prelude> dif
[1,2,2,4,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,6,6,2,10,2,4,2,12,12,4,2,4,6,2,10,6,6,6,2,6,4,2,10,14,4,2,4,14,6,10,2,4,6,8,6,6,4,6,8,4,8,10,2,10,2,6,4,6,8,4,2,4,12,8,4,8,4,6,12,2,18]

間隔の最大値は 18 で最小値は 1 だ。

Prelude> maximum dif
18
Prelude> minimum dif
1

意外と素数の密度は高い。

間隔の平均値は、

Prelude> (fromIntegral (sum dif)) / (fromIntegral (length dif))
5.444444444444445

これは500までの自然数の6個に1個は素数であることを示している。

[PR]
by tnomura9 | 2018-11-02 16:51 | Haskell | Comments(0)