Goブログ

関数型にわたる範囲

イアン・ランス・テイラー
2024年8月20日

はじめに

これはGopherCon 2024での私の講演のブログ投稿版です。

関数型にわたる範囲は、Go 1.23リリースの新しい言語機能です。このブログ投稿では、なぜこの新機能を追加するのか、具体的にどのような機能なのか、そしてどのように使用するかを説明します。

なぜ?

Go 1.18以降、Goで新しいジェネリックコンテナ型を作成できるようになりました。たとえば、マップの上に実装された非常に単純な`Set`型を考えてみましょう。

// Set holds a set of elements.
type Set[E comparable] struct {
    m map[E]struct{}
}

// New returns a new [Set].
func New[E comparable]() *Set[E] {
    return &Set[E]{m: make(map[E]struct{})}
}

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

// Add adds an element to a set.
func (s *Set[E]) Add(v E) {
    s.m[v] = struct{}{}
}

// Contains reports whether an element is in a set.
func (s *Set[E]) Contains(v E) bool {
    _, ok := s.m[v]
    return ok
}

そして、とりわけ、2つの集合の和集合を返す関数が必要になります。

// Union returns the union of two sets.
func Union[E comparable](s1, s2 *Set[E]) *Set[E] {
    r := New[E]()
    // Note for/range over internal Set field m.
    // We are looping over the maps in s1 and s2.
    for v := range s1.m {
        r.Add(v)
    }
    for v := range s2.m {
        r.Add(v)
    }
    return r
}

`Union`関数のこの実装を少し見てみましょう。2つの集合の和集合を計算するには、各集合に含まれるすべての要素を取得する方法が必要です。このコードでは、集合型の非公開フィールドに対してfor/rangeステートメントを使用しています。それは、`Union`関数が集合パッケージで定義されている場合にのみ機能します。

しかし、集合内のすべての要素をループしたい理由はたくさんあります。この集合パッケージは、ユーザーがそれを行うための何らかの方法を提供する必要があります。

どのように動作するべきでしょうか?

集合要素のプッシュ

1つのアプローチは、関数を受け取る`Set`メソッドを提供し、その関数を`Set`内のすべての要素で呼び出すことです。`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`メソッドを使用して集合のすべての要素を出力する方法は次のとおりです。要素に対して必要な処理を行う関数を使用して`Push`を呼び出します。

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

集合要素のプル

`Set`の要素をループするもう1つのアプローチは、関数を返すことです。関数が呼び出されるたびに、`Set`から値と、値が有効かどうかを報告するブール値が返されます。ループがすべての要素を処理したとき、ブール値の結果はfalseになります。この場合、値がこれ以上必要ないときに呼び出すことができる停止関数も必要です。

この実装では、集合の値用と値の返却を停止するための2つのチャネルのペアを使用します。ゴルーチンを使用してチャネルに値を送信します。`next`関数は要素チャネルから読み取ることで集合から要素を返し、`stop`関数は停止チャネルを閉じることでゴルーチンに終了するように指示します。値がこれ以上必要ないときにゴルーチンが確実に終了するように、`stop`関数が必要です。

// Pull returns a next function that returns each
// element of s with a bool for whether the value
// is valid. The stop function should be called
// when finished calling the next function.
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.CallersFrames``reflect.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)
    }
}

アプローチの標準化

集合のすべての要素をループする2つの異なるアプローチを見てきました。異なるGoパッケージはこれらのアプローチといくつかの他のアプローチを使用します。つまり、新しいGoコンテナパッケージを使い始めると、新しいループメカニズムを学ぶ必要がある場合があります。また、コンテナ型はループを異なる方法で処理するため、複数の異なるタイプのコンテナで動作する1つの関数を記述できないことも意味します。

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

イテレータ

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

1994年に初版が発行された、人気のデザインパターンブックは、これをイテレータパターンとして説明しています。イテレータを使用して、「基になる表現を公開することなく、集約オブジェクトの要素に順次アクセスする方法を提供します」。この引用が集約オブジェクトと呼んでいるのは、私がコンテナと呼んでいるものです。集約オブジェクト、つまりコンテナは、私たちが議論してきた`Set`型のように、他の値を保持する値です。

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

今日、多くの一般的な言語が、C++、Java、Javascript、Python、Rustなどを含め、何らかの形でイテレータを提供しています。

