Как стать автором
Обновить

Go: обобщенные алгоритмы и типы

Время на прочтение 10 мин
Количество просмотров 9.8K

Предисловие

До недавнего времени у тех, кто пишет на Go было два пути: копипаста и кодогенерация. Фанатом ни первого, ни второго я не являюсь, однако к моей радости, теперь и в Go есть обобщенные типы. Казалось бы, проблема решена! Но не тут-то было, дженерики Go имеют весьма специфические ограничения, которые, портят всю малину. С одним из них мне и захотелось разобраться.

Проблематика

Примечание: Ниже не будет объяснения "что такое обобщенные типы в Go, и как с ними работать", за сей информацией предлагаю проследовать на сайт с официальной документацией, где все довольно подробно разжевано.

Возьмем, к примеру, паттерн строитель (builder) и построим с его помощью примитивный калькулятор, который будет уметь лишь складывать, вычитать, делить, умножать и возвращать результат, создавая новый экземпляр после каждой операции:

type Calc struct {
	value float64
}

func NewCalc(value float64) Calc {
	return Calc{value: value}
}

func (c Calc) Add(operand float64) Calc {
	return Calc{value: c.value + operand}
}

func (c Calc) Sub(operand float64) Calc {
	return Calc{value: c.value - operand}
}

func (c Calc) Mul(operand float64) Calc {
	return Calc{value: c.value * operand}
}

func (c Calc) Div(operand float64) Calc {
	return Calc{value: c.value / operand}
}

func (c Calc) Value() float64 {
	return c.value
}

Пусть структура будет считаться ядром калькулятора. Теперь можно построить пару цепочек вызовов:

calc := NewCalc(0)

a := calc.Add(6).Mul(3).Div(2).Sub(1).Value() // 8
b := calc.Sub(10).Div(2).Add(6).Value() // 1

fmt.Printf("a + b = %f\n", calc.Add(a).Add(b).Value()) // a + b = 9

Предположим, что структура Calc является библиотечной структурой, а мы лишь хотим добавить к ней обработчик команд, поступающих откуда-то извне.

Примечание: Предположение выше важно потому, что в противном случае логичней было бы переписать сам код ядра калькулятора для поддержки обработки команд, чем городить обертку. Весь код, относящийся к ядрам калькулятора, подразумевается как код, доставшийся в виде зависимости. Реализовывать подобным образом собственное решение крайне не рекомендуются! Другими словами, публикация пытается ответить на вопрос: каким образом можно использовать обобщенный алгоритм для необобщенных зависимостей?

type CommandName uint8

// Набор команд калькулятора.
const (
	CommandNameAdd CommandName = iota
	CommandNameSub
	CommandNameMul
	CommandNameDiv
)

// Структура содержащая имя команды и операнд.
type Command struct {
	Name    CommandName
	Operand Calc
}

// Пакетная обработка команд
func ProcessCommands(calc Calc, commands ...Command) Calc {
	for _, command := range commands {
		switch command.Name {
		case CommandNameAdd:
			calc = calc.Add(command.Operand.Value())
		case CommandNameSub:
			calc = calc.Sub(command.Operand.Value())
		case CommandNameMul:
			calc = calc.Mul(command.Operand.Value())
		case CommandNameDiv:
			calc = calc.Div(command.Operand.Value())
		}
	}

	return calc
}

Прекрасно, теперь, имея ядро калькулятора Calc и процессор пакетной обработки команд в виде функции ProcessCommands, можно обрабатывать приходящие извне команды и возвращать результат одним вызовом:

calc := NewCalc(0)

// в переменных a и b храним уже не числовые значения, а состояния калькулятора
a := ProcessCommands(calc,
	Command{CommandNameAdd, NewCalc(6)},
	Command{CommandNameMul, NewCalc(3)},
	Command{CommandNameDiv, NewCalc(2)},
	Command{CommandNameSub, NewCalc(1)},
)

b := ProcessCommands(calc,
	Command{CommandNameSub, NewCalc(10)},
	Command{CommandNameDiv, NewCalc(2)},
	Command{CommandNameAdd, NewCalc(6)},
)

// воспользуемся сохраненным состоянием калькулятора (`a`) и применим только одну команду для вычисления суммы
sum := ProcessCommands(a, Command{CommandNameAdd, b}).Value()
fmt.Printf("a + b = %f\n", sum) // a + b = 9

Да, теперь выглядит не так лаконично, зато можно создать список команд, которые необходимо выполнить и откладывать вычисления до нужного момента или повторять их несколько раз:

// где-то в модуле A
initA := []Command{
	{CommandNameAdd, NewCalc(6)},
	{CommandNameMul, NewCalc(3)},
	{CommandNameDiv, NewCalc(2)},
	{CommandNameSub, NewCalc(1)},
}

// где-то в модуле B
initB := []Command{
	{CommandNameSub, NewCalc(10)},
	{CommandNameDiv, NewCalc(2)},
	{CommandNameAdd, NewCalc(6)},
}

// где-то в основном модуле
calc := NewCalc(0)

a := ProcessCommands(calc, initA...)
b := ProcessCommands(calc, initB...)
sum := ProcessCommands(a, Command{CommandNameAdd, b}).Value()

fmt.Printf("a + b = %f\n", sum) // a + b = 9

Теперь использование команд выглядит уже не столь бессмысленным, и можно даже реализовать операции работы с памятью калькулятора (M+, M-, MC) без модификации кода ядра, что, впрочем, выходит за рамки рассматриваемой темы.

На данном этапе имеются: ядро калькулятора, команды, их пакетный обработчик и безумная мысль в голове... А что, если написать другое ядро калькулятора, которое будет выполнять не скалярные операции, а векторные? Набор операций, пускай, остается тем же, поэтому методы типа умножения на скаляр отправятся за борт. Сказано - сделано:

type Vector struct {
	X float64
	Y float64
	Z float64
}

type VectorCalc struct {
	value Vector
}

func NewVectorCalc(value Vector) VectorCalc {
	return VectorCalc{value: value}
}

func (c VectorCalc) Add(operand Vector) VectorCalc {
	return VectorCalc{
		value: Vector{
			X: c.value.X + operand.X,
			Y: c.value.Y + operand.Y,
			Z: c.value.Z + operand.Z,
		},
	}
}

func (c VectorCalc) Sub(operand Vector) VectorCalc {
	return VectorCalc{
		value: Vector{
			X: c.value.X - operand.X,
			Y: c.value.Y - operand.Y,
			Z: c.value.Z - operand.Z,
		},
	}
}

func (c VectorCalc) Mul(operand Vector) VectorCalc {
	return VectorCalc{
		value: Vector{
			X: c.value.Y*operand.Z - c.value.Z*operand.Y,
			Y: -(c.value.Z*operand.X - c.value.X*operand.Z),
			Z: c.value.X*operand.Y - c.value.Y*operand.X,
		},
	}
}

func (c VectorCalc) Div(operand Vector) VectorCalc {
	// так как операция деления для векторов в общем случае не определена
	panic("operation is not defined")
}

func (c VectorCalc) Value() Vector {
	return c.value
}

Не трудно видеть, что обе структуры повторяют один и тот же интерфейс:

type Calculator[T any, V any] interface {
	Add(operand V) T
	Sub(operand V) T
	Mul(operand V) T
	Div(operand V) T
	Value() V
}

Логичным предположением будет то, что нужно подобным образом параметризировать тип операнда в команде, а также типы в функции ProcessCommands и получить решение:

type Command[T any, V any] struct {
	Name    CommandName
	Operand Calculator[T, V]
}

func ProcessCommands[T any, V any](calc Calculator[T, V], commands ...Command[T, V]) Calculator[T, V] {
	for _, command := range commands {
		switch command.Name {
		case CommandNameAdd:
			calc = calc.Add(command.Operand.Value())
		case CommandNameSub:
			calc = calc.Sub(command.Operand.Value())
		case CommandNameMul:
			calc = calc.Mul(command.Operand.Value())
		case CommandNameDiv:
			calc = calc.Div(command.Operand.Value())
		}
	}

	return calc
}

