関数型に対するrange

Range Over Function Types by Ian Lance Taylor

はじめに

本記事は、GopherCon 2024での私の講演をブログ記事にしたものです。

GopherCon 2024 での講演動画

関数型に対するrangeは、Go 1.23で導入された新しい言語機能です。本記事では、なぜこの新機能を追加したのか、それが具体的に何なのか、そしてどのように使うのかを説明します。

なぜ導入したのか

Go 1.18以降、Goでは新しいジェネリックなコンテナ型を書けるようになりました。例として、mapの上に実装された非常にシンプルなジェネリック型である、次のSet型を考えてみましょう。

// Setは要素の集合を保持します。
type Set[E comparable] struct {
    m map[E]struct{}
}

// Newは新しい[Set]を返します。
func New[E comparable]() *Set[E] {
    return &Set[E]{m: make(map[E]struct{})}
}

当然ながら、Set型には要素を追加する方法と、要素が存在するかを確認する方法が必要です。ここでの詳細は重要ではありません。

// Addはsetに要素を追加します。
func (s *Set[E]) Add(v E) {
    s.m[v] = struct{}{}
}

// Containsは要素がsetの中にあるかどうかを報告します。
func (s *Set[E]) Contains(v E) bool {
    _, ok := s.m[v]
    return ok
}

そしてとりわけ、2つのsetの和集合を返す関数も欲しいところです。

// Unionは2つのsetの和集合を返します。
func Union[E comparable](s1, s2 *Set[E]) *Set[E] {
    r := New[E]()
    // Setの内部フィールドmに対してfor/rangeしていることに注意。
    // s1とs2の中のmapをループしています。
    for v := range s1.m {
        r.Add(v)
    }
    for v := range s2.m {
        r.Add(v)
    }
    return r
}

ここでUnion関数の実装を少し見てみましょう。2つのsetの和集合を計算するには、それぞれのsetに含まれるすべての要素を取得する方法が必要です。このコードでは、set型のエクスポートされていないフィールドに対してfor/range文を使っています。これがうまくいくのは、Union関数がsetパッケージの中で定義されている場合に限られます。

しかし、setの中のすべての要素をループしたい理由はたくさん考えられます。このsetパッケージは、利用者がそれを行うための何らかの方法を提供しなければなりません。

それはどのように実現すればよいでしょうか。

Setの要素をPushする

一つのアプローチは、関数を引数に取るSetのメソッドを用意して、Set内のすべての要素に対してその関数を呼び出すというものです。これをPushと呼びます。Setがすべての値をその関数へ押し出す(push)からです。ここでは、その関数がfalseを返したら呼び出しをやめます。

func (s *Set[E]) Push(f func(E) bool) {
    for v := range s.m {
        if !f(v) {
            return
        }
    }
}

Goの標準ライブラリでは、この一般的なパターンが sync.Map.Range メソッドや flag.Visit 関数、filepath.Walk 関数のようなケースで使われているのを見かけます。これはあくまで一般的なパターンであり、厳密に同一のものではありません。実際、これら3つの例はどれも全く同じようには動作しません。

Pushメソッドを使ってsetのすべての要素を出力するコードは次のようになります。要素に対してやりたいことを行う関数を渡してPushを呼び出します。

func PrintAllElementsPush[E comparable](s *Set[E]) {
    s.Push(func(v E) bool {
        fmt.Println(v)
        return true
    })
}

Setの要素をPullする

Setの要素をループするもう一つのアプローチは、関数を返すというものです。この関数は呼び出されるたびに、Setの中の値と、その値が有効かどうかを示すbool値を返します。ループがすべての要素を通過し終えると、このbool値はfalseになります。この場合、これ以上値が不要になったときに呼び出せるstop関数も必要になります。

この実装では2つのチャネルの組を使います。1つはset内の値のためのもので、もう1つは値の返却を止めるためのものです。値をチャネルに送信するためにゴルーチンを使います。next関数は要素用チャネルから読み込むことでsetから要素を返し、stop関数はstop用チャネルを閉じることでゴルーチンに終了を伝えます。値がこれ以上不要になったときにゴルーチンが確実に終了するように、このstop関数が必要です。

