Yoshi Yamaguchi

ジェネリックインターフェース

Generic interfaces by Axel Wagner

初めて聞くまでは気づきにくい考え方があります。インターフェースもそれ自体が型である以上、型パラメータを持てるということです。 この考え方は、ジェネリックな関数や型に対する制約を表現する場面で驚くほど強力であることがわかります。 この記事では、いくつかの典型的なシナリオを通して、型パラメータを持つインターフェースの使い方を実演します。

シンプルな木構造セット

動機となる例として、二分探索木のジェネリック版が必要になったとしましょう。 この木に格納する要素には順序が必要なので、型パラメータには使用する順序を決定する制約が必要です。 単純な選択肢は、Go 1.21で導入された cmp.Ordered 制約を使うことです。 この制約は型パラメータを順序付け可能な型(文字列と数値)に制限し、その型のメソッド内で組み込みの順序演算子を使えるようにします。

// The zero value of a Tree is a ready-to-use empty tree.
type Tree[E cmp.Ordered] struct {
    root *node[E]
}

func (t *Tree[E]) Insert(element E) {
    t.root = t.root.insert(element)
}

type node[E cmp.Ordered] struct {
    value E
    left  *node[E]
    right *node[E]
}

func (n *node[E]) insert(element E) *node[E] {
    if n == nil {
        return &node[E]{value: element}
    }
    switch {
    case element < n.value:
        n.left = n.left.insert(element)
    case element > n.value:
        n.right = n.right.insert(element)
    }
    return n
}

(プレイグラウンド)

しかし、このアプローチには、< が定義された基本的な型でしか動作しないという欠点があります。 time.Time のような構造体の型は挿入できません。

これは、ユーザーに比較関数を提供してもらうことで解決できます。

// A FuncTree must be created with NewFuncTree.
type FuncTree[E any] struct {
    root *funcNode[E]
    cmp  func(E, E) int
}

func NewFuncTree[E any](cmp func(E, E) int) *FuncTree[E] {
    return &FuncTree[E]{cmp: cmp}
}

func (t *FuncTree[E]) Insert(element E) {
    t.root = t.root.insert(t.cmp, element)
}

type funcNode[E any] struct {
    value E
    left  *funcNode[E]
    right *funcNode[E]
}

func (n *funcNode[E]) insert(cmp func(E, E) int, element E) *funcNode[E] {
    if n == nil {
        return &funcNode[E]{value: element}
    }
    sign := cmp(element, n.value)
    switch {
    case sign < 0:
        n.left = n.left.insert(cmp, element)
    case sign > 0:
        n.right = n.right.insert(cmp, element)
    }
    return n
}

(プレイグラウンド)

これでうまくいきますが、これにも欠点があります。 比較関数を明示的に初期化しなければならないため、コンテナ型のゼロ値をもう使えなくなります。 また、関数フィールドを使うことで、コンパイラが比較の呼び出しをインライン化しにくくなり、実行時に無視できないオーバーヘッドが生じることがあります。

要素の型のメソッドを使えば、メソッドは型に直接紐づいているため、こうした問題を解決できます。 メソッドは明示的に渡す必要がなく、コンパイラは呼び出し先を把握できるので、インライン化できる可能性があります。 しかし、要素の型が必要なメソッドを提供することをどうやって制約として表現できるでしょうか。

レシーバーを制約に使う

最初に試してみたくなるアプローチは、Compare メソッドを持つ普通のインターフェースを定義することです。

type Comparer interface {
    Compare(Comparer) int
}

しかし、これがうまくいかないことにすぐ気づきます。 このインターフェースを実装するには、メソッドの引数自体が Comparer でなければなりません。 これは、このメソッドの実装が引数を自分自身の型に型アサーションしなければならないというだけでなく、すべての型が(メソッドのシグネチャが一致するように)明示的に Comparer 型を持つ私たちのパッケージを名前で参照しなければならないことも意味します。 これはあまり直交的ではありません。

より良いアプローチは、Comparer インターフェース自体をジェネリックにすることです。

type Comparer[T any] interface {
    Compare(T) int
}