Именно в этот момент суровая действительность бьет по голове, и компилятор сообщает о том, что T не реализует интерфейс Calculator[T, V]. С одной стороны странно, ведь понятно, что T - ядро калькулятора, которое и передается в функцию ProcessCommands в качестве аргумента calc, с другой - с точки зрения компилятора - определение обобщенного типа T заголовке функции гласит, что T - это любой тип (any), следовательно, компилятор не может никак знать, что T это все тот же тип, что и Calculator[T, V].

Решение 1

Что ж, не беда, можно добавить немного рекурсии в определение типов функции:

func ProcessCommands[T Calculator[T, V], V any](calc Calculator[T, V], commands ...Command[T, V]) Calculator[T, V] {
	for _, command := range commands {
		switch command.Name {
		case CommandNameAdd:
			calc = calc.Add(command.Operand.Value())
		case CommandNameSub:
			calc = calc.Sub(command.Operand.Value())
		case CommandNameMul:
			calc = calc.Mul(command.Operand.Value())
		case CommandNameDiv:
			calc = calc.Div(command.Operand.Value())
		}
	}

	return calc
}

Отлично, теперь можно добавить и работу с векторным ядром:

initA := []Command[Calc, float64]{
	{CommandNameAdd, NewCalc(6)},
	{CommandNameMul, NewCalc(3)},
	{CommandNameDiv, NewCalc(2)},
	{CommandNameSub, NewCalc(1)},
}

initB := []Command[Calc, float64]{
	{CommandNameSub, NewCalc(10)},
	{CommandNameDiv, NewCalc(2)},
	{CommandNameAdd, NewCalc(6)},
}

calc := NewCalc(0)

a := ProcessCommands[Calc, float64](calc, initA...)
b := ProcessCommands[Calc, float64](calc, initB...)
sum := ProcessCommands(a, Command[Calc, float64]{CommandNameAdd, b}).Value()

fmt.Printf("a + b = %f\n", sum) // a + b = 9

initVectorA := []Command[VectorCalc, Vector]{
	{CommandNameAdd, NewVectorCalc(Vector{1, 1, 1})},
	{CommandNameMul, NewVectorCalc(Vector{2, -2, 2})},
}

initVectorB := []Command[VectorCalc, Vector]{
	{CommandNameSub, NewVectorCalc(Vector{10, 10, 10})},
}

vcalc := NewVectorCalc(Vector{})

va := ProcessCommands[VectorCalc, Vector](vcalc, initVectorA...)
vb := ProcessCommands[VectorCalc, Vector](vcalc, initVectorB...)

fmt.Println(va.Value(), vb.Value()) // {4 -0 -4} {-10 -10 -10}

vsum := ProcessCommands(va, Command[VectorCalc, Vector]{CommandNameAdd, vb}).Value()

fmt.Printf("a + b = %v\n", vsum) // a + b = {-6 -10 -14}

Решение 2

Метод из первого решения работает до тех пор, пока интерфейс Calculator[T, V] реализуется при помощи немутирующих методов, то есть таких методов, в которые передается копия структуры, а не указатель на нее. В примере с калькулятором иммутабельность нам даже на руку, но в других случаях может понадобиться изменять исходный объект, скажем, в целях оптимизации либо при необходимости хранить указатель на экземпляр в другом месте. Следующее изменение структуры Calc уже не позволяет применить ее в качестве типа T для функции ProcessCommands:

type Calc struct {
	value float64
}

func NewCalc(value float64) *Calc {
	return &Calc{value: value}
}

func (c *Calc) Add(operand float64) *Calc {
	c.value += operand
	return c
}

func (c *Calc) Sub(operand float64) *Calc {
	c.value -= operand
	return c
}

func (c *Calc) Mul(operand float64) *Calc {
	c.value *= operand
	return c
}

func (c *Calc) Div(operand float64) *Calc {
	c.value /= operand
	return c
}

func (c *Calc) Value() float64 {
	return c.value
}

Теперь интерфейс Calculator[T, V] примет вид:

type Calculator[T any, V any] interface {
	Add(operand V) *T
	Sub(operand V) *T
	Mul(operand V) *T
	Div(operand V) *T
	Value() V
}

