M言語で素数のリストを作成する

##はじめに
こんにちは。趣味で主にVBAのプログラミングをしているものです。


突然ですが、Power Queryってとても便利ですよね。基本的にマウス操作でデータの収集と加工の手順が記録されるので事務作業には欠かせません。Power Queryに記録された手順はM言語で記述されています。詳細エディタで見てみると、`let ... in ...`とよくわかりません。宣言は？変数は？ってなります。そこでM言語に慣れるため、データソースなしでいろいろなリストを作ってみました。あまり情報がなく、<a href="https://docs.microsoft.com/ja-jp/powerquery-m/">Microsoftのドキュメント</a>を漁りながら試行錯誤しました。ひとまずタイトルにあるように素数のリストを作ることができましたので、書き残しておきます。

##素数リストを生成するロジック
今回は下記のようにすることで素数のリストを取得します。
<ol>
<li>2以上の整数のリストを用意します。</li>
<li>リストの各要素でそれぞれが素数かどうか判定し、`true`のものを抽出します。</li>
<li>完了！！</li>
</ol>
とってもシンプルですね。
つまり、必要なものは3つになります。
<ul>
<li>2以上の整数のリスト</li>
<li> 素数かどうかを判定する関数</li>
<li>リストの要素を関数に通して`true`のものを抽出する関数</li>
</ul>
また、素数かどうかの判定は再帰処理を用いて下記のように行います。
<ol>
<li>割る数の初期値として数値の2を用意します。</li>
<li>それが判定対象の平方根より大きいかどうか判定します。</li>
<li>大きかった場合は判定対象が素数になり、処理を終了します。（`true`を返す）</p></li>
<li>大きくない場合は、判定対象の数値がその割る数で割り切れるかどうか判定します。</li>
<li>割り切れた場合は素数でないことになり、処理を終了します。(`false`を返す)</li>
<li>割り切れない場合は、割った数に1を足した数を持って（手順 2.）に戻ります。（再帰処理）</li>
</ol>
処理が終了すると素数か素数でないかがわかります。再帰処理にした理由は後述します。
<h2>2以上の自然数のリストを生成する</h2>
指定範囲で連続する整数のリストは```{a..b}```のようにすると得られます。（<a href="https://docs.microsoft.com/ja-jp/powerquery-m/m-spec-values#list">参考</a>）なのでこれに無限大`#infinity`を入れればいいのではと考えたのですが、うまくはいきませんでした。指定は整数値でないといけないようです。
![PowerQuery001.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/578163/f015d2c2-ad2e-c0b2-04d0-c44e7b6f025d.png)

したがって、<a href="https://docs.microsoft.com/ja-jp/powerquery-m/list-generate">リスト生成関数</a>`List.Geneate`にて自然数のリストを得るべく関数を作成します。`List.Generate`関数の定義を下記に記します。

```
List.Generate(initial as function, condition as function, next as function, optional selector as
nullable function) as list
```

`List.Generate`関数は第一引数に初期値を与える関数、第二引数に終了条件関数、第三引数に次項の生成関数を指定します。（第四引数は今回不使用）見事におそろいですべての引数に関数を渡します。VBAではありえない状況にナンダコレと思いながら、できたものが下記になります。

```
let
    整数リスト = List.Generate(() => 2, each true, each _ + 1)    // {2, 3, 4, ...}
in
    整数リスト


/* eachを使用しない記述
let
    整数リスト = List.Generate(() => 1, (_) => true, (_) => _ + 1)    // {2, 3, 4, ...}
in
    整数リスト
*/
```

初期値はアロー関数式で`2`を与え、終了条件は常に`true`で無限ループにしています。また、次項は`_ + 1`のカウントアップとしております。ちなみに下の式は<a href = "https://docs.microsoft.com/ja-jp/powerquery-m/m-spec-functions#simplified-declarations">`each`の使い方</a>を覚える前にすべて<a href="https://docs.microsoft.com/ja-jp/powerquery-m/m-spec-functions#writing-functions">アロー関数式</a>で表記したもので、上と等価の関数となっています。

##素数かどうかを判定する関数①
次に、素数を判定する関数を作成します。


2から判定対象の平方根まで+1ずつカウントアップしていき、途中で割り切れたら`false`を、最後まで割り切れなかったら`true`を返すという関数を作るわけですが、M言語にはループ構文（for文、do文）や終了命令文（return文、exit文）がありません。

VBAならIfで判定してExit Functionで結果を返しますがM言語ではそれができないのです。なのでまずは愚直に全要素に対して計算し、それが完了してから判定をするコードを組みました。

```
let
    ソース = (parameter as number) as logical => (
        let
            範囲外 = (parameter < 2) or (Number.RoundDown(parameter) <> parameter),    // 2未満もしくは小数は判定の対象外
            割る数リスト = {2..Number.RoundDown(Number.Sqrt(parameter))},    // 2から判定対象の平方根までの整数リスト
            余りリスト = List.Transform(割る数リスト, each Number.Mod(parameter, _)),    // 判定対象を割った余りのリスト
            余りの最小値 = List.Min(余りリスト),    // リスト内の最小値を取得します
            Is素数 = 余りの最小値 <> 0,    // 余りが0の割り切れた要素がなければ素数
            素数判定 = if 範囲外 then false else Is素数    // 範囲外かどうかの判定を先に行います
        in
            素数判定
    )
in
    ソース

```


