ジェネリック

ジェネリック、またはより学術的な名称であるパラメータ化多態（Parameterized Polymorphism）は、型のパラメータ化を通じてコードの再利用と柔軟性を実現します。多くのプログラミング言語において、パラメータ化多態は重要な概念であり、関数やデータ構造が異なる型のデータを処理できるようにし、型ごとに個別のコードを記述する必要がありません。初期の Go にはジェネリックという概念はありませんでしたが、誕生以来、コミュニティから最も多かった要望はジェネリックの追加でした。ついに Go 言語は 2022 年の 1.18 バージョンでジェネリックのサポートを追加しました。

設計

Go 言語がジェネリックを設計する際、以下の方案を検討しました。

• stenciling：単相化。C++ や Rust のような典型的な例で、使用される型ごとにテンプレートコードを生成します。この方法の性能は最も優れており、実行時オーバーヘッドが全くなく、直接呼び出したのと同じ性能です。欠点はコンパイル速度を大幅に低下させること（Go 自体と比較して）、また各型ごとにコードを生成するため、コンパイル済みバイナリファイルのサイズが膨張することです。
• dictionaries：これは 1 つのコードセットのみを生成し、コンパイル時に型辞書を生成して読み取り専用データセグメントに格納します。これは使用されるすべての型情報を格納し、関数を呼び出す際に辞書を参照して型情報を取得します。この方法はコンパイル速度を低下させず、サイズの膨張も引き起こしませんが、大きな実行時オーバーヘッドを引き起こし、ジェネリックの性能が非常に悪くなります。

上記の 2 つの方法は両極端を表しており、Go 言語が最終的に選択した実装方案は Gcshape stenciling です。これは折衷案で、同じメモリ形状（形状はメモリ割り当てプログラムによって決定されます）の型には単相化を使用し、同じコードセットを生成します。例えば type Int int と int は実際には同じ型であるため、同じコードを共有します。しかしポインタの場合、すべてのポインタ型は同じメモリ形状ですが（例えば *int、*Person はすべて同じメモリ形状）、同じコードを共有することはできません。参照解除時に操作対象の型のメモリレイアウトが完全に異なるためです。そのため、Go は実行時に型情報を取得するために辞書も使用します。したがって、Go のジェネリックにも実行時オーバーヘッドが存在します。

導入

まず簡単な例を見てみましょう。

func Sum(a, b int) int {
   return a + b
}

これは非常にシンプルな機能の関数で、2 つの int 型の整数を加算して結果を返すものです。2 つの float64 型の浮動小数点数を加算したい場合、型が一致しないため明らかにできません。1 つの解決策は新しい関数を定義することです。以下の通りです。

func SumFloat64(a, b float64) float64 {
  return a + b
}

ここで問題です。数学ツールパッケージを開発して、すべての数値型の 2 つの数の和を計算する場合、型ごとに 1 つずつ関数を書く必要があるでしょうか。明らかにそれは不可能です。あるいは any 型とリフレクションを使用して判断することもできます。以下の通りです。

func SumAny(a, b any) (any, error) {
  tA, tB := reflect.ValueOf(a), reflect.ValueOf(b)
  if tA.Kind() != tB.Kind() {
    return nil, errors.New("disMatch type")
  }

  switch tA.Kind() {
  case reflect.Int:
  case reflect.Int32:
    ...
  }
}

しかしこのように記述すると煩雑で、性能も低くなります。しかし Sum 関数のロジックはすべて同一で、単に 2 つの数を加算するだけです。ここでジェネリックが必要になります。なぜジェネリックが必要なのかというと、ジェネリックは実行ロジックが型に無関係な問題を解決するためです。このような問題は、与えられた型が何であるかを気にせず、対応する操作を完了するだけで十分です。

構文

ジェネリックの記述方法は以下の通りです。

func Sum[T int | float64](a, b T) T {
   return a + b
}

型仮パラメータ：T は型仮パラメータです。具体的な型は何が渡されるかによって異なります。

型制約：int | float64 は型制約を構成します。この型制約はどの型が許可されるかを規定し、型仮パラメータの型範囲を制約します。

型実パラメータ：Sum[int](1,2)、int 型を手動で指定します。int が型実パラメータです。

1 つ目の使い方は、どの型を使用するかを明示的に指定することです。以下の通りです。

Sum[int](2012, 2022)

2 つ目の使い方は、型を指定せず、コンパイラに推論させることです。以下の通りです。