この Comparer は、インスタンス化に使われる型それぞれに対応する、インターフェースの一族全体を表すようになりました。 Comparer[T] を実装する型は、「自分自身を T と比較できる」と宣言していることになります。 たとえば time.Time は、一致する Compare メソッドを持つため、自然に Comparer[time.Time] を実装しています。

// Implements Comparer[Time]
func (t Time) Compare(u Time) int

これはより良くなりましたが、まだ十分ではありません。 私たちが本当に欲しいのは、型パラメータが自分自身と比較できることを表す制約、つまり自己参照的な制約です。 ここでの微妙な洞察は、自己参照的な側面がインターフェースの定義自体に含まれている必要はないということです。 具体的には、Comparer 型における T の制約は単なる any です。 その代わり、自己参照性は MethodTree の型パラメータの制約として Comparer をどう使うかから生じます。

// The zero value of a MethodTree is a ready-to-use empty tree.
type MethodTree[E Comparer[E]] struct {
    root *methodNode[E]
}

func (t *MethodTree[E]) Insert(element E) {
    t.root = t.root.insert(element)
}

type methodNode[E Comparer[E]] struct {
    value E
    left  *methodNode[E]
    right *methodNode[E]
}

func (n *methodNode[E]) insert(element E) *methodNode[E] {
    if n == nil {
        return &methodNode[E]{value: element}
    }
    sign := element.Compare(n.value)
    switch {
    case sign < 0:
        n.left = n.left.insert(element)
    case sign > 0:
        n.right = n.right.insert(element)
    }
    return n
}

(プレイグラウンド)

time.Time は Comparer[time.Time] を実装しているので、このコンテナに対する有効な型引数になり、しかもゼロ値を空のコンテナとして使い続けられます。

var t MethodTree[time.Time]
t.Insert(time.Now())

完全な柔軟性を求めるなら、ライブラリは3つのAPIバージョンすべてを提供できます。 繰り返しを最小限にしたいのであれば、すべてのバージョンで共有の実装を使うこともできます。 最も汎用的な、関数バージョンをその共有実装として使えるでしょう。

type node[E any] struct {
    value E
    left  *node[E]
    right *node[E]
}

func (n *node[E]) insert(cmp func(E, E) int, element E) *node[E] {
    if n == nil {
        return &node[E]{value: element}
    }
    sign := cmp(element, n.value)
    switch {
    case sign < 0:
        n.left = n.left.insert(cmp, element)
    case sign > 0:
        n.right = n.right.insert(cmp, element)
    }
    return n
}

// Insert は、E が cmp.Ordered を実装していれば、element を木に挿入する。
func (t *Tree[E]) Insert(element E) {
    t.root = t.root.insert(cmp.Compare[E], element)
}

// Insert は、与えられた比較関数を使って element を木に挿入する。
func (t *FuncTree[E]) Insert(element E) {
    t.root = t.root.insert(t.cmp, element)
}

// Insert は、E が Comparer[E] を実装していれば、element を木に挿入する。
func (t *MethodTree[E]) Insert(element E) {
    t.root = t.root.insert(E.Compare, element)
}

(プレイグラウンド)

ここで重要な観察点は、共有の実装(関数ベースのバージョン)には何の制約もかかっていないということです。 共通のコアとして機能するためには、最大限柔軟なままである必要があります。 また、比較関数を構造体のフィールドには格納していません。 代わりに引数として渡しています。関数の引数の方が構造体のフィールドよりもコンパイラにとって解析しやすいからです。

もちろん、ある程度の定型的なコードは依然として必要です。 エクスポートされたすべての実装は、わずかに異なる呼び出しパターンでAPI全体を複製しなければなりません。 しかし、この部分は書くのも読むのも簡単です。

メソッドと型集合を組み合わせる

この新しい木構造を使えば、要素の探索を対数時間で行える順序付きセットを実装できます。 では、この探索を定数時間で行えるようにする必要があるとしましょう。 これは、木と並行して通常のGoのマップを保持することで実現できるかもしれません。

type OrderedSet[E Comparer[E]] struct {
    tree     MethodTree[E] // 順序通りの効率的な反復のため
    elements map[E]bool    // (ほぼ)定数時間での探索のため
}

func (s *OrderedSet[E]) Has(e E) bool {
    return s.elements[e]
}

