Zenn
SODA Engineering Blog
😎

Go1.22で登場するかも！？開発中の新機能イテレータを使ってみる！

Pana
2023/09/01に公開
Golang
#
言語仕様
tech

導入

Go1.21が先日リリースされ、スライスとマップに関する汎用的な処理を扱う標準パッケージ (slicesとmaps) が導入されましたが、 直前になって入る予定の maps.Keys が削除されてしまいました。

これはイテレータが実装予定のため maps.Keys 等はイテレータの実装を待ってからの方が良いと判断されたためだと思われます。

Go1.22で実装予定のイテレータとはどういう機能なのか、イテレータにすることで何が嬉しいのかがよく分からなかったので調べてみました。

この記事で知れること

  • Goでのイテレータの実装がどのようになるのか (2023/08/30現在の実装)
  • イテレータのメリット

事前準備

  • gotip は開発中のGoのコードを扱うことができるCLIツールで、以下のコマンドでインストールすることができます
  • 2つ目のコマンドの末尾の数字 (510541) はGoのチームがコードをレビューするサイト (Gerrit) 上で割り振られた番号になります。 (GitHub上でのPRの番号と同じようなものです)
$ go install golang.org/dl/gotip@latest
$ gotip download 510541

ダウンロードできたらバージョンを確認してみます。

$ gotip version
go version devel go1.22-af4dc2ef9f Wed Aug 30 08:43:32 2023 -0400 darwin/amd64

ちゃんと開発中のGo1.22になっていることが確認できました。

イテレータの仕様をみてみる

イテレータのプロポーザルは https://github.com/golang/go/issues/61405 にあります。
冒頭の文章を抜粋して、どんな仕様になるのか軽くみてみます。

In the spec, the table that begins the section would have a few more rows added:

Range expression                                   1st value          2nd value

array or slice      a  [n]E, *[n]E, or []E         index    i  int    a[i]       E
string              s  string type                 index    i  int    see below  rune
map                 m  map[K]V                     key      k  K      m[k]       V
channel             c  chan E, <-chan E            element  e  E
integer             n  integer type                index    i int
function, 0 values  f  func(func()bool) bool
function, 1 value   f  func(func(V)bool) bool      value    v  V
function, 2 values  f  func(func(K, V)bool) bool   key      k  K      v          V

(意訳はじまり)
仕様では、表はいくつかの行が追加されたセクションから始まるだろう。
(意訳終わり)

現状の仕様を見てみると、channel までの記載になっており、integer, function, 0 values, function, 1 value, function, 2 values の部分の記載はありません。この部分がイテレータの追加にともなって、使用可能になる予定の文法であることがわかります。

さっそくコードを書いてみる

上記の表ではinteger n integer typeのパターンが一番簡単そうなので、この形式でコードを書いてみます。

package main

import "fmt"

func main() {
	for x := range 3 {
		fmt.Println(x)
	}
}

まずは現状のコードでは動かないことを確かめるため、Go1.21で実行してみます。

$ go version
go version go1.21.0 darwin/amd64

$ go run .
# github.com/k3forx/iterator
./main.go:6:17: cannot range over 10 (untyped int constant)

続いて gotip で実行してみます。ここでポイントなのが GOEXPERIMENT=range というフラグを渡さないと実行できないようになっています。

$ GOEXPERIMENT=range gotip run .
0
1
2

ちゃんと 0, 1, 2 が出力されました。

整数に対するイテレータについて

上記の整数に対するイテレータのコードに関して、プロポーザルでは以下のように述べられています。

If n is an integer type, then for x := range n { ... } would be completely equivalent to for x := T(0); x < n; x++ { ... }, where T is the type of n (assuming x is not modified in the loop body).
The additional spec text for range over integer is:

For an integer n, the index iteration values 0 through n-1 are produced, with the same type as n. If n <= 0, the loop does not run any iterations.