Так как экземпляр теперь мутабелен, нужно переписать главный код, чтобы a и b не ссылались на одно и то же значение:

initA := []Command[Calc, float64]{
	{CommandNameAdd, NewCalc(6)},
	{CommandNameMul, NewCalc(3)},
	{CommandNameDiv, NewCalc(2)},
	{CommandNameSub, NewCalc(1)},
}

initB := []Command[Calc, float64]{
	{CommandNameSub, NewCalc(10)},
	{CommandNameDiv, NewCalc(2)},
	{CommandNameAdd, NewCalc(6)},
}

// так как объект мутабелен, то стартовых экзепляра потребуется два
sum := NewCalc(0)
a := ProcessCommands[Calc, float64](sum, initA...)
b := ProcessCommands[Calc, float64](NewCalc(0), initB...)
// результат можно не сохранять, так как ядро мутабельно
ProcessCommands(a, Command[Calc, float64]{CommandNameAdd, b})

fmt.Printf("a + b = %f\n", sum.Value()) // a + b = 9
// так как a и sum ссылаются на один и тот же экземпляр ядра, то
fmt.Printf("a == sum = %t\n", sum.Value() == a.Value()) // a == sum = true

На строке вызова функции ProcessCommands компилятор скажет, что структура Calc не реализует интерфейс Calculator[Calc, float64]. Так происходит потому, что требуемый интерфейс реализует лишь указатель на структуру, но не сам экземпляр. Однако тип T уже рекурсивно описан как T Calculator[T, V], а значит, должен реализовываться и самим экземпляром структуры, что, очевидно, не так.

Примечание: В некоторых случаях невозможно получить указатель на структуру, например, если структура хранится в map в виде значения, а не указателя.

Можно попытаться вернуть тип T any и попытаться обойти ограничение при помощи явного приведения типа:

calc = calc.Add(command.Operand).(Calculator[T, V])

Но и здесь калькулятор отправит желающего так сделать в долгий путь, наполненный пикантного рода фантазиями. Тем не менее, решение лежит на поверхности: если на уровне функции ProcessCommands соответствие типа интерфейсу не может быть гарантировано, то нужно произвести преобразование на том уровне, где оно может быть гарантировано, ведь при передаче указателя на ядро калькулятора в функцию все проходит гладко. Если немного формализовать понятие обобщенного типа, то тип Calculator[T, V] это функция от T и V, остается лишь явно определить ее параметры:

func CastCalc(calc *Calc) Calculator[Calc, float64] { return calc }

func CastVCalc(calc *VectorCalc) Calculator[VectorCalc, Vector] { return calc }

Что ж, безопасный способ приведения типа получен, осталось внедрить его в функцию обработки команд:

func ProcessCommands[T any, V any](calc Calculator[T, V], cast func(*T) Calculator[T, V], commands ...Command[V]) Calculator[T, V] {
	for _, command := range commands {
		switch command.Name {
		case CommandNameAdd:
			calc = cast(calc.Add(command.Operand))
		case CommandNameSub:
			calc = cast(calc.Sub(command.Operand))
		case CommandNameMul:
			calc = cast(calc.Mul(command.Operand))
		case CommandNameDiv:
			calc = cast(calc.Div(command.Operand))
		}
	}

	return calc
}

Теперь можно переписать код функции main следующим образом:

initA := []Command[Calc, float64]{
	{CommandNameAdd, NewCalc(6)},
	{CommandNameMul, NewCalc(3)},
	{CommandNameDiv, NewCalc(2)},
	{CommandNameSub, NewCalc(1)},
}

initB := []Command[Calc, float64]{
	{CommandNameSub, NewCalc(10)},
	{CommandNameDiv, NewCalc(2)},
	{CommandNameAdd, NewCalc(6)},
}

sum := NewCalc(0)
a := ProcessCommands[Calc, float64](sum, CastCalc, initA...)
b := ProcessCommands[Calc, float64](NewCalc(0), CastCalc, initB...)
ProcessCommands(a, CastCalc, Command[Calc, float64]{CommandNameAdd, b})