func (s *OrderedSet[E]) Insert(e E) {
    if s.elements == nil {
        s.elements = make(map[E]bool)
    }
    if s.elements[e] {
        return
    }
    s.elements[e] = true
    s.tree.Insert(e)
}

func (s *OrderedSet[E]) All() iter.Seq[E] {
    return func(yield func(E) bool) {
        s.tree.root.all(yield)
    }
}

func (n *node[E]) all(yield func(E) bool) bool {
    return n == nil || (n.left.all(yield) && yield(n.value) && n.right.all(yield))
}

(プレイグラウンド)

しかし、このコードをコンパイルするとエラーが発生します。

invalid map key type E (missing comparable constraint)

このエラーメッセージは、型パラメータをマップのキーとして使うには、さらに制約を加える必要があることを教えてくれます。 comparable 制約は、等価演算子 == と != が定義されているすべての型によって満たされる、特別な事前宣言された制約です。 Goでは、これは組み込みの map 型のキーとして使える型の集合でもあります。

この制約を型パラメータに追加する方法には3つの選択肢があり、それぞれにトレードオフがあります。

  1. 元の Comparer 定義に comparable を埋め込むことができます(プレイグラウンド)。

    type Comparer[E any] interface {
    comparable
    Compare(E) int
}

    この方法には、Tree 型も comparable な型でしか使えなくなってしまうという欠点があります。 一般に、ジェネリックな型を不必要に制限したくはありません。

  2. 新しい制約の定義を追加することもできます(プレイグラウンド)。

    type Comparer[E any] interface {
    Compare(E) int
}

type ComparableComparer[E any] interface {
    comparable
    Comparer[E]
}

    これはすっきりしていますが、APIに新しい識別子(ComparableComparer)を導入することになり、命名は難しいものです。

  3. より制約の強い型の中にインラインで制約を追加することもできます(プレイグラウンド)。

    type OrderedSet[E interface {
    comparable
    Comparer[E]
}] struct {
    tree     Tree[E]
    elements map[E]struct{}
}

    これは、特に頻繁に必要になる場合には、少し読みにくくなることがあります。 また、他の場所でその制約を再利用しにくくもなります。

このうちどれを使うかはスタイルの選択であり、最終的には個人の好みによります。

ジェネリックインターフェースを制約しすぎない

ここで、ジェネリックインターフェースに対する制約について議論しておく価値があります。 ジェネリックなコンテナ型に対するインターフェースを定義したくなることがあるかもしれません。 たとえば、セットのデータ構造を必要とするアルゴリズムがあるとしましょう。 セットの実装にはトレードオフの異なる様々な種類があります。 必要なセット操作に対してインターフェースを定義しておけば、パッケージに柔軟性を持たせられ、特定のアプリケーションにとってどのトレードオフが適切かの判断をユーザーに委ねられます。

type Set[E any] interface {
    Insert(E)
    Delete(E)
    Has(E) bool
    All() iter.Seq[E]
}

ここで自然に浮かぶ疑問は、このインターフェースにどんな制約を課すべきかということです。 可能であれば、ジェネリックインターフェースの型パラメータには any を制約として使い、任意の型を許容するべきです。

ここまでの議論から、その理由は明らかでしょう。 具体的な実装が異なれば、必要な制約も異なる可能性があります。 これまで見てきたすべての Tree 型と OrderedSet 型は、それぞれ異なる制約を持っているにもかかわらず、いずれもそれぞれの要素型に対して Set を実装できます。

インターフェースを定義する意義は、実装をユーザーに委ねることにあります。 ユーザーが自分の実装にどのような制約を課したいかは予測できないので、(any より強い)制約はインターフェースにではなく、具体的な実装の側に持たせるようにしましょう。

ポインタレシーバー

この Set インターフェースを例の中で使ってみましょう。 シーケンス内の重複した要素を取り除く関数を考えます。

// Unique は入力シーケンスから重複した要素を取り除き、各要素の最初の出現だけを返す。
func Unique[E comparable](input iter.Seq[E]) iter.Seq[E] {
    return func(yield func(E) bool) {
        seen := make(map[E]bool)
        for v := range input {
            if seen[v] {
                continue
            }
            if !yield(v) {
                return
            }
            seen[v] = true
        }
    }
}

