generic algorithms and types


Foreword

Until recently, those who write in Go had two paths: copy-paste and code generation. I am not a fan of either the first or the second, but to my joy, now Go has generic types. It would seem that the problem is solved! But that was not the case, Go generics have very specific limitations that, spoil all the raspberries. One of them I wanted to deal with.

Issues

Note: Below there will be no explanation of “what are generic types in Go, and how to work with them”, for this information I propose to follow the site with the official documentation, where everything is chewed in some detail.

Take, for example, the pattern builder (builder) and use it to build a primitive calculator that can only add, subtract, divide, multiply, and return the result, creating a new instance after each operation:

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
}

Let the structure be considered the core of the calculator. Now we can build a couple of call chains:

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

Let’s assume that the structure Calc is a library structure, and we just want to add a command handler to it, coming from somewhere outside.

Note: The assumption above is important because otherwise it would be more logical to rewrite the calculator core code itself to support command processing than to fence the wrapper.

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
}

Great, now having a calculator core Calc and a command batch processor as a function ProcessCommandsyou can process commands coming from outside and return the result in one call:

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

Yes, now it doesn’t look so concise, but you can create a list of commands that need to be executed and postpone calculations until the right moment or repeat them several times:

// где-то в модуле 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

Now the use of commands does not look so pointless, and you can even implement calculator memory operations (M+, M-, MC) without modifying the kernel code, which, however, is beyond the scope of this topic.

At this stage, there are: a calculator core, commands, their batch processor and a crazy thought in my head … But what if we write another calculator core that will perform not scalar operations, but vector ones? The set of operations, though, remains the same, so methods like multiplication by a scalar will go overboard. No sooner said than done:

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
}

It is not difficult to see that both structures repeat the same interface:

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
}

The logical assumption would be to parameterize the type of the operand in the command in this way, as well as the types in the function ProcessCommands and get solution:

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
}

It is at this moment that the harsh reality hits on the head, and the compiler reports that T does not implement an interface Calculator[T, V]. On the one hand, it is strange, because it is clear that T – the core of the calculator, which is passed to the function ProcessCommands as an argument calcon the other hand, from the compiler’s point of view, the generic type definition T function header says that T is any typeany), so the compiler has no way of knowing that T it’s still the same type as Calculator[T, V].

Solution 1

Well, it doesn’t matter, you can add a bit of recursion to the definition of function types:

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
}

Great, now you can add work with the vector kernel:

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}

Solution 2

The method from the first solution works as long as the interface Calculator[T, V] is implemented using non-mutating methods, that is, methods that are passed a copy of the structure, and not a pointer to it. In the example with the calculator, immutability even works to our advantage, but in other cases it may be necessary to change the original object, say, for optimization purposes, or if necessary, store the pointer to the instance in another place. Next structure change Calc no longer allows it to be used as a type T for function 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
}

Now interface Calculator[T, V] will take the form:

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
}

Since the instance is now mutable, the main code needs to be rewritten to a and b did not refer to the same value:

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

On the function call line ProcessCommands the compiler will say that the structure Calc does not implement an interface Calculator[Calc, float64]. This is because the required interface only implements a pointer to the structure, not the instance itself. However, the type T already recursively described as T Calculator[T, V]which means that it must be implemented by the instance of the structure itself, which is obviously not the case.

Note: In some cases, it is not possible to obtain a pointer to a structure, for example, if the structure is stored in map as a value, not as a pointer.

You can try to return the type T any and try to get around the restriction with an explicit type cast:

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

But here, too, the calculator will send those who wish to do so on a long journey, filled with a spicy kind of fantasy. However, the solution lies on the surface: if at the function level ProcessCommands Since the correspondence of the type to the interface cannot be guaranteed, then it is necessary to perform the conversion at the level where it can be guaranteed, because when passing a pointer to the calculator core to the function, everything goes smoothly. If we slightly formalize the concept of a generic type, then the type Calculator[T, V] this is a function from T and Vit remains only to explicitly define its parameters:

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

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

Well, a safe type conversion has been obtained, it remains to implement it in the command processing function:

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
}

Now you can rewrite the function code main in the following way:

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())

Conclusion

Both solutions described above, like any other, have a limited range of applications. For example, if you write a similar calculator from scratch, initially implying that there can be several cores, then you can immediately lay the return of the interface by methods, instead of instances of the structure, although this contradicts the principles of Go, one of which says that the interface should be defined by the one who uses it , not one that returns data (accept interfaces – return values). Structure Calc will take the following form:

type Calc struct {
	value float64
}

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

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

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

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

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

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

No type conversions will be needed in the body ProcessCommandsbut this also means that the structure Calc needs to know about the existence of the interface Calculator[T, V], although it does not use it. Another option would be to add command handling support to the framework itself Calc.

However, if you want to execute a single algorithm using structures from a third-party library such as those described above Calc and VectorCalc, then you can use one of the methods described here. I myself faced a similar problem when using the library bun. It allows you to compose queries by chains of calls, the same as for a pointer to a structure bun.SelectQueryso on bun.UpdateQuery. I needed to be able to add identical parameters to both types of request, and although the names and parameters of the methods of both structures are identical, they returned pointers to their own types, which did not allow me to simply describe the interface and wrap instances in it:

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

It would be possible to use copy-paste or code generation, but the worm that lives in my brain again began to itch and whisper something about generics, keeping me awake at night.

Thanks to all those who read this text to the end, I hope that it seemed interesting to someone, and perhaps even saved time – the most valuable resource in our lives. Criticism, as always, is welcome, bringing ideas to mind together is always more productive and more fun.

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *