【Go1.23】range over func原理主義者のためのモジュール作りました【itermania】

# TL; DR

https://github.com/Syuparn/itermania

```go
prime := Bind(Inc(2), func(n int) Gen[int] {
	return Where(Const(n), All(Not(Eq(Mod(Const(n), Range(2, n, 1)), Const(0)))))
})

for i := range Head(prime, 10)() {
	fmt.Println(i)
}
```

```
2
3
5
7
11
13
17
19
23
29
```

# はじめに

Go1.23から、for文の `range` に関数を指定することができるようになります。これによって、スライスを用いない反復処理をシンプルに書くことができます。

```go
// 0~2を繰り返すイテレータ
func rotate(yield func(int) bool) {
	i := 0
	for {
		// yieldの引数がループ変数として渡される
		if !yield(i) {
			// for文本体のループがcontinue, break等で終了した場合falseが返るので、イテレータも中断する
			return
		}
		i = (i + 1) % 3
	}
}

func main() {
	// イテレータを range に指定
	for i := range rotate {
		fmt.Println(i)
	}
}
```

```:結果
0
1
2
0
1
2
...
```

https://tip.golang.org/doc/go1.23

ジェネリクス以来の大幅な文法変更、このビッグウェーブを逃すわけにはいきません。
というわけで、本記事ではイテレータ **だけで** プログラムを組んでいきたいと思います。

# イテレータだけで処理を書く
先達はあらまほしきことなり。まずはお手本になる設計を探します。
今回は、Icon言語の「ジェネレータ」を目標にしました。

Icon言語は、言語仕様としてジェネレータ（Goのイテレータに相当）を持っています。
以下、「Rubyist のための他言語探訪」より素数を生成するソースコードの引用です。

https://magazine.rubyist.net/articles/0014/0014-Legwork.html

```icon:素数を無限に生成するジェネレータ（引用、コメントのみ追記）
# 素数を生成するジェネレータ（「エラトステネスの篩」を使用）
procedure sieve()
  # iを2から1ずつ増やし、「2からi-1までのすべての整数(jとする)に対し i % j == 0でない」ならばiを生成
  every i:=seq(2) & not(every i%(2 to i-1)=0 & break) & suspend(i)
end

procedure main()
  # 素数を小さい順に100個表示
  every write(sieve() \ 100)
end
 ```

`i%(2 to i-1)` で「iを2からi-1までの各整数で割ったあまり」（`[i % 2, i % 3, i % 4, ..., i % (i - 1)]`） というジェネレータが得られるため、反復処理込みで2行で書くことができています。初めて見たときは衝撃を受けました。

もしこれがGoで実現できればどうでしょう？**我々はもう深いfor文や嵩むif文に怯える必要はありません**。イテレータを使い倒して、1行野郎を目指しましょう[^icon]。

:::note info
~~言うまでもありませんが~~ **本記事はネタ記事です**。実用性は度外視しています。
真面目なコードはお作法に従って書きましょう。
:::

# 検証したバージョン

- Go1.23 rc1

正式リリースまでに仕様が変更される可能性があります。

# イテレータだけで処理を書く
作ったのがこちらのモジュールです。

https://github.com/Syuparn/itermania

このモジュールを使えば、Icon言語のように素数一覧の生成もお手のものです。

```go
prime := Bind(Inc(2), func(n int) Gen[int] {
	return Where(Const(n), All(Not(Eq(Mod(Const(n), Range(2, n, 1)), Const(0)))))
})

for i := range Head(prime, 10)() {
	fmt.Println(i)
}
```

```:結果
2
3
5
7
11
13
17
19
23
29
```

行が多くて気に食わないのであれば、こう書き直しましょう。
**Go言語は3行で素数を求められます**。

```go
for i := range Head(Bind(Inc(2), func(n int) Gen[int] { return Where(Const(n), All(Not(Eq(Mod(Const(n), Range(2, n, 1)), Const(0))))) }), 10)() {
	fmt.Println(i)
}
```

FizzBuzzだってこの通りです。

```go
fizzbuzz := Bind(Inc(1), func(n int) Gen[string] {
	return If(Eq(Mod(Const(n), Const(15)), Const(0)), Const("FizzBuzz"),
		If(Eq(Mod(Const(n), Const(3)), Const(0)), Const("Fizz"),
			If(Eq(Mod(Const(n), Const(5)), Const(0)), Const("Buzz"),
				Const(strconv.Itoa(n)))))
})

for i := range Head(fizzbuzz, 15)() {
	fmt.Println(i)
}
```

```
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
```

では、続いて実際の実装について見ていきましょう。

## 数列を生成するイテレータ
まずは基本となる数列をイテレータで生成します。

### Inc
名前の通り、生成される値が1ずつ増えていきます。スライスと異なり **無限長** の要素を生成可能です。

```go
func Inc[V constraints.Integer](v V) iter.Seq[V] {
	return func(yield func(V) bool) {
		for {
			if !yield(v) {
				return
			}
			v++
		}
	}
}
```