// Pullは、sの各要素と、その値が有効かどうかを示すboolを返す
// next関数を返します。next関数の呼び出しが終わったらstop関数を
// 呼び出す必要があります。
func (s *Set[E]) Pull() (func() (E, bool), func()) {
    ch := make(chan E)
    stopCh := make(chan bool)

    go func() {
        defer close(ch)
        for v := range s.m {
            select {
            case ch <- v:
            case <-stopCh:
                return
            }
        }
    }()

    next := func() (E, bool) {
        v, ok := <-ch
        return v, ok
    }

    stop := func() {
        close(stopCh)
    }

    return next, stop
}

標準ライブラリの中には、これと全く同じ動作をするものはありません。runtime.CallersFramesreflect.Value.MapRange はどちらも似ていますが、関数を直接返すのではなく、メソッドを持つ値を返します。

Pullメソッドを使ってSetのすべての要素を出力するコードは次のようになります。Pullを呼び出して関数を取得し、その関数をforループの中で繰り返し呼び出します。

func PrintAllElementsPull[E comparable](s *Set[E]) {
    next, stop := s.Pull()
    defer stop()
    for v, ok := next(); ok; v, ok = next() {
        fmt.Println(v)
    }
}

アプローチを標準化する

ここまで、setのすべての要素をループする2つの異なるアプローチを見てきました。Goの様々なパッケージが、これらやその他いくつかのアプローチを使っています。つまり、新しいGoのコンテナパッケージを使い始めるたびに、新しいループの仕組みを学ばなければならないかもしれないということです。また、コンテナ型ごとにループの扱い方が異なるため、複数の異なる種類のコンテナに対して動作する単一の関数を書くことができないということでもあります。

私たちは、コンテナをループするための標準的なアプローチを整備することで、Goのエコシステムを改善したいと考えています。

イテレータ

これはもちろん、多くのプログラミング言語で生じる問題です。

1994年に最初に出版された、有名な書籍『デザインパターン』では、これをイテレータパターンと呼んでいます。イテレータを使うのは、「集約オブジェクトの内部表現を公開することなく、その要素に順番にアクセスする方法を提供する」ためです。この引用文の中で集約オブジェクトと呼ばれているものが、私がこれまでコンテナと呼んできたものです。集約オブジェクト、つまりコンテナとは、これまで議論してきたSet型のように、他の値を保持する値のことにすぎません。

プログラミングにおける多くのアイデアと同様に、イテレータの起源は1970年代に開発されたBarbara LiskovのCLU言語にまで遡ります。

現在では、C++、Java、JavaScript、Python、Rustをはじめとする多くの主要な言語が、何らかの形でイテレータを提供しています。

しかし、バージョン1.23より前のGoにはそれがありませんでした。

For/range文

ご存じの通り、Goにはスライス、配列、mapという言語組み込みのコンテナ型があります。そして、内部表現を公開することなくそれらの値の要素にアクセスする方法として、for/range文があります。for/range文はGoの組み込みコンテナ型に対して動作します(そして文字列、チャネル、さらにGo 1.22からはintに対しても動作します)。

for/range文は反復処理ではありますが、今日の主要な言語に見られるようなイテレータではありません。とはいえ、Set型のようなユーザー定義のコンテナに対してfor/rangeを使って反復処理できれば嬉しいものです。

しかし、バージョン1.23より前のGoはこれをサポートしていませんでした。

今回のリリースでの改善

Go 1.23では、ユーザー定義のコンテナ型に対するfor/rangeと、標準化された形式のイテレータの両方をサポートすることに決めました。

for/range文を拡張し、関数型に対するrangeをサポートするようにしました。これがユーザー定義のコンテナのループにどう役立つかは、この後見ていきます。

また、関数型をイテレータとして使うことをサポートする型と関数を標準ライブラリに追加しました。イテレータの標準的な定義があることで、異なるコンテナ型に対してもスムーズに動作する関数を書けるようになります。

一部の関数型に対するrange

改良されたfor/range文は、任意の関数型をサポートするわけではありません。Go 1.23の時点では、単一の引数を取る関数に対するrangeをサポートします。この単一の引数自体は、0個から2個の引数を取りboolを返す関数でなければなりません。慣習的に、これをyield関数と呼びます。

func(yield func() bool)

func(yield func(V) bool)

func(yield func(K, V) bool)

Goにおいてイテレータと言うとき、それはこれら3つの型のいずれかを持つ関数を指します。この後説明するように、標準ライブラリにはもう1種類のイテレータがあります。pullイテレータです。標準的なイテレータとpullイテレータを区別する必要があるときは、標準的なイテレータをpushイテレータと呼びます。この後見るように、yield関数を呼び出すことで値の列を押し出す(push)からです。

標準的な(push)イテレータ

イテレータを使いやすくするために、新しい標準ライブラリパッケージiterでは、SeqSeq2 という2つの型を定義しています。これらはイテレータ関数の型、つまりfor/range文で使える型に付けられた名前です。イテレータは値の列(sequence)を反復処理することから、Seqという名前はsequenceの略になっています。

package iter

type Seq[V any] func(yield func(V) bool)

type Seq2[K, V any] func(yield func(K, V) bool)

// 今のところ、Seq0はありません

SeqSeq2の違いは、Seq2がmapのキーと値のようなペアの列であるという点だけです。本記事では単純化のためSeqに焦点を当てますが、ここで述べる内容のほとんどはSeq2にも当てはまります。

イテレータがどのように動作するかは、例で説明するのが一番わかりやすいでしょう。ここでは、SetのメソッドAllが関数を返します。Allの戻り値の型は iter.Seq[E] なので、これがイテレータを返すことがわかります。

// Allはsの要素に対するイテレータです。
func (s *Set[E]) All() iter.Seq[E] {
    return func(yield func(E) bool) {
        for v := range s.m {
            if !yield(v) {
                return
            }
        }
    }
}

このイテレータ関数自体は、別の関数であるyield関数を引数に取ります。イテレータはsetの中のすべての値に対してyield関数を呼び出します。この場合、イテレータ、つまりSet.Allが返す関数は、先ほど見たSet.Push関数によく似ています。

これがイテレータの動作の仕組みです。ある値の列に対して、その列の各値でyield関数を呼び出します。yield関数がfalseを返したら、これ以上値は不要ということなので、必要な後片付けを行ったうえでイテレータは単にreturnすればよいのです。yield関数が一度もfalseを返さなければ、その列のすべての値でyieldを呼び出した後にイテレータはreturnするだけで構いません。

これが仕組みですが、初めてこれを目にしたときの最初の反応はおそらく「ここにはたくさんの関数が飛び交っているな」というものでしょう。それは間違っていません。ここでは2つの点に注目してみましょう。

1つ目は、この関数のコードの最初の1行さえ乗り越えれば、イテレータの実際の実装は非常にシンプルだということです。setのすべての要素に対してyieldを呼び出し、yieldがfalseを返したら止まる、というだけです。

        for v := range s.m {
            if !yield(v) {
                return
            }
        }

2つ目は、これを使うのが本当に簡単だということです。s.All を呼び出してイテレータを取得し、for/rangeを使ってsのすべての要素をループします。for/range文は任意のイテレータをサポートしており、これがいかに使いやすいかを示しています。

func PrintAllElements[E comparable](s *Set[E]) {
    for v := range s.All() {
        fmt.Println(v)
    }
}

このようなコードでは、s.All はメソッドであり、関数を返します。私たちは s.All を呼び出し、それが返す関数に対してfor/rangeを使ってrangeしています。今回の場合、Set.All をイテレータ関数を返す関数にするのではなく、Set.All 自体をイテレータ関数にすることもできたはずです。しかし、イテレータを返す関数が引数を取る必要がある場合や、何らかの準備作業を行う必要がある場合など、それがうまくいかないケースもあります。慣習として、私たちはすべてのコンテナ型がイテレータを返すAllメソッドを提供することを推奨しています。そうすることで、プログラマはAllに直接rangeすべきか、それともAllを呼び出してrangeできる値を取得すべきかを覚えておく必要がなくなります。常に後者の方法を使えばよいのです。

考えてみればわかる通り、コンパイラは s.All が返すイテレータに渡すyield関数を作るために、ループを調整しているはずです。これを効率的にし、ループ内のbreakやpanicなどを正しく処理するために、Goのコンパイラとランタイムにはかなりの複雑さがあります。本記事ではその詳細には触れません。幸いなことに、この機能を実際に使う上では実装の詳細は重要ではありません。

