Generics

Лекция 10

Максим Иванов

План лекции

2

Type parameters

3

Sorting in Go

Сейчас: 

func Sort(data Interface)

type Interface interface {
  Len() int
  Less(i, j int) bool
  Swap(i, j int)
}

Что хотим: 

func Sort(list []Elem)

// use
Sort(myList)
4

Используем type parameters

func Sort[Elem ?](list []Elem)

Параметризованный тип — это объявление типа с параметрами типа в квадратных скобках (например, `[T any]`),
из которого компилятор может получить множество конкретных типов, подставляя вместо параметров реальные типы (Sort[int], Sort[string] и т.п.).

5

Parameter lists

Аргументы функции 

(x, y aType, z anotherType)

Type параметры 

[P, Q aConstraint, R anotherConstraint]
6

Ограничения (Constraints)

7

Generic Sort

func Sort[Elem interface{ Less(y Elem) bool }](list []Elem) {
  ...
}
8

Generic Sort

Код в библиотеке: 

func Sort[Elem interface{ Less(y Elem) bool }](list []Elem)

Код пользователя: 

type book struct{...}
func (x book) Less(y book) bool {...}

var bookshelf []book
...
Sort[book](bookshelf) // generic function call
9

Проверка вызова Sort: инстанцирование

Что происходит, когда мы вызываем Sort? 

Sort[book](bookshelf)
Sort[Elem interface{ Less(y Elem) bool }] | (list []Elem)

Sort[book interface{ Less(y book) bool }] | (list []book)
Sort[book] | (list []book)
10

Type-checking generic-ов

Инстанцирование (новое)

Вызов (как обычно)

11

Типы тоже могут быть generic-ами

type Lesser[T any] interface{
  Less(y T) bool
}
12

Сортировка

type Lesser[T any] interface{
  Less(y T) bool
}

func Sort[Elem Lesser[Elem]](list []Elem)
13

Проблема

Что хотим: 

Sort([]int{1, 2, 3})

int не реализует "ограничение" Elem (нет метода Less)

Что можно было бы сделать 

type myInt int

func (x myInt) Less(y myInt) bool { return x < y }

Но что если ...

14

Проблема

Есть одно аккуратное решение 

// orderedSlice — это внутренний тип, который реализует sort.Interface.
// Метод Less использует оператор <. Ограничение типа Ordered
// гарантирует, что для T определён оператор <.
type orderedSlice[T constraints.Ordered] []T

func (s orderedSlice[T]) Len() int           { return len(s) }
func (s orderedSlice[T]) Less(i, j int) bool { return s[i] < s[j] }
func (s orderedSlice[T]) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

func Sort[T constraints.Ordered](s []T) {
    sort.Sort(orderedSlice[T](s))
}
15

min

func min(x, y int) int {
  if x < y {
    return x
  }
  return y
}
16

Generic min

func min[T constraints.Ordered](x, y T) T {
  if x < y {
    return x
  }
  return y
}

calling generic min 

m := min[int](1, 2)
17

Инстанцирование

fmin := min[float64] // non generic
m := fmin(2.71, 3.14)

компилятор создаёт специализированный вариант функции или типа.

18

Generic тип

type Tree[T any] struct {
    left, right *Tree[T]
    data T
}

func (t *Tree[T]) Lookup(x T) *Tree[T]

var stringTree Tree[string]
19

Type sets

20

Type sets

func min(x, y float64) float64
func min[T constraints.Ordered](x, y T) T {
21

constraints.Ordered

// Ordered — это "ограничение", которое допускает любой упорядоченный тип:
// любой тип, который поддерживает операторы < <= >= >.
// Если в будущих версиях Go появятся новые упорядоченные типы,
// в это "ограничение" будут добавлены новые типы.
type Ordered interface {
    Integer | Float | ~string
}
22

constraints

type Signed interface {
    ~int | ~int8 | ~int16 | ~int32 | ~int64
}

type Unsigned interface {
    ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}

type Integer interface {
    Signed | Unsigned
}

type Float interface {
    ~float32 | ~float64
}

type Complex interface {
    ~complex64 | ~complex128
}
23

comparable

comparable - встроенный идентификатор для всего, что можно сравнить с помощью == 

func SetFrom[T comparable](s []T) map[T]struct{} {
    m := make(map[T]struct{}, len(s))
    for _, v := range s {
        m[v] = struct{}{}
    }
    return m
}

начиная с Go 1.20 comparable также разрешён для интерфейсов

24

Constraints & type sets

type OrderedStringer interface {
    constraints.Ordered  // набор типов
    fmt.Stringer         // и интерфейс Stringer
}

type Int int
func (i Int) String() string { return strconv.Itoa(int(i)) }

func MaxString[T OrderedStringer](a, b T) string {
    if a > b {
        return a.String()
    }
    return b.String()
}
25

Короткая запись

[S interface{~[]E}, E interface{}]
[S ~[]E, E interface{}]
[S ~[]E, E any]
26

Type inference

27

Scale

type Point []uint32

func (p Point) String() string { return "" }

Хотим написать функцию ScaleAndPrint 

func ScaleAndPrint(p Point) {
    r := Scale(p, 2)
    fmt.Println(r.String())
}
28

Scale, first attempt

import "golang.org/x/exp/constraints"

type Point []uint32

func (p Point) String() string { return "" }

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
}

func ScaleAndPrint(p Point) {
    r := Scale(p, 2)
    fmt.Println(r.String())
}
29

Scale, first attempt

// Generic функция
func Scale[E constraints.Integer](s []E, c E) []E

// Подстановка E = uint32 (Point — это []uint32)
func Scale[uint32 constraints.Integer](s []uint32, c uint32) []uint32

// После проверки ограничений остаётся конкретная функция
func ScaleUint32(s []uint32, c uint32) []uint32 {
  r := make([]uint32, len(s))
  for i, v := range s {
    r[i] = v * c
  }
  return r
}
30

Scale, fixed

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
}
31

Scale, fixed

// Generic функция
func Scale[S ~[]E, E constraints.Integer](s S, c E) S

// Подстановка S = Point, E = uint32 (Point — это []uint32)
func Scale[Point ~[]uint32, uint32 constraints.Integer](s Point, c uint32) Point

// После проверки ограничений остаётся конкретная функция
func ScalePoint(s Point, c uint32) Point {
  r := make(Point, len(s))
  for i, v := range s {
    r[i] = v * c
  }
  return r
}

// Теперь r имеет тип Point, и у Point есть метод String, поэтому r.String() компилируется.
32

Scale, fixed

func Scale[S ~[]E, E constraints.Integer](s S, c E) S

vs 

func Scale[E constraints.Integer](s []E, c E) []E
33

Inference

func ScaleAndPrint(p Point) {
    r := Scale(p, 2)
    fmt.Println(r.String())
}

Почему нам не нужно явно указывать type параметры? 

r := Scale[Point, int32](p, 2)
34

Inference

35

Argument type inference

func Scale[S ~[]E, E constraints.Integer](s S, c E) S

type Point []int32

Scale(p, 2)
36

Constraint type inference

func Scale[S ~[]E, E constraints.Integer](s S, c E) S

type Point []int32

Scale(p, 2)
37

Разные type параметры — это разные типы

func invalid[Tx, Ty Ordered](x Tx, y Ty) Tx {
  ...
  if x < y { ...// INVALID
  ...
}
38

Связи между type параметрами

type Pointer[T any] interface {
  *T
}

func f[T any, PT Pointer[T]](p PT)

или 

func f[T any, PT interface{*T}](p PT)
39

Инстанцирование по выходному типу

func CallJSONRPC[Output any](method string) (Output, error) {
    var output Output

    resBytes, err := doCall(method)
    if err != nil {
        return output, err
    }

    err = json.Unmarshal(resBytes, &output)
    return output, err
}

Теперь нам не нужно руками писать шаблонный код для unmarshal: 

res, err := CallJSONRPC[BatchReadResponse]("batch_read")
40

Когда стоит использовать generic-и

Все это по сравнению с any

41

Когда generic-и лучше не использовать

мы можем написать 

func Concat[T fmt.Stringer](a, b T) string {
    return a.String() + b.String()
}

но почему бы не написать просто 

func Concat(a, b fmt.Stringer) string {
    return a.String() + b.String()
}

P.S. эквивалентны ли эти функции?

42

Когда generic-и лучше не использовать

package main

import "fmt"

func F[T ~[]T](t T) T {
    return t[1][3][3][7][6][6][6]
}

type G []G

func main() {
    g := make(G, 10)
    for i := range g {
        g[i] = g
    }
    fmt.Println(F(g))
}

Не делайте так...

43

Некоторые проблемы

func Smallest[E ~[]T, T constraints.Ordered](e E) (T, error) {
    if len(e) == 0 {
        var zero T
        return zero, errors.New("empty slice provided")
    }

    s := e[0]
    for _, v := range e[1:] {
        is v < s {
            s = v
        }
    }
    return s, nil
}
44

Некоторые проблемы

func Mul[T string | int](t T, cnt int) T {
    switch v := any(t).(type) {
    case string:
        v = strings.Repeat(v, cnt)
        return *(*T)(unsafe.Pointer(&v))
    case int:
        v *= cnt
        return *(*T)(unsafe.Pointer(&v))
    }
    panic("impossible type")
}
45

Summary

Generic-и — это «макросы», которые проверяются и разворачиваются по типам на этапе компиляции.

46

Ссылки

- предложение по добавлению generic-ов

- блог Go: «Зачем нужны generic-и?»

- GopherCon 2020, Robert Griesemer — доклад "Typing [Generic] Go"

47

Thank you

Максим Иванов

Use the left and right arrow keys or click the left and right edges of the page to navigate between slides.
(Press 'H' or navigate to hide this message.)