ただし、バージョン1.23より前のGoはそうではありませんでした。

For/range

誰もが知っているように、Goには言語に組み込まれているコンテナ型があります。スライス、配列、マップです。また、基になる表現を公開することなく、これらの値の要素にアクセスする方法があります。for/rangeステートメントです。for/rangeステートメントは、Goの組み込みコンテナ型(および文字列、チャネル、Go 1.22以降はint)で機能します。

for/rangeステートメントは反復処理ですが、今日の一般的な言語に現れるイテレータではありません。それでも、`Set`型のようなユーザー定義コンテナを反復処理するためにfor/rangeを使用できると便利です。

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

このリリースでの改善

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

ユーザー定義コンテナのループに役立つように、for/rangeステートメントを拡張して関数型にわたる範囲をサポートしました。以下で、これがユーザー定義コンテナのループにどのように役立つかを見ていきます。

また、関数型をイテレータとして使用することをサポートするために、標準ライブラリ型と関数を追加しました。イテレータの標準定義により、異なるコンテナ型でスムーズに動作する関数を記述できます。

(一部の)関数型にわたる範囲

改良されたfor/rangeステートメントは、任意の関数型をサポートしているわけではありません。Go 1.23の時点では、単一の引数を取る関数にわたる範囲をサポートしています。単一の引数は、0から2の引数を取り、boolを返す関数でなければなりません。慣例により、これをyield関数と呼びます。

func(yield func() bool)

func(yield func(V) bool)

func(yield func(K, V) bool)

Goでイテレータについて話すとき、これらの3つの型のいずれかを持つ関数を意味します。以下で説明するように、標準ライブラリには別の種類のイテレータがあります。プルイテレータです。標準イテレータとプルイテレータを区別する必要がある場合は、標準イテレータをプッシュイテレータと呼びます。これは、見ていくように、yield関数を呼び出すことによって一連の値をプッシュアウトするためです。

標準(プッシュ)イテレータ

イテレータを使いやすくするために、新しい標準ライブラリパッケージiterは2つの型を定義しています。`Seq`と`Seq2`です。これらはイテレータ関数型、つまりfor/rangeステートメントで使用できる型の名前です。`Seq`という名前は、イテレータが一連の値をループするため、sequenceの略です。

package iter

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

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

// for now, no Seq0

`Seq`と`Seq2`の違いは、`Seq2`がマップからのキーと値などのペアのシーケンスであることだけです。この投稿では、簡潔にするために`Seq`に焦点を当てますが、私たちが言うことのほとんどは`Seq2`にも当てはまります。

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

// All is an iterator over the elements of 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関数を引数として取ります。イテレータは、集合内のすべての値でyield関数を呼び出します。この場合、イテレータ、つまり`Set.All`によって返される関数は、前に見た`Set.Push`関数によく似ています。

これは、イテレータがどのように動作するかを示しています。一連の値について、シーケンス内の各値でyield関数を呼び出します。yield関数がfalseを返すと、値はこれ以上必要なくなり、イテレータは必要なクリーンアップを実行して返ることができます。yield関数がfalseを返さない場合、イテレータはシーケンス内のすべての値でyieldを呼び出した後に返すことができます。

それがどのように動作するのかはわかりましたが、最初にこれを見たときの最初の反応はおそらく「ここにはたくさんの関数が飛び交っている」でしょう。それは間違いではありません。2つのことに焦点を当てましょう。

1つ目は、この関数のコードの最初の行を過ぎると、イテレータの実際の実装は非常に単純であるということです。集合のすべての要素で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を使用して、返される関数の範囲を指定しています。この場合、イテレータ関数を返すのではなく、`Set.All`自体をイテレータ関数にすることもできました。ただし、場合によっては、イテレータを返す関数が引数を取る必要がある場合や、セットアップ作業を行う必要がある場合など、これは機能しません。慣例として、すべてのコンテナ型にイテレータを返す`All`メソッドを提供することをお勧めします。そのため、プログラマーは`All`を直接範囲指定する必要があるか、`All`を呼び出して範囲指定できる値を取得する必要があるかを覚えておく必要がありません。彼らは常に後者を行うことができます。