Sum(3.1415926, 1.114514)

これはジェネリックスライスで、型制約は int | int32 | int64 です。

type GenericSlice[T int | int32 | int64] []T

使用する際は型実パラメータを省略できません。

GenericSlice[int]{1, 2, 3}

これはジェネリックハッシュテーブルで、キーの型は比較可能である必要があるため、comparable インターフェースを使用します。値の型制約は V int | string | byte です。

type GenericMap[K comparable, V int | string | byte] map[K]V

使用

gmap1 := GenericMap[int, string]{1: "hello world"}
gmap2 := make(GenericMap[string, byte], 0)

これはジェネリック構造体で、型制約は T int | string です。

type GenericStruct[T int | string] struct {
   Name string
   Id   T
}

使用

GenericStruct[int]{
   Name: "jack",
   Id:   1024,
}
GenericStruct[string]{
   Name: "Mike",
   Id:   "1024",
}

これはジェネリックスライスパラメータの例です。

type Company[T int | string, S []T] struct {
   Name  string
   Id    T
   Stuff S
}

// または以下のようにも記述できます
type Company[T int | string, S []int | []string] struct {
  Name  string
  Id    T
  Stuff S
}

使用

Company[int, []int]{
   Name:  "lili",
   Id:    1,
   Stuff: []int{1},
}

TIP

ジェネリック構造体では、以下の記述方法を推奨します。

type Company[T int | string, S int | string] struct {
  Name  string
  Id    T
  Stuff []S
}

SayAble はジェネリックインターフェースで、Person がこのインターフェースを実装しています。

type SayAble[T int | string] interface {
   Say() T
}

type Person[T int | string] struct {
   msg T
}

func (p Person[T]) Say() T {
   return p.msg
}

func main() {
  var s SayAble[string]
  s = Person[string]{"hello world"}
  fmt.Println(s.Say())
}

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

ジェネリックインターフェースは、より優れた抽象化制約能力を提供できます。以下に例を示します。

func PrintObj[T fmt.Stringer](s T) {
	fmt.Println(s.String())
}

type Person struct {
	Name string
}

func (p Person) String() string {
	return fmt.Sprintf("Person: %s", p.Name)
}

func main() {
	PrintObj(Person{Name: "Alice"})
}

また、非ジェネリックインターフェースをジェネリックの型仮パラメータとして使用することもできます。

func Write[W io.Writer](w W, bs []byte) (int, error) {
	return w.Write(bs)
}

ジェネリックアサーション

ジェネリックを使用して any 型の型アサーションを行うことができます。例えば、以下の関数はすべての型をアサーションできます。

func Assert[T any](v any) (bool, T) {
	var av T
	if v == nil {
		return false, av
	}
	av, ok := v.(T)
	return ok, av
}

型セット

1.18 以降、インターフェースの定義は型セット (type set) に変更され、型セットを含むインターフェースは General interfaces、つまり汎用インターフェースと呼ばれます。

An interface type defines a type set

型セットはジェネリック内の型制約にのみ使用でき、型宣言、型変換、型アサーションには使用できません。型セットは集合であるため、空集合、和集合、積集合があります。次にこれら 3 つの状況について解説します。

和集合

インターフェース型 SignedInt は型セットで、符号付き整数型の和集合は SignedInt です。逆に SignedInt はそれらのスーパーセットです。

type SignedInt interface {
   int8 | int16 | int | int32 | int64
}

基本データ型も同様で、他の汎用インターフェースも同様です。

type SignedInt interface {
  int8 | int16 | int | int32 | int64
}

type UnSignedInt interface {
  uint8 | uint16 | uint32 | uint64
}

type Integer interface {
  SignedInt | UnSignedInt
}

積集合

空でないインターフェースの型セットは、そのすべての要素の型セットの積集合です。言い換えると、あるインターフェースが複数の空でない型セットを含む場合、そのインターフェースはこれらの型セットの積集合となります。例を以下に示します。

type SignedInt interface {
   int8 | int16 | int | int32 | int64
}

type Integer interface {
   int8 | int16 | int | int32 | int64 | uint8 | uint16 | uint | uint32 | uint64
}

type Number interface {
  SignedInt
  Integer
}

例の積集合は明らかに SignedInt です。

func Do[T Number](n T) T {
   return n
}

Do[int](2)
DO[uint](2) // コンパイルできません

空集合