```go
for i := range Inc(1) {
	fmt.Println(i)
}
```

```
1
2
3
4
5
...
```

### Range
続いて、開始、終了、増分を指定できる数列です。Pythonの `range` 関数から名前を取ったのですが、`range Range` の字面が紛らわしいのが反省点です。

```go
func Range[V constraints.Integer](start, stop, step V) iter.Seq[V] {
	return func(yield func(V) bool) {
		i := start
		increasing := step > 0
		for {
			if (increasing && (i >= stop)) || (!increasing && (i <= stop)) {
				return
			}

			if !yield(i) {
				return
			}
			i += step
		}
	}
}
```

```go:例
for i := range Range(1, 11, 2) {
	fmt.Println(i)
}
```

```結果
1
3
5
7
9
```

### スライス
決め打ちで値を入れたい際にも使えるよう、スライスをイテレータに変換する関数も用意しました。

```go
for s := range FromSlice([]string{"a", "b", "c"}) {
	fmt.Println(s)
}
```

```go
func FromSlice[V any](values []V) iter.Seq[V] {
	return func(yield func(V) bool) {
		for _, v := range values {
			if !yield(v) {
				return
			}
		}
	}
}
```

## イテレータ同士の演算
続いて、イテレータを加工する関数を用意します。もちろん戻り値もイテレータです。

### 単項演算

```go:bool反転
for i := range Not(FromSlice([]bool{true, false})) {
	fmt.Println(i)
}
```

```
false
true
```

```go
// 符号反転
func Not(gen iter.Seq[bool]) iter.Seq[bool] {
	uni := Uni(func(v bool) bool {
		return !v
	})
	return uni(gen)
}

// 単項演算の共通処理
func Uni[V, W any](op func(V) W) func(iter.Seq[V]) iter.Seq[W] {
	return func(xSeq iter.Seq[V]) iter.Seq[W] {
		return func(yield func(W) bool) {
			for x := range xSeq {
				if !yield(op(x)) {
					return
				}
			}
		}
	}
}
```

### 二項演算
二項演算では、2つのイテレータの直積に対して演算子を適用しています。これは、冒頭のIcon言語の仕様に合わせました。

```go
for i := range Mul(FromSlice([]int{10, 100}), FromSlice([]int{2, 3})) {
		fmt.Println(i)
}
```

```
20  // 10 * 2
30  // 10 * 3
200 // 100 * 2
300 // 100 * 3
```

```go
// 二項演算の共通処理
func Bin[V, W any](op func(V, V) W) func(iter.Seq[V], iter.Seq[V]) iter.Seq[W] {
	return func(xSeq iter.Seq[V], ySeq iter.Seq[V]) iter.Seq[W] {
		return func(yield func(W) bool) {
			for x := range xSeq {
				for y := range ySeq {
					if !yield(op(x, y)) {
						return
					}
				}
			}
		}
	}
}

// 積を求める
func Mul[V Number](xSeq iter.Seq[V], ySeq iter.Seq[V]) iter.Seq[V] {
	bin := Bin(func(xVal V, yVal V) V {
		return xVal * yVal
	})
	return bin(xSeq, ySeq)
}
```

## 単一の値をイテレータ化する
すべてをイテレータ化するということは、当然単一の値もイテレータに変換する必要があります（でないと上記の演算用関数の引数に渡せません）。
この関数があれば、以下のように「数列をn倍する」等の演算を簡単に書けます[^slice]。

```go:3の倍数の数列
// Const: リテラルをイテレータ化する関数
Mul(Const(3), Inc(1)) // 3, 6, 9, ...
```

実装はシンプルで、1度だけ値を `yield` して終了しています。

```go
func Const[V any](v V) Gen[V] {
	return func() iter.Seq[V] {
		return func(yield func(V) bool) {
			if !yield(v) {
				return
			}
		}
	}
}
```

```go
for i := range Const(5)() {
	fmt.Println(i)
}
```

```
5
```

## イテレータを変数として使う
Icon言語の素数を求める処理では、変数を使用して同じイテレータ（ジェネレータ）を複数回使いまわしています。

```icon:素数を無限に生成するジェネレータ（再掲）
 procedure sieve()
   # 変数 i を使って、ジェネレータを使いまわしている
   every i:=seq(2) & not(every i%(2 to i-1)=0 & break) & suspend(i)
 end
 ```

では、このモジュールでも同じことをやってみましょう。

```go:以下はコンパイルエラー
i := Inc(2)
// ConstやRangeはintを引数に取るが、iはイテレータなので型が合わない
prime := Where(Const(i), All(Not(Eq(Mod(Const(i), Range(2, i, 1)), Const(0)))))
```

型が合わずにコンパイルエラーになってしまいました。よくよく考えると、変数として扱いたいのは `Inc(2)` そのものではなく、`Inc(2)` が**生成する各要素**です。

イテレータの要素を変数として扱う構文などもちろんありません。ここがGoでできる限界でしょうか...？

