Generics in Go: functional programming is finally here

Posted on Dec 2, 2021

Go 1.18 introduces generics as part of the language. This post describes how to use it and look at how it enables functional programming.

FOREWORD

In case you are reading this before go 1.18 is released as stable:

You will have to build from sources — and gotip is there to help you with that.
If you are using VSCode, you can switch your go environment to gotip temporarily. To do this, hit ctrl+shift+P and search for “Choose go environment”, and select gotip. If you also want to have a working gopls, then you will have to either install an unstable version of gopls or name your files with a .go2 extension for gopls to understand the syntax (but gotip won’t pick them up).

Go generics 101

First, let’s read carefully the Abstract section of the Type Parameters Proposal:

We suggest extending the Go language to add optional type parameters to type and function declarations. Type parameters are constrained by interface types. Interface types, when used as type constraints, support embedding additional elements that may be used to limit the set of types that satisfy the constraint. Parameterized types and functions may use operators with type parameters, but only when permitted by all types that satisfy the parameter’s constraint. Type inference via a unification algorithm permits omitting type arguments from function calls in many cases. The design is fully backward compatible with Go 1.

Let’s define a couple of terms: type constraints and type parameters.

Type constraints

A type constraint defines what kind of type is needed in order to satisfy it. It is defined as an interface type, using the habitual syntax:

type Foo interface {
    Bar
}

Here, we are defining a type constraint named Foo, that describes types that are Bar. Bar can be another type constraint, an interface type, or a type.

Approximation constraint elements

Let’s define a constraint that describes a signed integer:

type Signed interface {
    int
}

Now, consider my custom type:

type MyDopeInt int

Will it satisfy that constraint? The answer is no!

MyDopeInt is a different type from int, even though they mean the same thing in the end. We need a way of specifying that we also want to cover alias types. For this, Go 1.18 introduces approximation constraint elements.

These elements are defined by prefixing the token ~ to a type, ~T meaning any type whose underlying type is T. Let’s update our previous Signed constraint:

type Signed interface {
    ~int
}

With this change, Signed does not mean anything that is of type int anymore, but anything whose underlying type is int. Now, MyDopeInt does satisfy our Signed constraint, as its underlying type is int. Approximation is not allowed on interface types and type parameters.

Union constraint element

Our current Signed constraint is not complete: what about other integer types? To define multiple elements in our constraint, we can use |. Let’s update our previous example:

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

Now, any signed integer type and any alias satisfies this constraint.

Actually, this Signed constraint is defined in a new package to define standard type constraints that is now available in the standard lib, and is called constraints.

The `any` constraint

The any keyword is equivalent to interface{}, and is meant to be used as a type constraint only. Do not see this as a wildcard constraint though, it has limitations: only operations permitted for any types are allowed here.

The `comparable` constraint

The comparable keyword is a predeclared type constraint for all types that are strictly comparable, meaning that we can use == or != on them.

Type parameters

Type parameters are the heart of generics in Go. They are abstract data types that are defined by a name and a type constraint. Let’s consider the following:

package main

import "fmt"

func Print[T any](s []T) {
    for _, v := range s {
        fmt.Print(v)
    }
}

func main() {
    Print([]string{"hello", " ", "world"})
    Print([]int{1,2,3})
    // output will be "hello world123"
}

The argument for Print is a slice of type T, and T is defined right after the function name, inside a bracket pair. Here, we define T as being of any type — we defined the any constraint earlier.

Here, we have generic functions!

Generic types

What about OOP, though? Well, generic types are what we need. Let’s define a generic type:

type Stack[T any] []T

Here, we define a Stack type, that is parameterized with a type T that should satisfy the type constraint any. Stack will be a slice of type T.

func NewStack[T any]() *Stack[T] {
	v := make(Stack[T], 0)
	return &v
}

We then define a constructor, that is nothing more than a generic function.

func (s *Stack[T]) Push(v T) {
	*s = append(*s, v)
}

func (s *Stack[T]) Pop() *T {
	if len(*s) == 0 {
		return nil
	}

	v := (*s)[len(*s)-1]
	*s = (*s)[:len(*s)-1]
	return &v
}

We then define a couple methods on it, to implement a stack. Now we can use it like this:

s := NewStack[int]()

v := s.Pop()
fmt.Println(v) //  <nil>

s.Push(1)
s.Push(2)
v = s.Pop()
fmt.Println(*v) // "2"

Functional programming

Could we now get the power of Map, Filter, Reduce […] in Go? Absolutely!

// Package slices implements various slice algorithms.
package slices

// Map turns a []T1 to a []T2 using a mapping function.
// This function has two type parameters, T1 and T2.
// This works with slices of any type.
func Map[T1, T2 any](s []T1, f func(T1) T2) []T2 {
	r := make([]T2, len(s))
	for i, v := range s {
		r[i] = f(v)
	}
	return r
}

// Reduce reduces a []T1 to a single value using a reduction function.
func Reduce[T1, T2 any](s []T1, initializer T2, f func(T2, T1) T2) T2 {
	r := initializer
	for _, v := range s {
		r = f(r, v)
	}
	return r
}

// Filter filters values from a slice using a filter function.
// It returns a new slice with only the elements of s
// for which f returned true.
func Filter[T any](s []T, f func(T) bool) []T {
	var r []T
	for _, v := range s {
		if f(v) {
			r = append(r, v)
		}
	}
	return r
}

With type inferance, using these feels extremely natural:

s := []int{1, 2, 3}

floats := slices.Map(s, func(i int) float64 { return float64(i) })
// Now floats is []float64{1.0, 2.0, 3.0}.

sum := slices.Reduce(s, 0, func(i, j int) int { return i + j })
// Now sum is 6.

evens := slices.Filter(s, func(i int) bool { return i%2 == 0 })
// Now evens is []int{2}.

The golang.org/x/exp/slices package, containing these functions, should get merged to the standard standard library in go v1.19. Do not use this x/exp package in anything that is meant to last — it is not stable. Just be patient!