空集合とは積集合がないことです。例を以下に示します。以下の例の Integer は型空集合です。

type SignedInt interface {
  int8 | int16 | int | int32 | int64
}

type UnsignedInt interface {
  uint8 | uint16 | uint | uint32 | uint64
}

type Integer interface {
  SignedInt
  UnsignedInt
}

符号なし整数と符号付き整数には明らかに積集合がないため、積集合は空集合になります。以下の例では、どの型を渡してもコンパイルできません。

Do[Integer](1)
Do[Integer](-100)

空インターフェース

空インターフェースと空集合は異なります。空インターフェースはすべての型セットの集合で、つまりすべての型を含みます。

func Do[T interface{}](n T) T {
   return n
}

func main() {
   Do[struct{}](struct{}{})
   Do[any]("abc")
}

ただし、一般的には any をジェネリック仮パラメータとして使用します。interface{} は見栄えが悪いためです。

基底型

type キーワードを使用して新しい型を宣言した場合、その基底型が型セットに含まれていても、渡す際にコンパイルできません。

type Int interface {
   int8 | int16 | int | int32 | int64 | uint8 | uint16 | uint | uint32 | uint64
}

type TinyInt int8

func Do[T Int](n T) T {
   return n
}

func main() {
   Do[TinyInt](1) // 基底型が Int 型セットの範囲内に属していても、コンパイルできません
}

2 つの解決策があります。1 つ目は型セットにその型を和集合することですが、これは無意味です。TinyInt と int8 の基底型は同一であるため、2 つ目の解決策があります。

type Int interface {
   int8 | int16 | int | int32 | int64 | uint8 | uint16 | uint | uint32 | uint64 | TinyInt
}

~ 記号を使用して基底型を表します。ある型の基底型がその型セットに属する場合、その型はその型セットに属します。以下の通りです。

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64
}

修正後はコンパイルできます。

func main() {
   Do[TinyInt](1) // TinyInt が型セット Int 内に属しているため、コンパイルできます
}

注意点

ジェネリックは型の基底型として使用できません

以下の記述は誤りです。ジェネリック仮パラメータ T は基底型として使用できません。

type GenericType[T int | int32 | int64] T

以下の記述は許可されていますが、無意味で数値オーバーフローの問題を引き起こす可能性があるため、推奨されません。

type GenericType[T int | int32 | int64] int

ジェネリック型は型アサーションを使用できません

ジェネリック型に対して型アサーションを使用すると、コンパイルできません。ジェネリックが解決しようとする問題は型に無関係なものです。もし問題が異なる型に基づいて異なるロジックを実行する必要がある場合、ジェネリックを使用すべきではなく、interface{} または any を使用するべきです。

func Sum[T int | float64](a, b T) T {
   ints,ok := a.(int) // 許可されていません
   switch a.(type) { // 許可されていません
   case int:
   case bool:
      ...
   }
   return a + b
}

匿名構造体はジェネリックをサポートしていません

匿名構造体はジェネリックをサポートしていません。以下のコードはコンパイルできません。

testStruct := struct[T int | string] {
   Name string
   Id T
}[int]{
   Name: "jack",
   Id: 1
}

匿名関数はカスタムジェネリックをサポートしていません

以下の 2 つの記述はすべてコンパイルできません。

var sum[T int | string] func (a, b T) T
sum := func[T int | string](a,b T) T{
    ...
}

ただし、既存のジェネリック型を使用することはできます。例えばクロージャ内などです。

func Sum[T int | float64](a, b T) T {
  sub := func(c, d T) T {
    return c - d
  }
  return sub(a,b) + a + b
}

ジェネリックメソッドはサポートされていません

メソッドはジェネリック仮パラメータを持つことはできませんが、receiver はジェネリック仮パラメータを持つことができます。以下のコードはコンパイルできません。

type GenericStruct[T int | string] struct {
   Name string
   Id   T
}

func (g GenericStruct[T]) name[S int | float64](a S) S {
   return a
}

型セットは型実パラメータとして使用できません

型セットを含むインターフェースは、型実パラメータとして使用できません。

type SignedInt interface {
  int8 | int16 | int | int32 | int64
}

func Do[T SignedInt](n T) T {
   return n
}

func main() {
   Do[SignedInt](1) // コンパイルできません
}

型セットの積集合の問題

非インターフェース型の場合、型和集合に積集合を含めることはできません。例えば以下の例の TinyInt と ~int8 には積集合があります。

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64 | TinyInt // コンパイルできません
}

