Generics in Go

TL;DR

Go 1.18 以后，interface 可以包含方法和其它 interface（和 1.18 前一样），也可以包含非 interface 类型、unions 和 underlying types 的集合。

一个 interface 类型定义了一种 type set，这样的 type set 可以被用作 type constraint。

普通函数 func Min(x, y float64) 中：

(x, y float64) 是参数列表，定义了每个参数的类型。

包含泛型的函数 func GMin[T constraints.Ordered](x, y T) T 中：

方括号里的是 type constraint 的列表。
- T 在此处用作 constraints.Ordered 这一 type constraint 的形参名。
- 每个 type constraint 定义了一个类型（们）的集合（a set of types）。
泛型函数同样有参数列表。

Basics

Generics are a way of writing code that is independent of the specific types being used. Functions and types may now be written to use any of a set of types.

Generics add three new big things to the language:

Type parameters for function and types.
- 对标 value parameters.
Defining interface types as sets of types, including types that don’t have methods.
Type inference, which permits omitting type arguments in many cases when calling a function.

Type Parameters

Functions and types are now permitted to have type parameters.

A type parameter list looks like an ordinary parameter list, except that it uses square brackets instead of parentheses.

func Index[T comparable](s []T, x T) int means that s is a slice of any type T that fulfills the built-in constraint comparable. x is also a value of the same type.

comparable is a useful constraint that makes it possible to use the == and != operators on values of the type.
This Index function works for any type that supports comparison.

import "golang.org/x/exp/constraints"
func GMin[T constraints.Ordered](x, y T) T {
	if x < y {
		return x
	}
	return y
}
func main() {
	x := GMin[int](2, 3)
}

Providing the type argument to GMin, in this case int, is called instantiation.
1. First, the compiler substitutes all type arguments for their respective type parameters throughout the generic function or type.
2. Second, the compiler verifies that each type argument satisfies the respective constraint.
After successful instantiation we have a non-generic function that can be called just like any other function.
```
fmin := GMin[float64]
m := fmin(2.71, 3.14)
```
- The instantiation GMin[float64] produces what is effectively our original floating-point Min function, and we can use that in a function call.

Type parameters can be used with types:

type Tree[T interface{}] struct {
    left, right *Tree[T]
    value       T
}
func (t *Tree[T]) Lookup(x T) *Tree[T] { ... }
var stringTree Tree[string]

The generic type Tree stores values of the type parameter T.
Generic types can have methods, like Lookup in this example.
In order to use a generic type, it must be instantiated; Tree[string] is an example of instantiating Tree with the type argument string.

Type Sets

An ordinary function has a type for each value parameter; that type defines a set of values.

For instance, if we have a float64 type as in the non-generic function Min, the permissible set of argument values is the set of floating-point values that can be represented by the float64 type.

Similarly, type parameter lists have a type for each type parameter.

Because a type parameter is itself a type, the types of type parameters define sets of types.
This meta-type is called a type constraint.
- In the generic GMin, the type constraint is imported from the constraints package.
  - The Ordered constraint describes the set of all types with values that can be ordered, or, in other words, compared with the < operator (or <= , > , etc.).
  - The constraint ensures that only types with orderable values can be passed to GMin.
  - It also means that in the GMin function body values of that type parameter can be used in a comparison with the < operator.

Another perspective of looking at interface is that interface defines a type set, and each type within it implements all the methods of the interface.

We can explicitly add types to the type set.
Go has extended the syntax for interface types to make this work.
- For instance, interface{ int|string|bool } defines the type set containing the types int, string, and bool. Another way of saying this is that this interface is satisfied by only int, string, or bool.

// constraints.Ordered
type Ordered interface {
	Integer | Float | ~string
}
type Integer interface {
	Signed | Unsigned
}
type Float interface {
	~float32 | ~float64
}

The Ordered interface is the set of all integer, floating-point, and string types.
The vertical bar expresses a union of types (or sets of types in this case).
Integer and Float are interface types that are similarly defined in the constraints package.
- There are no methods defined by the Ordered interface.
The expression ~string means the set of all types whose underlying type is string.

In Go 1.18 an interface may contain methods and embedded interfaces just as before, but it may also embed non-interface types, unions, and sets of underlying types.

When used as a type constraint, the type set defined by an interface specifies exactly the types that are permitted as type arguments for the respective type parameter.

Interfaces used as constraints may be given names (such as Ordered), or they may be literal interfaces inlined in a type parameter list.

Within a generic function body, if the type of a operand is a type parameter P with constraint C, operations are permitted if they are permitted by all types in the type set of C (there are currently some implementation restrictions here, but ordinary code is unlikely to encounter them).

Interfaces used as constraints may be given names (such as Ordered), or they may be literal interfaces inlined in a type parameter list.

For example: [S interface{~[]E}, E interface{}]
- Here S must be a slice type whose element type can be any type.
- Because this is a common case, the enclosing interface{} may be omitted for interfaces in constraint position, and we can simply write: [S ~[]E, E interface{}]
- Go 1.18 introduces a new predeclared identifier any as an alias for the empty interface type, we can write [S ~[]E, E any]

Type Inference

Type inference lets people use a natural style when writing code that calls generic functions.

func GMin[T constraints.Ordered](x, y T) T { ... }
var a, b, m float64

m = GMin[float64](a, b) // explicit type argument, float64
m = GMin(a, b) // no type argument

In many cases the compiler can infer the type argument for T from the ordinary arguments.
- This works by matching the types of the arguments a and b with the types of the parameters x, and y.
This kind of inference, which infers the type arguments from the types of the arguments to the function, is called function argument type inference.
- 由 a 和 b（types of the arguments）推断出 T（type argument）。
Function argument type inference only works for type parameters that are used in the function parameters, not for type parameters used only in function results or only in the function body.
- For example, it does not apply to functions like MakeT[T any]() T, that only uses T for a result.

func Scale[E constraints.Integer](s []E, c E) []E {
    r := make([]E, len(s))
    for i, v := range s {
        r[i] = v * c
    }
    return r
}

type Point []int32
func (p Point) String() string {
    return "Implementation details not important."
}
func ScaleAndPrint(p Point) {
    r := Scale(p, 2)
    fmt.Println(r.String()) // DOES NOT COMPILE: r.String undefined (type []int32 has no field or method String)
}

The problem is that the Scale function returns a value of type []E where E is the element type of the argument slice. When we call Scale with a value of type Point, whose underlying type is []int32, we get back a value of type []int32, not type Point.
In order to fix this, we have to change the Scale function to use a type parameter for the slice type.
```
// https://go.dev/play/p/LGBGJicuWpQ
func Scale[S ~[]E, E constraints.Integer](s S, c E) S {
    r := make(S, len(s))
    for i, v := range s {
        r[i] = v * c
    }
    return r
}
func ScaleAndPrint(p Point) {
    r := Scale(p, 2) // no need to write Scale[Point, int32](p, 2)
    fmt.Println(r.String())
}
```
- We’ve introduced a new type parameter S that is the type of the slice argument such that the underlying type is S rather than []E.
- Our new Scale function has two type parameters, S and E.
  - In a call to Scale not passing any type arguments, function argument type inference lets the compiler infer that the type argument for S is Point.
  - The function also has a type parameter E which is the type of the multiplication factor c. The corresponding function argument is 2, and because 2 is an untyped constant, function argument type inference cannot infer the correct type for E (at best it might infer the default type for 2 which is int and which would be incorrect). Instead, the process by which the compiler infers that the type argument for E is the element type of the slice is called constraint type inference.

Constraint type inference deduces type arguments from type parameter constraints. It is used when one type parameter has a constraint defined in terms of another type parameter.

In the Scale example, S is ~[]E, which is ~ followed by a type []E written in terms of another type parameter. If we know the type argument for S we can infer the type argument for E. S is a slice type, and E is the element type of that slice.

The exact details of how type inference works are complicated, but using it is not: type inference either succeeds or fails.

If it succeeds, type arguments can be omitted, and calling generic functions looks no different than calling ordinary functions.
If type inference fails, the compiler will give an error message, and in those cases we can just provide the necessary type arguments.

When To Use Generics

A general guideline for programming Go is “write Go programs by writing code, not by defining types”. When it comes to generics, start by writing functions.

If you start writing your program by defining type parameter constraints, you are probably on the wrong path.
It’s easy to add type parameters later when it’s clear that they will be useful.

References

An Introduction To Generics

https://go.dev/tour/generics/1

Contents