タイダログ

もっと怠けますか? (y/n)

F# で素数判定と素因数分解をする

F# を始めました。新しい言語で最初にすることと言ったらやっぱりあれですよね。素数判定と素因数分解です。Hello, World! しても面白くないので。

投稿日の 20211127 は素数です。

作業環境

関数型プログラミングを始めるにあたって意識したこと

  • 変数の再代入はしない
  • 再帰関数を使う

そうすること自体が目的ではないのですが、関数型の特徴らしいのと、たしかにメリットがありそうなので、上の2点を意識しました。

素数判定

完成形

以前の PowerShell のコードを書き換えました。ほぼ同じ考え方でできました。

taidalog.hatenablog.com

let oddNumbersThreeToSqrt x = 
    [3..System.Math.Max(3, int(System.Math.Sqrt(float(x))))]
    |> List.filter (fun x -> x % 2 = 1);;


let isPrime number =
    if number < 2 then
        false
    elif number = 2 then
        true
    elif number % 2 = 0 then
        false
    else
        oddNumbersThreeToSqrt number
        |> List.filter ((fun x y -> y < x) number)
        |> List.filter ((fun x y -> x % y = 0) number) = [];;


let isPrime2 number =
    match number with
    | var when number < 2 -> false
    | var when number = 2 -> true
    | var when number % 2 = 0 -> false
    | _ -> oddNumbersThreeToSqrt number
        |> List.filter ((fun x y -> y < x) number)
        |> List.filter ((fun x y -> x % y = 0) number) = [];;

使い方

isPrime 60;;
// val it: bool = false

説明

oddNumbersThreeToSqrt は、 int の引数 x を取り、int list を返す関数です。リストの中身は、3から \sqrt{x} までの奇数です。\sqrt{x} が3未満なら3のみを返します。

isPrime素数判定の関数です。isPrime2 の方では match 式というのを使ってみました。int の引数 number を取り、素数かどうかを bool で返します。1以外の奇数を受け取ると、oddNumbersThreeToSqrt で奇数のリストを作成し、引数 number を割り切れるものを抽出します。割り切れるものがなければ number素数です。

最小限の関数を組み合わせるのが関数型プログラミングだそうですが、関数の小ささはどのくらいがよいのでしょうか。

つまづいたところ

isPrime 関数や isPrime2 関数で List.filter 関数を使っていますが、ラムダ式の部分適用でつまずきました。はじめはこうしていて、

oddNumbersThreeToSqrt number
|> List.filter (fun x y -> y < x) number

これでは以下のエラーが出ました。

          |> List.filter (fun x y -> y < x) number
  -----------^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

stdin(13,12): error FS0001: この式に必要な型は
    'int list -> 'a'
ですが、ここでは次の型が指定されています
    ''b list'

こうすると解決です。

oddNumbersThreeToSqrt number
|> List.filter ((fun x y -> y < x) number)

何でこうなるかというと……

List.filter 関数は、第一引数に関数を、第二引数にリストを取ります。リストは、パイプラインから渡すこともできます。

List.filter (fun x -> x % 2 = 0) [1..10];;

// または

[1..10]
|> List.filter (fun x -> x % 2 = 0);;

// 以下のことをしているイメージ
// (fun x -> x % 2 = 0) 1
// (fun x -> x % 2 = 0) 2
// (fun x -> x % 2 = 0) 3
// (fun x -> x % 2 = 0) 4
// ...

とにかく、「関数」と「リスト」の2つを取るわけです。それを踏まえて上手くいかなかった部分見てみると、

[1..10]
|> List.filter (fun x y -> y < x) number

// 以下のことをしているイメージ
// List.filter (fun x y -> y < x) number 1
// List.filter (fun x y -> y < x) number 2
// List.filter (fun x y -> y < x) number 3
// List.filter (fun x y -> y < x) number 4
// ...

List.filter (fun x y -> y < x) number の時点で「ラムダ式」と「number」という引数が渡っていますね。number はリストではないのでエラーになったのです。またパイプラインからリストが渡り、引数が3つになっています(多分)。

これを解決するため、カッコでくくって ((fun x y -> y < x) number) として、ひとつの式にします……という解釈で合っている気がします。

……ここまで書いて気づきましたが、これでいいですね。

oddNumbersThreeToSqrt number
|> List.filter (fun x -> x < number)

