jqのむだづかいーフィボナッチ数・素数生成篇

[JSON](https://datatracker.ietf.org/doc/html/rfc7159)処理のコマンドラインツールである[jq](https://stedolan.github.io/jq/)は、JSONテキストを1行でちゃくっと解析、変換するときに使うものです。複雑な分岐や制御が絡んできたら、`sed`や`awk`など他の文字列処理ユーティリティと組み合わせて何とかするのが通例です。単体で複雑なことをしたりはしません。

とは言え、`jq`にも変数定義、`for`や`if`などの制御構造、関数定義などプログラミング言語らしき機能が備わっているので、「やればできんじゃねぇ」と野望を募らせてしまうこともあります。

というわけで、ここではフィボナッチ数と素数の生成に挑戦します。

### コード

コード（フィルタファイル）は`fibo.jq`と`prime.jq`で、次の[Github](https://github.com/stoyosawa/jqDoc-public/tree/main/filters)から取得できます（短いのでコピペでも十分ですが）。

```https://github.com/stoyosawa/jqDoc-public/```

フィルタファイルの改行はUnixスタイルの`LF`だけでなければならないので、保存時に注意してください。Windows流に`CRLF`だと次のエラーが報告されます。

```
jq: error: syntax error, unexpected INVALID_CHARACTER (Unix shell quoting issues?)
  at <top-level>, line 1:
```

### フィルタファイルの使い方

これらファイルを`jq`から呼び出すときは、次のオプションを指定します。

- `-f`オプション（`--from-file`）ーフィルタファイルを読み込みます。
- `-n`オプション（`--null-input`）ー数列は内部で生成されるので、JSONデータを外部から読み込まないよう指示します。
- `-c`オプション（`--compact-output`）ーデフォルトでは配列要素（数列は配列に収容される）が縦に表示されるので長くなります。これで読みやすくなります。
- `--arg`オプションー生成する数列の数を制限する変数値をセットします。

まとめると、次のようになります。

```
$ jq --arg loop 20 -cnf fibo.jq                          # フィボナッチ数を20個まで生成
$ jq --arg max 60 -cnf prime.jq                          # 60までの素数を探す
```

### フィボナッチ数

[フィボナッチ数列](https://ja.wikipedia.org/wiki/フィボナッチ数)（Fibonacchi sequence）は、1つ前と2つ前の要素の和を次の要素の値とする数列です。0番目の要素は0、1番目の要素は1と決められているので、2番目は0+1=1、3番目は1+1=2です。定義は次のとおりです。

```
F(0) = 0                                                 # 0番目のフィボナッチ数
F(1) = 1                                                 # 1番目のフィボナッチ数
F(n) = F(n-1) + F(n-2)                                   # n番目のフィボナッチ数（n≧2）
```

フィルタは次の通りです。

```
($loop | tonumber) as $loop |
[0, 1] |
while(
	length <= $loop;
	(
		length as $len |
		. + [.[$len-1] + .[$len-2]]
	)
)
```

1. `--arg`コマンドラインオプションで指定した変数`loop`は、フィルタ内では`$loop`で参照できます。コマンドライン引数は文字列なので、`tonumber`で数値に変換して`$loop`に入れ直します。なお、変数定義の`... as $x`文は、`jq`のパイプライン処理（`|`）には影響を与えません。データの流れという観点では無視して構いません。
2. フィボナッチ数の最初の2要素を配列で定義します。以降、この配列（`.`で参照）に要素を追加していきます。
3. ループです。`while`には条件式と更新式という、2つの制御要素が含まれます。
4. ループは条件式が`true`の間は回り続けます。ここでは配列（`.`）の長さを`length`から調べ、それが変数`$loop`より大きくなったら終了します。
5. 更新式では、入力配列を変更します。わかりやすいように括弧`()`でまとめています（なくても問題ありませんが）。
6. 更新式ではまず、現在の配列長を変数`$len`に代入します。これは、配列中の要素を参照するときに用います。
7. 続いて、現在の配列`.`に末尾の要素（`.[$len-1]`）とその1つ前の要素（`.[$len-2]`）の和を加えます。和の値（たとえば0+1=1）をさらに`[]`で括ることで配列化しているのは、配列の加算（要素の追加）ではどちらも配列でなければならないからです。

実行例を示します。

```
$ jq --arg loop 20 -cnf fibo.jq
[0,1]
[0,1,1]
[0,1,1,2]
[0,1,1,2,3]
[0,1,1,2,3,5]
[0,1,1,2,3,5,8]
[0,1,1,2,3,5,8,13]
[0,1,1,2,3,5,8,13,21]
[0,1,1,2,3,5,8,13,21,34]
[0,1,1,2,3,5,8,13,21,34,55]
[0,1,1,2,3,5,8,13,21,34,55,89]
[0,1,1,2,3,5,8,13,21,34,55,89,144]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181]
```

最後の結果だけを出力したいのなら、`while`を`until`に変えます。条件式が満たされたときに`.`を出力して終了します。

```
($loop | tonumber) as $loop |
[0, 1] |
until(                                                   # 変更点はここと
	length >= $loop;                                     # この条件式だけ
	(
		length as $len |
		. + [.[$len-1] + .[$len-2]]
	)
)
```

実行例を示します。

```
$ jq --arg loop 20 -cnf fibo.jq
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181]
```

### 素数

ある数が[素数](https://ja.wikipedia.org/wiki/素数)かは、その数までの素数すべてで割ってみて、どれでも割り切れないか否かをチェックすることで判定できます。つまり、コードは「ある数」を順次増やしていくループと、「これまでの素数」の配列要素で割っていくループの2重ループで構成されます。

ここでは、チェック対象となる数のループには`for`ループと等価な`foreach`を、素数の配列要素で試し割をするループには配列を一気に処理する述語関数の`map`を使います。`map`はPythonやJavaScriptのものと機能は同じです。

> 他にも、`x`が素数かは`x`<sup>1/2</sup>以下の素数まで確認すれば効率が良い（たとえば11が素数かは2と3で割るだけでよく、5はチェックする必要はない）など高速化のテクニックがありますが、ここではそこまでは追及しません。だって、`jq`なんですもの。

フィルタは次の通りです。

```
($max | tonumber) as $max |
[2] |
foreach range(3; $max) as $x
(
	.;
	. as $p |
	map($x % . == 0) | 
	if contains([true]) then
		[]
	else
		[$x]
	end | 
	$p + .;
	.
)
```

2重ループが絡んできているだけあって、フィボナッチと比べるとややこしくなっています。また、パイプラインで次の処理に渡される`.`の中身がその都度変化するので、追うのにも苦労します。具体的には、次のように変遷します。

- 素数を収容した配列。2行目で定義され、5～7行目の`.`で参照されているのがこれ。ループしてコード先頭に戻った時は、最後の13行目のものが用いられます。
- `map`が生成する、素数配列と同じ要素数の`true`/`false`からなる配列（7行目）。この`.`は8行目の`contains`に暗黙的に引き渡されます。
- 素数配列に追加される配列。`$x`が素数かに応じて`[]`または`[$x]`が9行目あるいは11行目で定義されます。この`.`は13行目で用いられます。
- 素数を収容した配列。最初のものを退避させた`$p`から、13行目で新規に生成されます。14行目がこれです。

行順に説明します。

1. コマンドライン引数取り込みの要領は`fibo.jq`と同じです。
2. 素数配列は`[2]`からスタートします。以下、順次、この配列に素数を加えていきます。
3. 素数か否かのチェック対象になる数値を生成する`foreach`ループです。`foreach 入力値 as 変数`で構成されています。入力値は反復可能な値ならなんでも構いません。ここでは`range`関数から3以上`$max`未満の整数の配列を生成しています。これら値は、ループを回る毎に変数`$x`に収容されます。
4. `foreach`ループには3つの制御要素が含まれます。初期化値、更新式、抽出式です。
5. ループの初期値は、入力された配列（2行目）を参照する`.`です（だから、最初は`[2]`）。
6. ここで、現在の素数配列（`.`）を一時的に変数`$p`に退避させます。以下の計算で`.`をオーバーライトしてしまうからです。
7. 現在の数値`$x`に対し、`.`の要素でモジュロ演算（`%`）を施します。演算結果は`== 0`で比較することで`true`（割り切れる）、`false`（割り切れない）に変換します。これらを現在の配列すべての素数で実行するには、述語関数の`map`を用います。これにより、たとえば、`$x=10`に対し、ここまでの素数配列`[2, 3, 5, 7]`でモジュロ演算を行うと、`[true, false, true, false]`が得られます。以下、次のステップの`.`はこの真偽配列を参照します。
8. 上記の結果に1つでも`true`が含まれていたら、`$x`は素数ではありません。これは`contains`関数からチェックできます。引数で指定された要素が含まれていれば、関数は`true`を返します。なお、`.`（真偽配列）が配列なので引数も配列でなければなりません（`true`単体ではなく`[true]`配列）。
9. 素数でないならば、カラ配列`[]`を用意します。
10. `contains`が`false`なら、`$x`は素数です。
11. 素数ならば、`$x`を収容した配列`[$x]`を用意します。
12. `jq`の`if`文は、末尾に`if`文の末尾に終了を明示する`end`が必要です（bashの`if-fi`に似た感じです）。
13. この段階で、`.`は`[]`または`[$x]`を参照しています。始めに素数を収容していた配列は`$p`に退避されています。そこで、この`$p`に新たに素数と判定された値`.`を加えることで、素数配列を更新します。これで、`foreach`の更新式は終わりです。`;`で終了を示します。
14. `foreach`のだ3番目の要素の抽出式に記述された値が、ループを巡るたびに出力されます。ここで指定されている`.`は`$p + .`で更新された素数配列です。

長かったですね。では、実行例を示します。

```
$ jq --arg max 60 -cnf prime.jq
[2,3]                                                    # $x=3。3が加わる。
[2,3]                                                    # $x=4。4は2で割り切れるので加えられない。
[2,3,5]                                                  # $x=5。追加。
[2,3,5]                                                  # $x=6。素数ではない。
⁞
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53]            # $x=57。3で割れる。
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53]            # $x=58。2で割れる。
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]         # $x=59。素数。
```

もっと目に優しいコーディングがありそうですが、今日はここまでにしておきます。


### おわりに

ええ、実用性はゼロです。`jq`を拗らせて「限界など知らない」と頑張っただけです（が、確かに、意味はねぇなぁ...）。でも、ここまで書ければ、レベル4くらいには達したと思います。


### 参考

- [./jq](https://stedolan.github.io/jq/) - `jq`のオフィシャルサイトです（英文）。
- [Qiita jq tag](https://qiita.com/tags/jq) - Qiita掲載の`jq`関連の記事一覧です。
- [jqマニュアル（開発バージョン）](https://yujiorama.github.io/unofficial-translations/jq/l10n/jp/manual/) - Yuji Okazawa氏が（非公式に）訳しておられる`jq`マニュアルの日本語版です。和訳マニュアルは他にもあるので、検索してください。
- [The JavaScript Object Notation (JSON) Data Interchange Format（RFC 8259）](https://www.rfc-editor.org/rfc/rfc8259.txt) - JSONの仕様です（英文）。しばしば[RFC 7159](https://www.rfc-editor.org/rfc/rfc7159.txt)が参照されますが、そちらはobsoleteになりました。
- [JSON(JavaScript Object Notation)データ交換フォーマット](https://www.asahi-net.or.jp/~ax2s-kmtn/internet/rfc8259j.html) - 上記の非公式の和訳です。
- [jqハンドブックーNetOps/DevOps必携のJSONパーザ](http://www.cutt.co.jp/book/978-4-87783-491-3.html) - このページに掲載したフィボナッチ数のコードは、この本の10.5節で紹介したものです。ご購入はこちらから: 【[出版社](http://www.cutt.co.jp/book/978-4-87783-491-3.html) | [honto](https://honto.jp/netstore/pd-book_31037910.html) | [amazon.co.jp](https://www.amazon.co.jp/jq/dp/4877834915) | [ヨドバシカメラ](https://www.yodobashi.com/product/100000009003450000/)】。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2712175/20272c85-f084-557b-189f-aa7128e283ab.png)