考えてみると、コンパイラはループを調整して、`s.All` によって返されるイテレータに渡す yield 関数を生成する必要があることがわかります。Go のコンパイラとランタイムには、これを効率的に行い、ループ内の `break` や `panic` などを正しく処理するための複雑な仕組みが備わっています。このブログ記事では、それらについては触れません。幸いなことに、この機能を実際に使用する場合、実装の詳細を知る必要はありません。

プル型イテレータ

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

答えは、異なる種類のイテレータ、つまりプル型イテレータを使用することです。プッシュ型イテレータとも呼ばれる標準のイテレータは、yield 関数を引数に取り、yield 関数を呼び出すことによってシーケンス内の各値をプッシュする関数です。

プル型イテレータは、その逆の動作をします。呼び出すたびに、シーケンス内の次の値を返すように記述された関数です。

2 種類のイテレータの違いを覚えるために、繰り返します。

  • プッシュ型イテレータは、シーケンス内の各値を yield 関数にプッシュします。プッシュ型イテレータは Go 標準ライブラリの標準イテレータであり、for/range ステートメントで直接サポートされています。
  • プル型イテレータは、その逆の動作をします。プル型イテレータを呼び出すたびに、シーケンスから別の値をプルして返します。プル型イテレータは for/range ステートメントで直接サポートされていません。ただし、プル型イテレータをループ処理する通常の for ステートメントを簡単に記述できます。実際、`Set.Pull` メソッドの使用について説明した際に、例を見ました。

プル型イテレータを自分で書くこともできますが、通常は必要ありません。新しい標準ライブラリ関数 `iter.Pull` は、標準のイテレータ、つまりプッシュ型イテレータである関数を受け取り、関数のペアを返します。1 つ目はプル型イテレータです。呼び出されるたびにシーケンス内の次の値を返す関数です。2 つ目は、プル型イテレータの使用が完了したときに呼び出す必要がある停止関数です。これは、前に見た `Set.Pull` メソッドに似ています。

`iter.Pull` によって返される最初の関数であるプル型イテレータは、値と、その値が有効かどうかを報告するブール値を返します。シーケンスの終わりでは、ブール値は false になります。

`iter.Pull` は、シーケンスを最後まで読み取らない場合に備えて、停止関数を返します。一般的に、`iter.Pull` の引数であるプッシュ型イテレータは、ゴルーチンを開始したり、反復処理が完了したときにクリーンアップする必要がある新しいデータ構造を構築したりする場合があります。プッシュ型イテレータは、yield 関数が false を返したときにクリーンアップを実行します。これは、それ以上の値が必要ないことを意味します。for/range ステートメントで使用する場合、for/range ステートメントは、ループが `break` ステートメントまたはその他の理由で早期に終了した場合、yield 関数が false を返すことを保証します。一方、プル型イテレータでは、yield 関数を強制的に false を返す方法がないため、停止関数が必要です。

言い換えると、停止関数を呼び出すと、プッシュ型イテレータによって呼び出されたときに yield 関数が false を返すようになります。

厳密に言えば、プル型イテレータがシーケンスの終わりに達したことを示すために false を返す場合、停止関数を呼び出す必要はありませんが、通常は常に呼び出す方が簡単です。

プル型イテレータを使用して 2 つのシーケンスを並列に処理する例を次に示します。この関数は、2 つの任意のシーケンスに同じ要素が同じ順序で含まれているかどうかを報告します。

// EqSeq reports whether two iterators contain the same
// elements in the same order.
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 つのプッシュ型イテレータ `s1` と `s2` をプル型イテレータに変換します。`defer` ステートメントを使用して、プル型イテレータの使用が完了したときに停止されるようにします。

次に、コードはループして、プル型イテレータを呼び出して値を取得します。最初のシーケンスが完了した場合、2 番目のシーケンスも完了していれば true を返し、そうでなければ false を返します。値が異なる場合は、false を返します。次に、ループして次の 2 つの値をプルします。

プッシュ型イテレータと同様に、Go ランタイムにはプル型イテレータを効率的にするための複雑な仕組みが備わっていますが、これは `iter.Pull` 関数を実際に使用するコードには影響しません。

イテレータの反復処理

これで、関数型とイテレータの範囲に関するすべてを理解できました。これらを楽しんで使用していただければ幸いです。

それでも、いくつか言及する価値のあることがあります。

アダプター

イテレータの標準定義の利点は、それらを使用する標準アダプター関数を記述できることです。