まあ、部分適用についてよく分かったので良しとしましょう。

素因数分解

完成形

PowerShellワンライナーから持ってきた部分もありますが、再帰関数にするためにほぼ書き換えました。

let primeNumbersLessThanSqrt x =
    [2..System.Math.Max(2, int(System.Math.Sqrt(float(x))))]
    |> List.filter isPrime;;

let rec primeFactorizationRec number primes results =
    if number = 1 then
        results
    elif primes = [] then
        List.append results [number]
    elif number % primes.Head = 0 then
        primeFactorizationRec (number / primes.Head) primes (List.append results [primes.Head])
    else
        primeFactorizationRec number primes.Tail results;;

let primeFactorization number = 
    let primeNumbers = primeNumbersLessThanSqrt number
    primeFactorizationRec number primeNumbers [];;

使い方

primeFactorization 600;;
// val it: int list = [2; 2; 2; 3; 5; 5]

説明

今回も試し割法を用いました。素数で割り続けるというと while を使いたくなりますし F# にも while...do 式があるようですが、今回は使いませんでした。再帰関数に書き換えるにあたって、「割り切れている間はその素数で割り続ける」という考え方から、「割り切れたら、商とその素数を自分自身に渡す」という考え方に変えました。

primeFactorizationRec 関数は、「素因数分解したい整数」と「素数リスト」、「現時点までの素因数分解の結果リスト」を受け取り、割り算をする再帰関数です。

整数が、素数リストの先頭の素数で割り切れるかたしかめ、割り切れたらその素数を結果リストに加えて、「整数とその素数の商」と「素数リスト」、「結果リスト」を自分自身に渡します。割り切れなかったら、「受け取った整数」と、「先頭を除いた素数リスト」と、「結果リスト」を自分自身に渡します。

リストの先頭を除くのは List.Tail を用いました。楽。

60の素因数分解を図で表すとこんな感じです。

f:id:taidalog:20211126211211p:plain
再帰関数のイメージ図

60の素因数分解を言葉で表すとこんな感じです。

  1. 60素数リストの最初の素数 2 で割り切れるので、2 を結果リストに加えて、60 / 2 = 30素数リスト、結果リストを自分自身に渡します。
  2. 30素数リストの最初の素数 2 で割り切れるので、2 を結果リストに加えて、30 / 2 = 15素数リスト、結果リストを自分自身に渡します。
  3. 15素数リストの最初の素数 2 で割り切れないので、素数リストから 2 を除いて、15素数リスト、結果リストを自分自身に渡します。
  4. 15素数リストの最初の素数 3 で割り切れるので、3 を結果リストに加えて、15 / 3 = 5素数リスト、結果リストを自分自身に渡します。
  5. 5素数リストの最初の素数 3 で割り切れないので、素数リストから 3 を除いて、5素数リスト、結果リストを自分自身に渡します。
  6. 5素数リストの最初の素数 5 で割り切れるので、5 を結果リストに加えて、5 / 5 = 1素数リスト、結果リストを自分自身に渡します。
  7. 1 はこれ以上割り切れなので、素因数分解は終了です。ここまでの結果リスト [2; 2; 3; 5] を結果として返します。

実行時間

コードの実行時間を計測するには #time ディレクティブを使うようです。

docs.microsoft.com

600 を素因数分解するのに 0.002秒かかりました。速いなぁ。PowerShellワンライナーは0.027秒、function 版は0.006秒でした。

#time "on";;
primeFactorization 600;;
// リアル: 00:00:00.002、CPU: 00:00:00.000、GC 全般0: 0, 全般1: 0, 全般2: 0
// val it: int list = [2; 2; 2; 3; 5; 5]

もう少し計ってみましょう。10n (3≦n≦9) と、それより小さい中で最大の素数素因数分解します。

整数 実行時間 (s)
997 0.000
1,000 0.000
9,973 0.000
10,000 0.000
99,991 0.000
100,000 0.000
999,983 0.001
1,000,000 0.000
9,999,991 0.003
10,000,000 0.002
99,999,989 0.012
100,000,000 0.011
999,999,937 0.059
1,000,000,000 0.116

はっやい。1,000,000,000は PowerShellワンライナーだと91.208秒、function 版でも1.185秒かかったことを考えると差は歴然ですね。

検算