### 変数をbindで書き換える
活路はHaskellのdo記法にありました。

https://www.nslabs.jp/haskell-do-notation.rhtml

do記法は、変数代入のように扱えるシンタックスシュガーです。

```haskell:上記サイトより引用
import System.Environment 
 
main :: IO () 
main = do  
    args <- getArgs -- 代入のように見える 
    case args of 
        []   -> putStrLn "empty!!" 
        x:_  -> putStrLn x
    putStrLn "END"
```

変数のような値（上記の `args`）は、実態としては `bind` 関数の引数に渡された関数の仮引数となります。

```haskell:上記サイトより引用
import System.Environment 
 
main :: IO () 
main = getArgs >>= 
           \args -> (case args of 
                       []   -> putStrLn "empty!!" 
                       x:_  -> putStrLn x) >> 
               putStrLn "END"
```

また、`args` は取り出された中身の型となる[^monad1]（イテレータでいうと要素の型）ので、要件にもあっています。

#### イテレータを使いまわせるようにする
ところで、`bind` を実装する際1点問題があります。**イテレータを複数個所で使いまわすとそれぞれで要素が消費されてしまう** ため、正しく計算できません。

解決するには、使用箇所ごとにイテレータをコピーする必要があります。そこで、「イテレータを生成する関数」を引数に受け取り都度生成できるようにします。

シグネチャが複雑なので、以下 (Gen) とします[^alias]。

```go
type Gen[V any] = func() iter.Seq[V]
```

（先に紹介した `Inc`, `Range`, `Not`, `Mul` も、実際にはイテレータを生成する関数を返すように実装しています）

これをふまえると、 `Bind` は以下のように実装できます。

```go
func Bind[V, W any](gen Gen[V], f func(V) Gen[W]) Gen[W] {
	return func() iter.Seq[W] {
		return func(yield func(W) bool) {
			seq := gen()

			for vVal := range seq {
				// 要素に関数を適用し、返ってきたイテレータをループ
				wGen := f(vVal)
				wSeq := wGen()

				for wVal := range wSeq {
					if !yield(wVal) {
						return
					}
				}
			}
		}
	}
}
```

```go:使用例
Bind(Range(1, 5, 1), func(i int) Gen[int] {
	return Add(Const(i), Const(i))
}) // [2, 4, 6, 8]
```

#### 補足
「`Bind` という名前は適切なのか」、「イテレータに使用してよいのか」という疑問が湧いてくる方もいるかと思います。
少なくとも、モジュールで用意されている `func(V) Gen[W]` 型の関数の範囲ではモナド則を満たしています[^monad]。

`var x: V`, `func f(V) Gen[W]`,  `var m: Gen[V]` に対して以下を満たす [^equation]：

1. 左単位元結合： `Bind(Const(x), f)` == `f(x)`
1. 右単位元結合：`Bind(m, const)` == `m`
1. 結合律：`Bind(Bind(m, f), g)` == `Bind(m, func(x int) Gen[int] { return Bind(f(x), g) })`

## 先頭要素のみ切り取る
イテレータは要素を無限に生成しますが、プログラムが終わらないと使いづらいこともあるでしょう。
最後に、先頭n個のみ取得する関数も作っておきます。

```go
func Head[V any](gen Gen[V], n int) Gen[V] {
	return func() iter.Seq[V] {
		return func(yield func(V) bool) {
			seq := gen()
			next, stop := iter.Pull(seq)
			defer stop()
			for _ = range n {
				v, ok := next()
				if !ok {
					return
				}
				if !yield(v) {
					return
				}
			}
		}
	}
}
```

```go
Head(Inc(1), 10) // 1 2 3 4 5 6 7 8 9 10
```

これで素数を求めるイテレータの準備が整いました。

（`Where` と `All` の実装は割愛しましたが、興味のある方は[実装](https://github.com/Syuparn/itermania/blob/main/iter.go)をご覧ください）

# おわりに
以上、イテレータを濫用するためのモジュールの紹介でした。みなさんも、1.23リリースに備えてイテレータ ~~で遊んで~~ を試してみてはいかがでしょうか？

[^alias]: Go1.23時点ではジェネリクスの型エイリアスはexperimentalのため、 `GOEXPERIMENT=aliastypeparams GODEBUG=gotypesalias=1` の指定が必要です。
[^slice]: もちろん `FromSlice` を使用しても可能ですが、よく使う処理なので別関数にしました。
[^icon]: 今回再現したのはジェネレータの機能のみです。ゴール指向評価（計算が失敗する（=結果がfalseになる）とループを打ち切る）は採用していません。
[^monad]: 副作用がなければおそらくモナドになると思いますが（反例が思いつかない）、証明はしていません。
[^equation]: 関数としては等価ですが、上記を `==` 演算子で比較することはできません(Goでは関数は `nil` としか比較できないため)。
[^monad1]: ふわっとした書き方ですみません。モナドの話はあとで出てきます。