Pullイテレータ

ここまで、for/rangeループでイテレータを使う方法を見てきました。しかし、単純なループだけがイテレータの使い方ではありません。例えば、2つのコンテナを並行して反復処理する必要がある場合もあります。それはどのように行えばよいでしょうか。

答えは、別の種類のイテレータ、pullイテレータを使うというものです。標準的なイテレータ、すなわちpushイテレータとも呼ばれるものは、yield関数を引数に取り、それを呼び出すことで列の中の各値をpushする関数であることをこれまで見てきました。

pullイテレータはその逆の動きをします。呼び出すたびに、列の中の次の値を返すように書かれた関数です。

覚えやすいように、この2種類のイテレータの違いをもう一度まとめます。

  • pushイテレータは、列の中の各値をyield関数にpushします。pushイテレータはGoの標準ライブラリにおける標準的なイテレータであり、for/range文によって直接サポートされます。
  • pullイテレータはその逆に動作します。呼び出すたびに、列から次の値を引き出して返します。pullイテレータはfor/range文によって直接サポートされているわけではありませんが、pullイテレータをループする普通のfor文を書くのは簡単です。実際、先ほどSet.Pullメソッドの使用例を見たときに、その例をすでに目にしています。

pullイテレータを自分で書くこともできますが、通常はその必要はありません。新しい標準ライブラリ関数 iter.Pull は、標準的なイテレータ、つまりpushイテレータである関数を受け取り、関数のペアを返します。1つ目はpullイテレータで、呼び出すたびに列の中の次の値を返す関数です。2つ目は、pullイテレータの利用を終えたときに呼び出すべきstop関数です。これは先ほど見たSet.Pullメソッドと似ています。

iter.Pull が返す1つ目の関数、すなわちpullイテレータは、値とその値が有効かどうかを示すbooleanを返します。このbooleanは列の終端でfalseになります。

iter.Pull がstop関数を返すのは、列を最後まで読み切らない場合に備えてのことです。一般的なケースでは、iter.Pull の引数であるpushイテレータは、ゴルーチンを起動したり、反復処理の完了時に後片付けが必要な新しいデータ構造を構築したりすることがあります。pushイテレータは、yield関数がfalseを返したとき、つまりこれ以上値が不要であることを意味するタイミングで、後片付けを行います。for/range文で使われる場合、for/range文は、break文などの理由でループが早期に終了する場合でも、yield関数が確実にfalseを返すようにしてくれます。一方pullイテレータの場合、yield関数を強制的にfalseにする方法がないため、stop関数が必要になります。

別の言い方をすれば、stop関数を呼び出すと、pushイテレータによってyield関数が呼び出されたときにfalseを返すようになる、ということです。

厳密に言えば、pullイテレータが列の終端に達したことを示すfalseを返した場合、stop関数を呼び出す必要はありません。しかし、常に呼び出すようにしておく方が普通は単純です。

ここに、pullイテレータを使って2つの列を並行して走査する例を示します。この関数は、2つの任意の列が同じ順序で同じ要素を含んでいるかどうかを報告します。

// EqSeqは、2つのイテレータが同じ順序で同じ要素を
// 含んでいるかどうかを報告します。
func EqSeq[E comparable](s1, s2 iter.Seq[E]) bool {
    next1, stop1 := iter.Pull(s1)
    defer stop1()
    next2, stop2 := iter.Pull(s2)
    defer stop2()
    for {
        v1, ok1 := next1()
        v2, ok2 := next2()
        if !ok1 {
            return !ok2
        }
        if ok1 != ok2 || v1 != v2 {
            return false
        }
    }
}

この関数は iter.Pull を使って、2つのpushイテレータ s1s2 をpullイテレータに変換します。defer文を使うことで、それらのpullイテレータの利用が終わったときに確実に停止させています。

その後コードはループし、pullイテレータを呼び出して値を取得します。1つ目の列が終わっていれば、2つ目の列も終わっていればtrueを、そうでなければfalseを返します。値が異なっていればfalseを返します。それ以外の場合はループして次の2つの値をpullします。