たとえば、値のシーケンスをフィルタリングして新しいシーケンスを返す関数を次に示します。この `Filter` 関数は、イテレータを引数に取り、新しいイテレータを返します。もう 1 つの引数は、`Filter` が返す新しいイテレータにどの値を含めるかを決定するフィルター関数です。

// Filter returns a sequence that contains the elements
// of s for which f returns 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
                }
            }
        }

コードは入力イテレータの範囲を反復処理し、フィルター関数をチェックし、出力イテレータに含める値で yield を呼び出します。

以下に `Filter` を使用した例を示します.

(現在、Go 標準ライブラリには `Filter` のバージョンはありませんが、将来のリリースで追加される可能性があります。)

二分木

プッシュ型イテレータがコンテナ型のループ処理にどれほど便利かを示す例として、この単純な二分木型を考えてみましょう。

// Tree is a binary tree.
type Tree[E any] struct {
    val         E
    left, right *Tree[E]
}

ツリーに値を挿入するコードは表示しませんが、当然、ツリー内のすべての値を範囲指定する方法が必要です。

イテレータコードは、bool を返す方が簡単に記述できることがわかりました。for/range でサポートされる関数型は何も返さないため、ここでの `All` メソッドは、イテレータ自体(ここでは `push` と呼ばれる)を呼び出し、bool の結果を無視する小さな関数リテラルを返します.

// All returns an iterator over the values in t.
func (t *Tree[E]) All() iter.Seq[E] {
    return func(yield func(E) bool) {
        t.push(yield)
    }
}

// push pushes all elements to the yield function.
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 パッケージの新しい関数を次に示します。`All` と `Values` は、スライスの要素に対するイテレータを返す関数です。`Collect` はイテレータから値を取得し、それらの値を保持するスライスを返します。その他の関数については、ドキュメントを参照してください。

maps パッケージの新しい関数を次に示します。`All`、`Keys`、および `Values` は、マップの内容に対するイテレータを返します。`Collect` はイテレータからキーと値を取得し、新しいマップを返します。

標準ライブラリのイテレータの例

前に説明した `Filter` 関数とこれらの新しい関数をどのように使用できるかの例を次に示します。この関数は、int から string へのマップを受け取り、引数 `n` よりも長い文字列のみを保持するスライスを返します。

// LongStrings returns a slice of just the values
// in m whose length is n or more.
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` がマップを入力として、スライスを出力として使用していることに注目してください。`Filter` 内のコードを変更する必要はありません。

ファイル内の行のループ処理

これまでの例ではコンテナを扱ってきましたが、イテレータは柔軟性があります。

バイトスライス内の行をループ処理するための、イテレータを使用しないこの単純なコードを考えてみましょう。これは簡単に記述でき、かなり効率的です。

    nl := []byte{'\n'}
    // Trim a trailing newline to avoid a final empty blank line.
    for _, line := range bytes.Split(bytes.TrimSuffix(data, nl), nl) {
        handleLine(line)
    }

ただし、`bytes.Split` は行を保持するためにバイトスライスのスライスを割り当てて返します。ガベージコレクタは、最終的にそのスライスを解放するために少し作業を行う必要があります。

バイトスライスの行に対するイテレータを返す関数を次に示します。通常のイテレータのシグネチャの後、関数は非常に単純です。何もなくなるまでデータから行を選択し続け、各行を yield 関数に渡します。

// Lines returns an iterator over lines in 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)
    }

これは以前のコードと同じくらい簡単に記述でき、行のスライスを割り当てる必要がないため、少し効率的です。

プッシュ型イテレータに関数を渡す

最後の例として、range ステートメントでプッシュ型イテレータを使用する必要がないことを示します。

先ほど、セットの各要素を出力するPrintAllElements関数を見ました。セットのすべての要素を出力する別の方法を紹介します。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関数が特別なものではないことを示すための単なる例です。任意の関数を使用できます。

go.modを更新する

最後に、すべてのGoモジュールは使用する言語バージョンを指定します。つまり、既存のモジュールで新しい言語機能を使用するには、そのバージョンを更新する必要がある場合があります。これはすべての新しい言語機能に当てはまります。関数型に対する範囲指定に固有のものではありません。関数型に対する範囲指定は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ビルドタグを使用して、特定のファイルで関数型に対する範囲指定を使用できるようにします。

次の記事:新しいuniqueパッケージ
前の記事:Go 1.23がリリースされました
ブログインデックス