このアルゴリズムは多くの無駄な計算をすることになります。例えば`2^10 = 1024`の場合、`√1024 = 32`なので割る数の候補は`{2..32}`の31個になります。1個目の`2`で「素数ではない」と判定できるので残りの30個の判定は全くの無駄です。

##素数かどうかを判定する関数②
M言語で疑似的にループ処理を行うことは、関数を再帰的に使用すれば可能です。条件分岐で、関数を再度実行させるか終了するかを判定させればよいのです。そのためかＭ言語のリファレンスには<a href="https://docs.microsoft.com/ja-jp/powerquery-m/m-spec-functions#recursive-functions">再帰関数の項目</a>があります。

実装に当たっては、メイン関数と再帰用の副関数を分離することで引数の数の違いをクッションさせたり、平方根計算など何度も同じ計算をすることのないようにして関数を作成しました。


```
let
    ソース = (parameter as number) as logical => (
        let
            範囲外 = (parameter < 2) or (Number.RoundDown(parameter) <> parameter),    // 2未満もしくは小数は判定の対象外
            副関数 = (target as number, divisor as number, max as number) as logical => (
                if divisor > max then    // 割る数が最大値を超えていれば素数
                    true
                else
                    if Number.Mod(target, divisor)= 0 then    //  余り0がなら素数じゃない
                        false
                    else
                        @副関数(target, divisor + 1, max)    // 再帰処理、@が必要
            ),
            素数判定 = if 範囲外 then false else 副関数(parameter, 2, Number.Sqrt(parameter))    // ここで初期値と最大値を与えています
        in
            素数判定
    )
in
    ソース
```

##リストから条件に合うものを抽出する関数
これは組み込みのリスト関数である<a href="https://docs.microsoft.com/ja-jp/powerquery-m/list-select">`List.Select`</a>を使用します。

```
List.Select(list as list, selection as function) as list
```

第一引数に対象のリストを指定し、第二引数に判定式を指定します。すると判定式が`true`となる要素のリストが取得できます。今回は整数リストについて、素数判定が`true`となる要素を抽出するので下記のようになります。

```
let
    素数リスト = List.Select(整数リスト, each 素数判定(_))
in
    素数リスト


/*  eachを使用しない記述
let
    素数リスト = List.Select(整数リスト, (_) => 素数判定(_))
in
    素数リスト
*/
```


##関数を組み合わせて完成へ

これまでのパーツを組み合わせれば完成になります。ステップの間にComma`, `を入れるのを忘れないようにしましょう。また、素数判定の時に入れていた2未満の数値と小数をはじく処理はここでは不要なので除いています。

```
let
    整数リスト = List.Generate(() => 2, each true, each _ + 1),    // {2, 3, 4, ...}
    副関数 = (target as number, divisor as number, max as number) as logical => (
        if divisor > max then    // 割る数が最大値を超えていれば素数
            true
        else
            if Number.Mod(target, divisor)= 0 then    //  余り0がなら素数じゃない
                false
            else
                @副関数(target, divisor + 1, max)    // 再帰処理
    ),
    素数判定 = (parameter as number) as logical => 副関数(parameter, 2, Number.Sqrt(parameter)),
    素数リスト = List.Select(整数リスト, each 素数判定(_))
in
    素数リスト

```

Power Queryの「詳細エディター」にきちんと入力できていれば素数のリストが表示されます。これはロジック上、無限個の素数です。リストをスクロールしていくと素数を50個ずつ読み込んでいきました。また、素数が40000あたりから読み込みが遅くなりました。
![PowerQuery0021.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/578163/d90307d0-e7be-2e18-234d-19dca5861a6f.png)

##注意事項と対策
上記で作成したものは無限ループを用いて元のリストを作成しており、最後まで演算が完了しているわけではありませんし、完了しません。すなわち、このリストを全要素が対象となるリスト関数に渡すと無限の計算地獄に突入します。
![PowerQuery003.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/578163/45d302e7-c2d3-1b2e-507e-8d4973ee5b54.png)
これを防ぐには有限個のリストにする必要があります。先ほどのコードを関数の中に入れて、無限ループとしていたところに引数で最大値を指定してあげれば完了です。

```
let
    素数リスト = (max as number) => (
        let
            整数リスト = List.Generate(() => 2, each _ <= max, each _ + 1),    // 終了条件を調整しました
            副関数 = (target as number, divisor as number, max as number) as logical => (
                if divisor > max then    // 割る数が最大値を超えていれば素数
                    true
                else
                    if Number.Mod(target, divisor)= 0 then    //  余り0がなら素数じゃない
                        false
                    else
                        @副関数(target, divisor + 1, max)    // 再帰処理
            ),
            素数判定 = (parameter as number) as logical => 副関数(parameter, 2, Number.Sqrt(parameter)),
            素数リスト = List.Select(整数リスト, each 素数判定(_))
        in
            素数リスト
    )
in
    素数リスト

```


これで急に`1000`以下の素数の個数が必要になっても大丈夫です。


```
let
    ソース = List.Count(素数リスト(1000))
in
    ソース    // 168
```

![PowerQuery004.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/578163/3e4ba5de-e62f-947d-6014-c569d68389ed.png)

##おわりに
M言語について、試行錯誤しているうちはエラーばかりで何が何やらといった状態でしたが、できてしまえばずいぶん短くなっています。VBAでは表現できない無限を扱うことができたり、またコードが長くなってしまうものもシンプルに書き表せそうです。M言語といいますか関数型プログラミングの奥深さに触れられた気がします。

ここまで読んでいただきありがとうございます。
それでは皆様にもよきPower Queryライフを。