pushイテレータと同様に、pullイテレータを効率的にするためにGoランタイムにはいくらかの複雑さがありますが、これは実際に iter.Pull 関数を使うコードには影響しません。

イテレータについての補足

これで、関数型に対するrangeとイテレータについて知っておくべきことはすべて説明しました。ぜひ活用してみてください。

とはいえ、触れておく価値のある話がまだいくつか残っています。

アダプタ

イテレータの標準的な定義があることの利点の一つは、それを使う標準的なアダプタ関数を書けるようになることです。

例えば、値の列をフィルタリングして新しい列を返す関数を考えてみましょう。このFilter関数はイテレータを引数に取り、新しいイテレータを返します。もう一つの引数は、Filterが返す新しいイテレータにどの値を含めるべきかを決めるフィルタ関数です。

// Filterは、sの要素のうちfがtrueを返すものだけを
// 含む列を返します。
func Filter[V any](f func(V) bool, s iter.Seq[V]) iter.Seq[V] {
    return func(yield func(V) bool) {
        for v := range s {
            if f(v) {
                if !yield(v) {
                    return
                }
            }
        }
    }
}

先ほどの例と同様に、関数のシグネチャは最初に見たときは複雑に見えます。しかしシグネチャさえ乗り越えれば、実装は単純明快です。

        for v := range s {
            if f(v) {
                if !yield(v) {
                    return
                }
            }
        }

このコードは入力イテレータに対してrangeし、フィルタ関数をチェックして、出力イテレータに含めるべき値でyieldを呼び出します。

Filterの使用例は、この後お見せします。

(現時点ではGoの標準ライブラリにFilterに相当するものはありませんが、将来のリリースで追加されるかもしれません。)

二分木

コンテナ型をループする際にpushイテレータがいかに便利かを示す例として、次のシンプルな二分木型を考えてみましょう。

// Treeは二分木です。
type Tree[E any] struct {
    val         E
    left, right *Tree[E]
}

木に値を挿入するコードはここでは示しませんが、当然、木の中のすべての値をrangeする何らかの方法が必要です。

実は、イテレータのコードはboolを返すようにした方が書きやすくなります。for/rangeがサポートする関数型は何も返さないため、ここでのAllメソッドは、pushと呼ばれるイテレータ本体を呼び出してそのbool結果を無視する、小さな関数リテラルを返します。

// Allはtの中の値に対するイテレータを返します。
func (t *Tree[E]) All() iter.Seq[E] {
    return func(yield func(E) bool) {
        t.push(yield)
    }
}

// pushはすべての要素をyield関数にpushします。
func (t *Tree[E]) push(yield func(E) bool) bool {
    if t == nil {
        return true
    }
    return t.left.push(yield) &&
        yield(t.val) &&
        t.right.push(yield)
}

pushメソッドは再帰を使って木全体を走査し、各要素に対してyieldを呼び出します。yield関数がfalseを返した場合、そのfalseはスタックを遡ってそのまま返されていきます。そうでなければ、反復処理が完了した時点で単に返るだけです。

これは、このイテレータのアプローチを使えば、複雑なデータ構造であってもループがいかに簡単になるかを示しています。木の中の位置を記録するための別個のスタックを維持する必要はありません。ゴルーチンの呼び出しスタックをそのまま使えばよいのです。

新しいイテレータ関数

また、Go 1.23ではイテレータと連携するslicesパッケージとmapsパッケージの関数も新たに追加されました。

以下は、slicesパッケージの新しい関数です。AllValues はスライスの要素に対するイテレータを返す関数です。Collect はイテレータから値を取り出し、それらの値を保持するスライスを返します。その他の関数についてはドキュメントを参照してください。

以下は、mapsパッケージの新しい関数です。AllKeysValues はmapの内容に対するイテレータを返します。Collect はイテレータからキーと値を取り出し、新しいmapを返します。

標準ライブラリ関数の利用例

これらの新しい関数を、先ほど見たFilter関数と組み合わせて使う例を示します。この関数はintからstringへのmapを受け取り、mapの中で引数nより長い値だけを保持するスライスを返します。