type TinyInt int8

ただし、インターフェース型の場合、積集合を含めることが許可されています。以下の例の通りです。

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64 | TinyInt // コンパイルできます
}

type TinyInt interface {
  int8
}

型セットは直接または間接的に自身を和集合できません

以下の例では、Floats が直接自身を和集合し、Double が Floats を和集合しているため、間接的に自身を和集合しています。

type Floats interface {  // コードはコンパイルできません
   Floats | Double
}

type Double interface {
   Floats
}

comparable インターフェースは型セットに和集合できません

同様に、型制約に和集合することもできません。したがって、基本的に単独で使用されます。

func Do[T comparable | Integer](n T) T { // コンパイルできません
   return n
}

type Number interface { // コンパイルできません
  Integer | comparable
}

type Comparable interface { // コンパイルできますが無意味です
  comparable
}

メソッドセットは型セットに和集合できません

メソッドを含むインターフェースは、型集合に和集合できません。

type I interface {
    int | fmt.Stringer // cannot use fmt.Stringer in union (fmt.Stringer contains methods)
}

ただし、積集合することはできますが、这样做は無意味です。

type I interface {
    int
    fmt.Stringer
}

使用

データ構造はジェネリックの最も一般的な使用例です。以下に 2 つのデータ構造を通じてジェネリックの使用方法を示します。

キュー

以下にジェネリックを使用して簡単なキューを実装します。まずキュー型を宣言します。キュー内の要素の型は任意であるため、型制約は any です。

type Queue[T any] []T

合計 4 つのメソッド Pop、Peek、Push、Size があります。コードは以下の通りです。

type Queue[T any] []T

func (q *Queue[T]) Push(e T) {
  *q = append(*q, e)
}

func (q *Queue[T]) Pop(e T) (_ T) {
  if q.Size() > 0 {
    res := q.Peek()
    *q = (*q)[1:]
    return res
  }
  return
}

func (q *Queue[T]) Peek() (_ T) {
  if q.Size() > 0 {
    return (*q)[0]
  }
  return
}

func (q *Queue[T]) Size() int {
  return len(*q)
}

Pop と Peek メソッドでは、戻り値が _ T であることがわかります。これは名前付き戻り値の使用方法ですが、アンダースコア _ を使用して匿名であることを表しています。これは余計なことではなく、ジェネリックのゼロ値を表すためです。ジェネリックを使用しているため、キューが空の場合、ゼロ値を返す必要があります。しかし型が不明であるため、具体的な型を返すことはできません。上記の方法を使用してジェネリックゼロ値を返すことができます。また、ジェネリック変数を宣言してゼロ値の問題を解決することもできます。ジェネリック変数の場合、デフォルトの値はその型のゼロ値です。以下の通りです。

func (q *Queue[T]) Pop(e T) T {
    var res T
  if q.Size() > 0 {
    res = q.Peek()
    *q = (*q)[1:]
    return res
  }
  return res
}

ヒープ

上記のキューの例では、要素に何の要件もないため、型制約は any です。しかしヒープは異なります。ヒープは特殊なデータ構造で、O(1) の時間で最大値または最小値を判断できます。したがって、要素に要件があります。つまり、ソート可能な型である必要があります。しかし、組み込みのソート可能な型は数値と文字列のみです。したがって、ヒープの初期化時にカスタムコンパレータを渡す必要があります。コンパレータは呼び出し元によって提供され、ジェネリックを使用する必要があります。以下の通りです。

type Comparator[T any] func(a, b T) int

以下は簡単な二項ヒープの実装です。まずジェネリック構造体を宣言します。引き続き any を使用して制約します。これにより任意の型を格納できます。

type Comparator[T any] func(a, b T) int

type BinaryHeap[T any] struct {
  s []T
  c Comparator[T]
}

いくつかのメソッドの実装

func (heap *BinaryHeap[T]) Peek() (_ T) {
  if heap.Size() > 0 {
    return heap.s[0]
  }
  return
}

func (heap *BinaryHeap[T]) Pop() (_ T) {
  size := heap.Size()
  if size > 0 {
    res := heap.s[0]
    heap.s[0], heap.s[size-1] = heap.s[size-1], heap.s[0]
    heap.s = heap.s[:size-1]
    heap.down(0)
    return res
  }
  return
}