(プレイグラウンド)

これは map[E]bool を E の単純なセットとして使っています。 そのため、comparable であり、組み込みの等価演算子が定義されている型に対してしか動作しません。 これを任意の型に一般化したいのであれば、これをジェネリックなセットに置き換える必要があります。

// Unique は入力シーケンスから重複した要素を取り除き、各要素の最初の出現だけを返す。
func Unique[E any](input iter.Seq[E]) iter.Seq[E] {
    return func(yield func(E) bool) {
        var seen Set[E]
        for v := range input {
            if seen.Has(v) {
                continue
            }
            if !yield(v) {
                return
            }
            seen.Insert(v)
        }
    }
}

(プレイグラウンド)

しかし、これはうまく動きません。 Set[E] はインターフェース型であり、seen 変数は nil に初期化されてしまいます。 Set[E] インターフェースの具体的な実装を使う必要があります。 しかし、この記事でここまで見てきたように、任意の要素型に対して機能するセットの汎用的な実装は存在しません。

そこで、追加の型パラメータとして、使用できる具体的な実装をユーザーに提供してもらう必要があります。

// Unique は入力シーケンスから重複した要素を取り除き、各要素の最初の出現だけを返す。
func Unique[E any, S Set[E]](input iter.Seq[E]) iter.Seq[E] {
    return func(yield func(E) bool) {
        var seen S
        for v := range input {
            if seen.Has(v) {
                continue
            }
            if !yield(v) {
                return
            }
            seen.Insert(v)
        }
    }
}

(プレイグラウンド)

しかし、これを私たちのセット実装でインスタンス化すると、別の問題にぶつかります。

// OrderedSet[E] does not satisfy Set[E] (method All has pointer receiver)
Unique[E, OrderedSet[E]](slices.Values(s))
// panic: invalid memory address or nil pointer dereference
Unique[E, *OrderedSet[E]](slices.Values(s))

最初の問題はエラーメッセージから明らかです。 私たちの型制約は、S の型引数が Set[E] インターフェースを実装している必要があると言っています。 そして OrderedSet のメソッドはポインタレシーバーを使っているため、型引数もポインタ型でなければなりません。

そうしようとすると、2番目の問題にぶつかります。 これは、実装の中で次のように変数を宣言していることに起因します。

var seen S

S が *OrderedSet[E] である場合、この変数は以前と同様に nil で初期化されます。 seen.Insert を呼び出すとパニックになります。

ポインタ型しか持っていなければ、値型の有効な変数を得られません。 そして値型しか持っていなければ、それに対してポインタメソッドを呼び出せません。 結果として、値型とポインタ型の両方が必要になります。 そこで、追加の型パラメータ PS と、新しい制約 PtrToSet を導入しなければなりません。

// PtrToSet は、Set[E] インターフェースを実装するポインタ型によって実装される。
type PtrToSet[S, E any] interface {
    *S
    Set[E]
}

// Unique は入力シーケンスから重複した要素を取り除き、各要素の最初の出現だけを返す。
func Unique[E, S any, PS PtrToSet[S, E]](input iter.Seq[E]) iter.Seq[E] {
    return func(yield func(E) bool) {
        // メソッドを持つよう制約されているのは PS だけなので、PS に変換する。
        // PS の型集合には *S しか含まれないため、この変換は許可されている。
        seen := PS(new(S))
        for v := range input {
            if seen.Has(v) {
                continue
            }
            if !yield(v) {
                return
            }
            seen.Insert(v)
        }
    }
}

(プレイグラウンド)

ここでのトリックは、PtrToSet インターフェース上の追加の型パラメータを介して、関数シグネチャ内の2つの型パラメータを結びつけていることです。 S 自体は無制約ですが、PS は型 *S を持たなければならず、また必要なメソッドを持たなければなりません。 つまり実質的に、S にいくつかのメソッドを持つよう制約しつつ、それらのメソッドがポインタレシーバーを使う必要がある、という形になっているのです。

この種の制約を持つ関数の定義には追加の型パラメータが必要になりますが、重要なのは、それを使うコード側は複雑にならないということです。 この追加の型パラメータが型パラメータリストの末尾にある限り、型推論できます。