// LongStringsは、mの中で長さがn以上である値だけの
// スライスを返します。
func LongStrings(m map[int]string, n int) []string {
    isLong := func(s string) bool {
        return len(s) >= n
    }
    return slices.Collect(Filter(isLong, maps.Values(m)))
}

maps.Values 関数は m の値に対するイテレータを返します。Filter はそのイテレータを読み取り、長い文字列だけを含む新しいイテレータを返します。slices.Collect はそのイテレータから読み取って新しいスライスに格納します。

もちろん、これを行うループは十分簡単に書けますし、多くの場合はループの方が明快でしょう。誰もが常にこのスタイルでコードを書くべきだと勧めたいわけではありません。とはいえ、イテレータを使う利点は、この種の関数がどんな列に対しても同じように動作することです。この例では、Filterのコードを一切変更することなく、入力としてmapを、出力としてスライスを使っていることに注目してください。

ファイル内の行をループする

ここまで見てきた例のほとんどはコンテナに関するものでしたが、イテレータは柔軟に使えます。

バイトスライス内の行をループする、イテレータを使わない次のシンプルなコードを考えてみましょう。これは書くのが簡単で、かなり効率的です。

    nl := []byte{'\n'}
    // 末尾の空行を避けるため、末尾の改行をトリムする。
    for _, line := range bytes.Split(bytes.TrimSuffix(data, nl), nl) {
        handleLine(line)
    }

しかし、bytes.Split は行を保持するためのバイトスライスのスライスをアロケートして返します。ガベージコレクタは、いずれそのスライスを解放するために多少の作業をしなければなりません。

ここに、あるバイトスライスの行に対するイテレータを返す関数を示します。おなじみのイテレータのシグネチャさえ過ぎれば、関数自体は非常にシンプルです。data から何も残らなくなるまで行を取り出し続け、各行をyield関数に渡します。

// Linesはdataの中の行に対するイテレータを返します。
func Lines(data []byte) iter.Seq[[]byte] {
    return func(yield func([]byte) bool) {
        for len(data) > 0 {
            line, rest, _ := bytes.Cut(data, []byte{'\n'})
            if !yield(line) {
                return
            }
            data = rest
        }
    }
}

これで、バイトスライスの行をループするコードは次のようになります。

    for line := range Lines(data) {
        handleLine(line)
    }

これは先ほどのコードと同じくらい書きやすく、行のスライスをアロケートする必要がない分、多少効率的です。

pushイテレータに関数を渡す

最後の例として、pushイテレータを必ずしもrange文の中で使う必要はないことを見てみましょう。

先ほど、setの各要素を出力するPrintAllElements関数を見ました。ここでは、setのすべての要素を出力する別の方法を示します。s.All を呼び出してイテレータを取得し、自分で書いたyield関数を渡すという方法です。このyield関数は単に値を出力してtrueを返すだけです。ここには2つの関数呼び出しがあることに注意してください。まず s.All を呼び出してイテレータ(それ自体が関数です)を取得し、次にその関数を自分で書いたyield関数とともに呼び出しています。

func PrintAllElements[E comparable](s *Set[E]) {
    s.All()(func(v E) bool {
        fmt.Println(v)
        return true
    })
}

このコードをこのように書く特別な理由はありません。これは単に、yield関数が魔法ではないことを示すための例にすぎません。yield関数は好きな関数を使えばよいのです。

go.modを更新する

最後に一点。すべてのGoモジュールは、使用する言語バージョンを指定しています。つまり、既存のモジュールで新しい言語機能を使うには、そのバージョンを更新する必要がある場合があります。これはすべての新しい言語機能に当てはまることであり、関数型に対するrangeに固有の話ではありません。関数型に対するrangeはGo 1.23で新しく導入されたので、これを使うには少なくともGo言語バージョン1.23を指定する必要があります。

言語バージョンを設定するには(少なくとも)4つの方法があります。

  • コマンドラインで go get go@1.23 を実行する(goディレクティブだけを編集する場合は go mod edit -go=1.23 を実行する)。
  • go.mod ファイルを手動で編集して go の行を変更する。
  • モジュール全体としては古い言語バージョンのままにしておき、特定のファイルでのみ //go:build go1.23 ビルドタグを使って関数型に対するrangeの利用を許可する。

By Ian Lance Taylor