func (heap *BinaryHeap[T]) Push(e T) {
  heap.s = append(heap.s, e)
  heap.up(heap.Size() - 1)
}

func (heap *BinaryHeap[T]) up(i int) {
  if heap.Size() == 0 || i < 0 || i >= heap.Size() {
    return
  }
  for parentIndex := i>>1 - 1; parentIndex >= 0; parentIndex = i>>1 - 1 {
    // greater than or equal to
    if heap.compare(heap.s[i], heap.s[parentIndex]) >= 0 {
      break
    }
    heap.s[i], heap.s[parentIndex] = heap.s[parentIndex], heap.s[i]
    i = parentIndex
  }
}

func (heap *BinaryHeap[T]) down(i int) {
  if heap.Size() == 0 || i < 0 || i >= heap.Size() {
    return
  }
  size := heap.Size()
  for lsonIndex := i<<1 + 1; lsonIndex < size; lsonIndex = i<<1 + 1 {
    rsonIndex := lsonIndex + 1

    if rsonIndex < size && heap.compare(heap.s[rsonIndex], heap.s[lsonIndex]) < 0 {
      lsonIndex = rsonIndex
    }

    // less than or equal to
    if heap.compare(heap.s[i], heap.s[lsonIndex]) <= 0 {
      break
    }
    heap.s[i], heap.s[lsonIndex] = heap.s[lsonIndex], heap.s[i]
    i = lsonIndex
  }
}

func (heap *BinaryHeap[T]) Size() int {
  return len(heap.s)
}

func NewHeap[T any](n int, c Comparator[T]) BinaryHeap[T] {
	var heap BinaryHeap[T]
	heap.s = make([]T, 0, n)
	heap.Comparator = c
	return heap
}

使用は以下の通りです。

type Person struct {
  Age  int
  Name string
}

func main() {
  heap := NewHeap[Person](10, func(a, b Person) int {
    return cmp.Compare(a.Age, b.Age)
  })
  heap.Push(Person{Age: 10, Name: "John"})
  heap.Push(Person{Age: 18, Name: "mike"})
  heap.Push(Person{Age: 9, Name: "lili"})
  heap.Push(Person{Age: 32, Name: "miki"})
  fmt.Println(heap.Peek())
  fmt.Println(heap.Pop())
  fmt.Println(heap.Peek())
}

出力

{9 lili}
{9 lili}
{10 John}

ジェネリックのサポートにより、ソート不可能な型でもコンパレータを渡すことでヒープを使用できるようになりました。これは以前に interface{} を使用して型変換とアサーションを行うよりも、はるかにエレガントで便利です。

オブジェクトプール

元のオブジェクトプールは any 型のみを使用でき、取得するたびに型アサーションを行う必要がありました。ジェネリックを使用して簡単に改善すると、この作業を省略できます。

package main

import (
	"bytes"
	"fmt"
	"sync"
)

func NewPool[T any](newFn func() T) *Pool[T] {
	return &Pool[T]{
		pool: &sync.Pool{
			New: func() interface{} {
				return newFn()
			},
		},
	}
}

type Pool[T any] struct {
	pool *sync.Pool
}

func (p *Pool[T]) Put(v T) {
	p.pool.Put(v)
}

func (p *Pool[T]) Get() T {
	var v T
	get := p.pool.Get()
	if get != nil {
		v, _ = get.(T)
	}
	return v
}

func main() {
	bufferPool := NewPool(func() *bytes.Buffer {
		return bytes.NewBuffer(nil)
	})

	for range 100 {
		buffer := bufferPool.Get()
		buffer.WriteString("Hello, World!")
		fmt.Println(buffer.String())
		buffer.Reset()
		bufferPool.Put(buffer)
	}
}

まとめ

Go の大きな特徴の 1 つはコンパイル速度が非常に速いことです。コンパイルが速いのは、コンパイル時に最適化が少ないためです。ジェネリックの追加はコンパイラの作業量を増やし、より複雑にします。これは必然的にコンパイル速度の低下を引き起こします。実際、Go1.18 がジェネリックを導入した当初、コンパイルがより遅くなったのは事実です。Go チームはジェネリックを追加したいが、コンパイル速度を大幅に低下させたくなく、開発者が使いやすく、コンパイラが苦しく、逆にコンパイラが楽（最も楽なのはジェネリックを完全に不要にすること）だと、開発者が苦しくなります。現在のジェネリックはこの 2 つの間で妥協した産物です。