(意訳はじまり)
もし、nが整数型であれば、for x := range n { ... }はx := T(0; x < n; x++ { ... }と完全に等しくなるだろう。ここでTはnの型で、xがループの中で修正されないものと仮定する。
整数に関するrange overの追加の仕様のテキストは「整数nの場合、nと同じ型のインデックス反復値0からn-1が生成される。もしn<=0なら、ループは反復を行いません。」です。
（意訳おわり）

先ほどのコードで見たような for x := range n というコードは x := T(0); x < n; x++ { ... } という書き方と完全に等しくなるそうです。

さらに n が0以下の整数の場合は、イテレーションの処理が実行されないということなので、以下のようなコードで試してみます。

package main

import "fmt"

func main() {
	for x := range 0 {
		fmt.Println(x)
	}
}

実行してみます。

$ GOEXPERIMENT=range gotip run .

確かに何も表示されませんでした。

関数に対するイテレータについて

続いて関数に対するイテレータについてもみてみます。
関数に対するイテレータについては冒頭の引用した表の function, 0 values f func(func()bool) bool のパターンが簡単に実装できそうです。

プロポーザルに記載されている通りの引数を持つ関数 f を定義し、for rangeに入れ込みます。
コードは以下のような感じになるかと思います。

package main

import "fmt"

func main() {
	for range f {
		fmt.Println("for range starts")
	}
}

func f(func() bool) bool {
	fmt.Println("func f starts")
	return true
}

実行すると以下のような出力になります。

$ GOEXPERIMENT=range gotip run .
func f starts

func f starts は表示されますが、ループの中の fmt.Println("for range starts") はコンソールに表示されないですね。なぜでしょうか？

プロポーザルをみてみましょう。

If f is a function type of the form func(yield func(T1, T2)bool) bool, then for x, y := range f { ... } is similar to f(func(x T1, y T2) bool { ... }), where the loop body has been moved into the function literal, which is passed to f as yield.

(意訳はじまり)
もしfがfunc(yield func(T1, T2)bool) boolという形式の関数の場合、for x, y := range f { ... }はf(func(x T1, y T2) bool { ... })と似ている。ここではループ本文はfにyieldとして関数リテラルに移動する。
(意訳終わり)

つまり、ループの中身を実行するには引数の func() bool を何かしらの変数として受け取って実行する必要がありそうです。

実際にやってみます。

package main

import "fmt"

func main() {
	for range f {
		fmt.Println("for range starts")
	}
}

// func() boolの変数をyieldとして受け取って実行する
func f(yield func() bool) bool {
	fmt.Println("func f starts")
	yield()
	return true
}

実行してみると以下のようになりました。確かに func f starts と for range starts が表示されました。

$ GOEXPERIMENT=range gotip run .
func f starts
for range starts

for rangeが値を受け取るパターンもやってみます。

コードは以下のようになります。

package main

import "fmt"

func main() {
	for x := range f {
		fmt.Println("for range starts")
		fmt.Printf("x: %d\n", x)
	}
}

func f(yield func(i int) bool) bool {
	fmt.Println("func f starts")
	yield(3)
	return true
}

実行してみると、ちゃんと x: 3 とコンソールに表示されました。

$ GOEXPERIMENT=range gotip run .
func f starts
for range starts
x: 3

yieldの返り値のboolの役割は？

さて、yield の返り値が bool になっていますが、この bool の役割はなんでしょうか？
再びプロポーザルを見てみます。

The boolean result from yield indicates to f whether to keep iterating.

(意訳はじまり)
yield からのブール値の結果は f が反復を続けるかどうかを決めるものです。
(意訳終わり)

まずは反復を続ける/続けないで yield の返り値がどういう値になるのかみてみます。

package main

import "fmt"

func main() {
	for x := range f {
		fmt.Println("for range starts")
		fmt.Printf("x: %d\n", x)
		if x == 2 {
			break // xが2の時にイテレーションをストップさせたい
		}
	}
}

func f(yield func(i int) bool) bool {
	fmt.Println("func f starts")
	// yieldに1, 2, 3の数字を渡し、yieldの返り値を見る
	for _, v := range []int{1, 2, 3} {
		fmt.Println(yield(v))
	}
	return true
}

実行してみます。

$ GOEXPERIMENT=range gotip run .
func f starts
for range starts
x: 1
true
for range starts
x: 2
false # イテレーションを止めたい時はyieldはfalseを返す
for range starts
x: 3
true

yield(i) の返り値としては、イテレーションを続けるときは true 、 中断したい時は false が返ってくるようです。

プロポーザルにも以下のように記載あります。

The return value from the yield function reports whether f should continue iterating. For example, if the loop body executes a break statement, the corresponding call to yield returns false.

(意訳はじまり)
yield 関数の返り値はfが反復を続けるべきかどうかを報告する。例えば、ループ本文が break を実行したときは、対応する yield のコールは false を返します。
(意訳終わり)

つまり、 x=2 の時にイテレーションをストップさせたい時は、以下のように yield からの返り値を拾ってあげる必要があるようです。

実際に以下のコードで試してみます。

package main

import "fmt"

func main() {
	for x := range f {
		fmt.Println("for range starts")
		fmt.Printf("x: %d\n", x)
		if x == 2 {
			break
		}
	}
}

func f(yield func(i int) bool) bool {
	fmt.Println("func f starts")
	for _, v := range []int{1, 2, 3} {
		// v=2 (x=2) の時にyieldがfalseを返すので、
		// 関数fの実行をreturnで終わらせる
		if !yield(v) {
			return true
		}
	}
	return true
}

実行してみます。

$ GOEXPERIMENT=range gotip run .
func f starts
for range starts
x: 1
for range starts
x: 2

先ほどの結果と違って x=3 の時のループ本文が実行されず、x=2 の時でイテレーションがストップしています。プロポーザルに記載されている通りの挙動です。

さらにプロポーザルには以下の記述もあります。

The use of a synthesized yield function does not change the semantics of the loop body. In particular, break, continue, defer, goto, and return statements all behave in a loop body ranging over a function exactly as they do in a loop body ranging over other types.

(意訳はじまり)
合成されたyield関数の使用は、ループ本体のセマンティクスを変更しない。特に、break、continue、defer、goto、return文はすべて、関数に及ぶループ本体でも、他の型に及ぶループ本体とまったく同じように動作する。
(意訳終わり)

先ほどの return を break に変えて、fmt.Println("func f ends") を関数 f の return の直前に置いてみます。

package main

import "fmt"

func main() {
	for x := range f {
		fmt.Println("for range starts")
		fmt.Printf("x: %d\n", x)
		if x == 2 {
			break
		}
	}
}

func f(yield func(i int) bool) bool {
	fmt.Println("func f starts")
	for _, v := range []int{1, 2, 3} {
		if !yield(v) {
			break // breakに変更
		}
	}
	fmt.Println("func f ends") // 追加
	return true
}

動かしてみます。

$ GOEXPERIMENT=range gotip run .
func f starts
for range starts
x: 1
for range starts
x: 2
func f ends

確かに func f ends が表示されました。言うまででもないかもしれませんが、この文言は break を return に変えると表示されません。

関数 f の返り値のboolの役割は？

先ほどまで yield が返すbool値の役割を見てみましたが、関数 f が返すbool値の役割はなんでしょうか？

プロポーザルには以下のように記載があります。

The boolean result from f itself is ignored in this usage but present to allow easier composition of iterators.

(意訳はじまり)
この使用方法では、f のbooleanの結果自体は無視されるが、イテレータの合成を容易にするために存在する。
(意訳終わり)

複数のイテレータを組み合わせて使うときに、関数 f の返り値を使用して、後続のイテレータに処理をつなげるか判断するとかそういった使用を想定しているようです。

先ほど if !yield(v) { ... } の箇所を return　true としていましたが、return false とするのが実装としては正しそうです。

で、結局何が便利になるのでしょうか？

ここまでイテレータの書き方を見てきましたが、イテレータが導入されることで何が便利になるのでしょうか？

この疑問に対する回答もプロポーザルあり、以下のような記載がありました。

The most recent motivation is the addition of generics, which we expect will lead to custom containers such as ordered maps, and it would be good for those custom containers to work well with range loops.

(意訳はじまり)
最も最近の動機は、ジェネリクスの追加で、これは順序付きマップのようなカスタム・コンテナにつながると期待している。
(意訳終わり)

Another equally good motivation is to provide a better answer for the many functions in the standard library that collect a sequence of results and return the whole thing as a slice. If the results can be generated one at a time, then a representation that allows iterating over them scales better than returning an entire slice. We do not have a standard signature for functions that represent this iteration. Adding support for functions in range would both define a standard signature and provide a real benefit that would encourage its use.

(意訳はじまり)
もうひとつの同じような動機は、標準ライブラリにある、一連の結果を収集し、全体をスライスとして返す多くの関数に対して、より良い答えを提供することである。結果が一度に1つずつ生成されるのであれば、スライス全体を返すよりも、結果を反復処理できる表現の方がスケールが大きくなります。この反復を表す関数の標準的なシグネチャはありません。range関数のサポートを追加することは、標準シグネチャを定義すると同時に、その使用を促進する真の利点を提供することになる。
(意訳終わり)

For example, here are a few functions from the standard library that return slices but probably merit forms that return iterators instead:

strings.Split
strings.Fields
bytes variants of the above
regexp.Regexp.FindAll and friends

(意訳はじまり)
スライスを返すが代わりにイテレータを返すことによってメリットが得られるような標準ライブラリの関数をここでは例としていくつか提示する。
(意訳終わり)

ジェネリクスと組み合わせたり、スライスを返している標準ライブラリの関数をイテレータに返したりするようにするとイテレータの恩恵が得られると書いてあります。

実際に書いてみる

実際にジェネリクスと組み合わせて、slices.Compact 関数の車輪の再開発をしてみます。

slices.Compact 関数の挙動

この関数は隣り合った数字が同じ場合はそれを1つにまとめるという挙動をします。
例えば、[]int{0, 1, 1, 2, 3, 5, 8} を []int{0, 1, 2, 3, 5, 8} とする関数です。

以下のようなコードを考えます.

package main

import (
	"fmt"
	"slices"
)

func main() {
	seq := []int{0, 1, 1, 2, 3, 5, 8}
	for _, v := range slices.Compact(seq) {
		fmt.Printf("v: %d\n", v)
	}
}

実際に動かしてみます。

$ go version
go version go1.21.0 darwin/amd64

$ go run .
v: 0
v: 1
v: 2
v: 3
v: 5
v: 8

この挙動をイテレータを使って再現してみます。

車輪の再開発

以下のようなステップを踏んでイテレータで再実装してみます。

  1. イテレータを使ってスライスの中身を出力する
  2. イテレータの中で今現在の値と隣の値が同じ場合は処理をスキップする
  3. 任意の整数のスライスをイテレータに渡せるように関数を書き換える
  4. ジェネリクスに置き換える

まずは1番からやります。

対象のスライスを original として、イテレータの中に閉じ込めておきます。
単純なfor loopで値を yield に渡して x として受け取って出力してみます。

package main

import (
	"fmt"
)

func main() {
	for x := range f {
		fmt.Printf("x: %v\n", x)
	}
}

func f(yield func(num int) bool) bool {
	original := []int{0, 1, 1, 2, 3, 5, 8}
	for _, v := range original {
		if !yield(v) {
			return false
		}
	}
	return true
}

実行してみます。

GOEXPERIMENT=range gotip run .
x: 0
x: 1
x: 1
x: 2
x: 3
x: 5
x: 8

ちゃんと original の各要素がfor rangeの返り値 x として受け取られています。

2番目のステップとして、出力しようとする値と、その次の値が同じである場合は処理をスキップするようにします。

コードは以下のような感じになるでしょうか。

package main

import (
	"fmt"
)

func main() {
	for x := range f {
		fmt.Printf("x: %v\n", x)
	}
}

func f(yield func(num int) bool) bool {
	original := []int{0, 1, 1, 2, 3, 5, 8}
	for i, v := range original {
		// 最後の要素の場合はyieldを呼び出して、
		// 返り値がfalseならfalseを、trueならtrueを返して
		// fを終了させる
		if i+1 == len(original) {
			if !yield(v) {
				return false
			}
			return true
		}

		// イテレータの値が隣の値と同じ場合はyieldを呼び出さない
		if v == original[i+1] {
			continue
		}

		if !yield(v) {
			return false
		}
	}
	return true
}

実際に動かしてみます。

$ GOEXPERIMENT=range gotip run .
x: 0
x: 1
x: 2
x: 3
x: 5
x: 8

期待通り、隣同士同じ値の 1 は出力結果から省かれました。

続いて3番目のステップです。

original で定義してある変数を任意の整数のスライスにしたいので、関数 f を返す関数 compactInt を作成します。

コードは以下のようになると思います。

package main

import (
	"fmt"
)

func main() {
	for x := range compactInt([]int{0, 1, 1, 2, 3, 5, 8}) {
		fmt.Printf("x: %v\n", x)
	}
}

func compactInt(nums []int) func(yield func(num int) bool) bool {
	// returnで返している関数は先ほどの関数 `f` の中身とほぼ同じです
	return func(yield func(num int) bool) bool {
		for i, v := range nums {
			if i+1 == len(nums) {
				if !yield(v) {
					return false
				}
				return true
			}

			if v == nums[i+1] {
				continue
			}

			if !yield(v) {
				return false
			}
		}
		return true
	}
}

実際に実行してみます。

GOEXPERIMENT=range gotip run .
x: 0
x: 1
x: 2
x: 3
x: 5
x: 8

全く同じ結果が得られました。

いよいよ最後のステップです。

先ほど自作した compactInt を任意の型のスライスを受け取れるようにしてみます。厳密にはイテレータの中で == の演算を行なっているので、完全に任意の型のスライスが受け取れるわけではないです。

コードは以下のようになると思います。

package main

import (
	"fmt"
)

func main() {
	for x := range compact([]int{0, 1, 1, 2, 3, 5, 8}) {
		fmt.Printf("x: %v\n", x)
	}
}

// 任意の型のスライスだと `==` の演算ができないので、comparableな型のスライスにする
func compact[S ~[]E, E comparable](s S) func(yield func(val E) bool) bool {
	return func(yield func(val E) bool) bool {
		for i, v := range s {
			if i+1 == len(s) {
				if !yield(v) {
					return false
				}
				return true
			}

			if v == s[i+1] {
				continue
			}

			if !yield(v) {
				return false
			}
		}
		return true
	}
}

実際に動かしてみます。

$ GOEXPERIMENT=range gotip run .
x: 0
x: 1
x: 2
x: 3
x: 5
x: 8

結果が変わらないのでちゃんと slices.Compact 関数と同じ動きをしているようです🎉🎉🎉

slices.Compact を実行して、それに対してfor loopを回すというようなユースケースの場合は、イテレータを使う場合とそうでない場合でパフォーマンスに違いがありそうなので、後日余裕があれば調べてみたいと思います。

もっと実用的な例を考えてみる

車輪の再開発ではなく、実用的な例を考えてみました。

ある大きなスライスに対してそれを小さい塊 (チャンク) にわけて、その小さい塊に対して演算を行うケースをイテレータを使って実装してみました。

package main

import "fmt"

func main() {
	chunkLength := 3
	chunks := make([]int, chunkLength)
	nums := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

	for i, v := range iter(nums) {
		chunks[i%chunkLength] = v
		if (i+1)%chunkLength == 0 {
			fmt.Printf("chunk: %v\n", chunks)
			clear(chunks)
			continue
		}

		if (i + 1) == len(nums) {
			fmt.Printf("chunk: %v\n", chunks)
			clear(chunks)
			break
		}
	}
}

func iter(nums []int) func(yield func(i, v int) bool) bool {
	return func(yield func(i, v int) bool) bool {
		for i, v := range nums {
			if !yield(i, v) {
				return false
			}
		}
		return true
	}
}

動かしてみます。

$ GOEXPERIMENT=range gotip run .
chunk: [1 2 3]
chunk: [4 5 6]
chunk: [7 8 9]
chunk: [10 0 0]

従来のGoなら、まず大きなスライスをチャンクに分けるという処理をしたのちに、各チャンクに対して演算を行うという処理を実装すると思います。しかし、イテレータを使えば、チャンクに分ける処理を呼ばなくても、チャンクに分けつつ、そのチャンクに対する処理を実装できるメリットが見つかりました。

上記の例では長さが3のスライスに対して値を代入しているので、実際にチャンクごとに処理を実行するときに必要でない値まで使う必要があります。[10 0 0]ではなく、[10]のみが表示されるようにしてみました。

package main

import "fmt"

func main() {
	var chunks []int

	chunkLength := 3
	nums := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

	for i := range iter(nums) {
		if (i+1)%chunkLength == 0 {
			chunks = nums[i+1-chunkLength : i+1]
			fmt.Printf("chunk: %v\n", chunks)
			continue
		}

		if (i + 1) == len(nums) {
			n := len(nums) / chunkLength
			chunks = nums[n*chunkLength:]
			fmt.Printf("chunk: %v\n", chunks)
			break
		}
	}
}

func iter(nums []int) func(yield func(i int) bool) bool {
	return func(yield func(i int) bool) bool {
		for i := range nums {
			if !yield(i) {
				return false
			}
		}
		return true
	}
}

動かしてみます。

$ GOEXPERIMENT=range gotip run .
chunk: [1 2 3]
chunk: [4 5 6]
chunk: [7 8 9]
chunk: [10]

これで無駄のない処理になったかと思います。

所感

  • Go1.22でもしかすると実装されるかもしれないイテレータの書き方がわかりました
  • イテレータ難しいです
  • スライスに対して何か演算を行なって、得られた結果のスライスの各要素に対してfor loopを回すような場面ではイテレータの方がパフォーマンスが良いかもしれません (要調査)

参考文献

SODA Engineering Blog
SODA Engineering Blog

株式会社SODAの開発組織がお届けするZenn Publicationです。 是非Entrance Bookもご覧ください！ → recruit.soda-inc.jp/engineer

Discussion