// 3番目の型引数は *OrderedSet[int] であると推論される
Unique[int, OrderedSet[int]](slices.Values(s))

これは一般的なパターンであり、覚えておく価値があります。他の人のコードでこれに出会ったときのため、あるいは自分のコードでこれを使いたいときのためにです。

func SomeFunction[T any, PT interface{ *T; SomeMethods }]()

2つの型パラメータがあり、一方がもう一方へのポインタであるよう制約されている場合、その制約によって、関連するメソッドがポインタレシーバーを使うことが保証されます。

ポインタレシーバーへの制約は必要か

この時点で、かなり圧倒されていることでしょう。 これはかなり複雑ですし、この関数シグネチャで何が起きているのかをすべてのGoプログラマーが理解できると期待するのは無理があるように思えます。 また、APIにさらに多くの名前を導入しなければなりませんでした。 そもそもGoにジェネリクスを追加することに人々が慎重だったとき、これはまさに懸念されていたことの一つです。

そのため、こうした問題に絡め取られてしまったと感じたら、一歩下がって考えてみる価値があります。 問題を別の角度から捉え直すことで、この複雑さを避けられることがよくあります。 この例では、iter.Seq[E] を受け取り、重複のない要素からなる iter.Seq[E] を返す関数を作りました。 しかし重複を排除するには、重複のない要素をセットに集める必要がありました。 そしてこれは結果全体分の領域を確保する必要があるということなので、結果をストリームとして表現することの恩恵を実際には受けていません。

この問題を捉え直せば、Set[E] を通常のインターフェース値として使うことで、追加の型パラメータをまるごと避けられます。

// InsertAll は seq に含まれるすべての重複しない要素を set に追加する。
func InsertAll[E any](set Set[E], seq iter.Seq[E]) {
    for v := range seq {
        set.Insert(v)
    }
}

(プレイグラウンド)

Set を単純なインターフェース型として使うことで、呼び出し側が自分の具体的な実装の有効な値を渡さなければならないことが明確になります。 これは非常によくあるパターンです。 そして iter.Seq[E] が必要であれば、set に対して単に All() を呼び出すことで得られます。

これは呼び出し側にとって多少複雑になりますが、ポインタレシーバーへの制約と比べてもう一つの利点があります。 私たちが最初に map[E]bool を単純なセット型として使っていたことを思い出してください。 それを基にして Set[E] インターフェースを実装するのは簡単です。

type HashSet[E comparable] map[E]bool

func (s HashSet[E]) Insert(v E)       { s[v] = true }
func (s HashSet[E]) Delete(v E)       { delete(s, v) }
func (s HashSet[E]) Has(v E) bool     { return s[v] }
func (s HashSet[E]) All() iter.Seq[E] { return maps.Keys(s) }

(プレイグラウンド)

この実装はポインタレシーバーを使っていません。 そのためこれは完全に有効な実装ではあるものの、ポインタレシーバーへの複雑な制約とは一緒に使えません。 しかし、私たちの InsertAll バージョンとは問題なく組み合わせられます。 多くの制約と同様に、メソッドがポインタレシーバーを使うことを強制するのは、実際には多くの実用的なユースケースにとって過度に制限的かもしれません。

結論

この記事が、インターフェースに型パラメータを持たせることで可能になるパターンやトレードオフのいくつかを示せていれば幸いです。 これは強力な道具ですが、代償も伴います。主な要点は次のとおりです。

  1. ジェネリックインターフェースを自己参照的に使うことで、レシーバーに対する制約を表現する。
  2. 異なる型パラメータ間の制約された関係を作るために使う。
  3. 異なる種類の制約を持つ異なる実装を抽象化するために使う。
  4. ポインタレシーバーへの制約が必要な状況に陥ったときは、その余分な複雑さを避けるようにコードをリファクタリングできないか検討する。「ポインタレシーバーへの制約は必要か」を参照。

いつものことですが、過剰に作り込まないようにしましょう。柔軟性は劣っていても、よりシンプルで読みやすい解決策の方が、結局は賢明な選択かもしれません。

By Axel Wagner