let factors = primeFactorization 600;;
// val factors: int list = [2; 2; 2; 3; 5; 5]

factors |> List.reduce (fun x y -> x * y);;
// val it: int = 600

手続き型と関数型の違い

PowerShell で手続き的に書いたときは、「割り切れている間はその素数で割り続ける」という風に考えました。その結果、ひとつの関数の中(の foreach や while の中)で、変数の中身を変えながらその変数を使い回すことになりました。

変数 = 60

foreach ( $p in @( 2, 3, 5, 7 ) ) {
    while ( 変数 % $p -eq 0 ) {
        変数 /= $p
        $p
    }
}

「割り切れている間はその素数で割り続ける」という風に、考えたことをそのまま書いたらプログラムができたように思います。ただし、変数の中身が変わり続けて、どの時点で何が入っているかよくわからなくなりました。また素数リストを ForEach-Object しつつその中で while していたので、二重ループとなりややこしかったです。

今回の関数型では、関数に与える引数を変えながら、その関数を使い回すという考え方でした。

関数 60 [2; 3; 5; 7] []
    関数 30 [2; 3; 5; 7] [2]
        関数 15 [2; 3; 5; 7] [2; 2]
            関数 15 [3; 5; 7] [2; 2]
               関数 5 [3; 5; 7] [2; 2; 3]
                    関数 5 [5; 7] [2; 2; 3]
                        関数 1 [5; 7] [2; 2; 3; 5]

関数型の場合は、ややこしく考えたら簡潔なプログラムができるという感じでした。関数を作るのは大変でしたが、二重ループを解消できたのであとから見て何をしているのか分かりやすい気がします。

パラダイムについて思ったこと

関数型は手続き型やオブジェクト指向よりもややこしくないと聞いていましたが、関数型は関数型でややこしかったです。ややこしさのベクトルが変わったと感じました。今回の再帰関数も、何回目の呼び出しの際に引数として何が渡っているか、考えたらややこしいです。

結局いろいろ調べて思ったのは、いろんな考え方がそれぞれの苦手なところを補い合っているのがいいんじゃないかということです。オブジェクト指向は同じようなものをたくさん作るのに向いているけど、状態を隠してしまうので動きを追い辛い。関数型はややこしいけど、状態を内包しないため引数が同じなら必ず同じ結果になる(ので並列処理に向いている)。

みんな違ってみんないいね。

結び

もともとは PythonJavaScript あたりを始めようと思っていました。来年度から授業でプログラミングを扱うためそろそろ触れておこうと思ったのと、新しい言語を学ぶことで、プログラミング未経験の生徒がつまづきそうな箇所を把握しておこうと思ったためです。ところが、多少 VBAPowerShell の経験があるため、同じ手続き型主体の言語では大きなつまづきはなさそうでした。じゃあもう関数型プログラミングに挑戦しようと思った次第です。

そんなわけで関数型プログラミングに手を出したのですが、PowerShellForEach-ObjectWhere-Objectスクリプトブロック、あとパイプライン等に慣れていたおかげでそのあたりはすんなり理解できました。やってて良かった PowerShell

とか言いつつ再帰関数には手間取ったので、この取り組みには意味があったと思います。というのも、情報Ⅰの教科書に Pythonフィボナッチ数列再帰関数を作るページがあったんですよ。発展課題でしたが。ひえぇ。

今回の素因数分解を通して関数型プログラミングの考え方の表層に少しだけ触れた気がします。深淵にはまだまだ届きませんが、今後も綾波カラーの F# と遊びつつ、そこで得た技術を PowerShell で試そうと思います。

f:id:taidalog:20211127032829p:plain
Windows PowerShell のアイコン

画像は PowerShell Team より
https://devblogs.microsoft.com/powershell/

f:id:taidalog:20211127034230p:plain
PowerShell Core 6.0 以降のアイコン

画像は Wikipedia より
https://ja.wikipedia.org/wiki/PowerShell

そういえば Windows PowerShell のアイコンって青と白……零号機改…… PowerShell Core 6.0 以降は黒……黒波…… PowerShell綾波じゃないか!

f:id:taidalog:20211127023434j:plain
アヤナミレイ(仮称)

画像は EVANGELION STORE ONLINE さんのツイッターより
https://twitter.com/eva_store/status/1355082895367368713

これは PowerShell をやるしかない!1

参考


  1. やるしかない。