fmt.Printf("a + b = %f\n", sum.Value()) // a + b = 9
fmt.Printf("a == sum = %t\n", sum.Value() == a.Value())

initVectorA := []Command[VectorCalc, Vector]{
	{CommandNameAdd, NewVectorCalc(Vector{1, 1, 1})},
	{CommandNameMul, NewVectorCalc(Vector{2, -2, 2})},
}

initVectorB := []Command[VectorCalc, Vector]{
	{CommandNameSub, NewVectorCalc(Vector{10, 10, 10})},
}

vsum := NewVectorCalc(Vector{})

va := ProcessCommands[VectorCalc, Vector](vsum, CastVCalc, initVectorA...)
vb := ProcessCommands[VectorCalc, Vector](NewVectorCalc(Vector{}), CastVCalc, initVectorB...)

fmt.Println(va.Value(), vb.Value())

ProcessCommands(va, CastVCalc, Command[VectorCalc, Vector]{CommandNameAdd, vb})

fmt.Printf("a + b = %v\n", vsum.Value())

Заключение

Оба решения, описанных выше, как и любые другие, имеют ограниченный спектр применений. Например, если писать подобный калькулятор с нуля, изначально подразумевая что ядер может быть несколько, то можно сразу заложить возврат интерфейса методами, вместо экземпляров структуры, хоть это и противоречит принципам Go, один из которых гласит, что интерфейс должен определять тот, кто его использует, а не тот, кто возвращает данные (принимайте интерфейсы - возвращайте значения). Структура Calc и интерфейс Calculator примут следующий вид:

type Calculator[T any] interface {
	Add(operand T) Calculator[T]
	Sub(operand T) Calculator[T]
	Mul(operand T) Calculator[T]
	Div(operand T) Calculator[T]
	Value() T
}

type Calc struct {
	value float64
}

func NewCalc(value float64) *Calc {
	return &Calc{value: value}
}

func (c *Calc) Add(operand float64) Calculator[float64] {
	c.value += operand
	return c
}

func (c *Calc) Sub(operand float64) Calculator[float64] {
	c.value -= operand
	return c
}

func (c *Calc) Mul(operand float64) Calculator[float64] {
	c.value *= operand
	return c
}

func (c *Calc) Div(operand float64) Calculator[float64] {
	c.value /= operand
	return c
}

func (c *Calc) Value() float64 {
	return c.value
}

Никакие преобразования типов уже не будут нужны в теле ProcessCommands, однако это же означает, что структура Calc должна знать о наличии интерфейса Calculator[T], хотя не использует его. Другим вариантом было бы добавить поддержку обработки команд в саму структуру Calc.

Тем не менее, если требуется выполнять единый алгоритм, используя структуры из сторонней библиотеки такими как описанные выше Calc и VectorCalc, то можно применить один из описанных здесь методов. Сам же я столкнулся с подобной задачей при использовании библиотеки bun. Она позволяет составлять запросы цепочками вызовов, одинаковыми как для указателя на структуру bun.SelectQuery, так и на bun.UpdateQuery. Мне было нужно позволить добавлять идентичные параметры в оба типа запроса и, хотя имена и параметры методов обеих структур идентичны, они возвращали указатели на собственные типы, что не позволяло просто описать интерфейс и оборачивать экземпляры в него:

func (q *UpdateQuery) Where(query string, args ...interface{}) *UpdateQuery

func (q *SelectQuery) Where(query string, args ...interface{}) *SelectQuery

func (q *DeleteQuery) Where(query string, args ...interface{}) *DeleteQuery

Можно было бы применить копипасту или кодогенерацию, но тот червь, что живет в моем мозгу, опять начал зудеть и нашептывать что-то про дженерики, не давая спать по ночам.

Спасибо всем тем, кто дочитал этот текст до конца, надеюсь, что кому-то он показался интересным, а, быть может, даже сэкономил время - самый ценный ресурс в нашей жизни. Критика, как всегда, приветствуется, доводить идеи до ума вместе всегда продуктивнее и веселее.

Теги:
Хабы:
+4
Комментарии 6
Комментарии Комментарии 6

Публикации

Истории

Работа

Go разработчик
141 вакансия

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн