F# を始めました。新しい言語で最初にすることと言ったらやっぱりあれですよね。素数判定と素因数分解です。Hello, World! しても面白くないので。
投稿日の 20211127 は素数です。
作業環境
関数型プログラミングを始めるにあたって意識したこと
- 変数の再代入はしない
- 再帰関数を使う
そうすること自体が目的ではないのですが、関数型の特徴らしいのと、たしかにメリットがありそうなので、上の2点を意識しました。
素数判定
完成形
以前の PowerShell のコードを書き換えました。ほぼ同じ考え方でできました。
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から までの奇数です。 が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の素因数分解を図で表すとこんな感じです。
60の素因数分解を言葉で表すとこんな感じです。
60
は素数リストの最初の素数2
で割り切れるので、2
を結果リストに加えて、60 / 2 =30
と素数リスト、結果リストを自分自身に渡します。30
は素数リストの最初の素数2
で割り切れるので、2
を結果リストに加えて、30 / 2 =15
と素数リスト、結果リストを自分自身に渡します。15
は素数リストの最初の素数2
で割り切れないので、素数リストから2
を除いて、15
と素数リスト、結果リストを自分自身に渡します。15
は素数リストの最初の素数3
で割り切れるので、3
を結果リストに加えて、15 / 3 =5
と素数リスト、結果リストを自分自身に渡します。5
は素数リストの最初の素数3
で割り切れないので、素数リストから3
を除いて、5
と素数リスト、結果リストを自分自身に渡します。5
は素数リストの最初の素数5
で割り切れるので、5
を結果リストに加えて、5 / 5 =1
と素数リスト、結果リストを自分自身に渡します。1
はこれ以上割り切れなので、素因数分解は終了です。ここまでの結果リスト[2; 2; 3; 5]
を結果として返します。
実行時間
コードの実行時間を計測するには #time
ディレクティブを使うようです。
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]
関数型の場合は、ややこしく考えたら簡潔なプログラムができるという感じでした。関数を作るのは大変でしたが、二重ループを解消できたのであとから見て何をしているのか分かりやすい気がします。
パラダイムについて思ったこと
関数型は手続き型やオブジェクト指向よりもややこしくないと聞いていましたが、関数型は関数型でややこしかったです。ややこしさのベクトルが変わったと感じました。今回の再帰関数も、何回目の呼び出しの際に引数として何が渡っているか、考えたらややこしいです。
結局いろいろ調べて思ったのは、いろんな考え方がそれぞれの苦手なところを補い合っているのがいいんじゃないかということです。オブジェクト指向は同じようなものをたくさん作るのに向いているけど、状態を隠してしまうので動きを追い辛い。関数型はややこしいけど、状態を内包しないため引数が同じなら必ず同じ結果になる(ので並列処理に向いている)。
みんな違ってみんないいね。
結び
もともとは Python か JavaScript あたりを始めようと思っていました。来年度から授業でプログラミングを扱うためそろそろ触れておこうと思ったのと、新しい言語を学ぶことで、プログラミング未経験の生徒がつまづきそうな箇所を把握しておこうと思ったためです。ところが、多少 VBA や PowerShell の経験があるため、同じ手続き型主体の言語では大きなつまづきはなさそうでした。じゃあもう関数型プログラミングに挑戦しようと思った次第です。
そんなわけで関数型プログラミングに手を出したのですが、PowerShell の ForEach-Object
や Where-Object
、スクリプトブロック、あとパイプライン等に慣れていたおかげでそのあたりはすんなり理解できました。やってて良かった PowerShell。
とか言いつつ再帰関数には手間取ったので、この取り組みには意味があったと思います。というのも、情報Ⅰの教科書に Python でフィボナッチ数列の再帰関数を作るページがあったんですよ。発展課題でしたが。ひえぇ。
今回の素因数分解を通して関数型プログラミングの考え方の表層に少しだけ触れた気がします。深淵にはまだまだ届きませんが、今後も綾波カラーの F# と遊びつつ、そこで得た技術を PowerShell で試そうと思います。
画像は PowerShell Team より
https://devblogs.microsoft.com/powershell/
画像は Wikipedia より
https://ja.wikipedia.org/wiki/PowerShell
そういえば Windows PowerShell のアイコンって青と白……零号機改…… PowerShell Core 6.0 以降は黒……黒波…… PowerShell も綾波じゃないか!
画像は EVANGELION STORE ONLINE さんのツイッターより
https://twitter.com/eva_store/status/1355082895367368713
これは PowerShell をやるしかない!1
参考
- 磯野ー!関数型言語やろうぜー!
- 「再代入なんて、あるわけない」 ~ふつうのプログラマが関数型言語を知るべき理由~ (Gunma.web #5 2011/05/14)
- 希望の関数と絶望の副作用
- 関数 - F# | Microsoft Docs
- F# インタラクティブ (dotnet) リファレンス | Microsoft Docs
- https://fsharp.github.io/fsharp-core-docs/reference/fsharp-collections-listmodule.html#append
- https://fsharp.github.io/fsharp-core-docs/reference/fsharp-collections-listmodule.html#filter
- https://fsharp.github.io/fsharp-core-docs/reference/fsharp-collections-listmodule.html#reduce
- https://fsharp.github.io/fsharp-core-docs/reference/fsharp-collections-listmodule.html#tail
-
やるしかない。↩