Go Language Generics Example

Slicing Operations

Functions like Map/Reduce/Filter are often used in functional programming. Because of generics, we can also write Map/Reduce/Filter functions that can be adapted to any type 😂.

All three of these functions are used to process sliced data, so Go officially wanted to provide a standard slices package. But it’s subject to Rob’s objection, so it has to go under exp package underneath.

// The slices package implements a series of slicing algorithms.
package slices

// Map uses the map function to convert []T1 to []T2.
// This function has two type parameters, T1 and T2.
// The map function f accepts two type types, T1 and T2.
// This function can handle all types of sliced data.
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 uses the summary function to aggregate []T1 slices into a single result.
	r := initializer
	for _, v := range s {
		r = f(r, v)
	}
	return r
}

// Filter uses the filter function to filter the data in a slice.
// The function returns a new slice, keeping only the elements for which the call to f returns 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
}

Examples of use are as follows, with all type parameters determined by derivation.

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

floats := slices.Map(s, func(i int) float64 { return float64(i) })
// The values of floats are []float64{1.0, 2.0, 3.0}.

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

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

Dictionary Operations

The following functions are given to extract a list of arbitrary dictionary keys.

// The maps package provides working dictionary handling functions.
package maps

// Keys returns a slice of the key of any dictionary.
// The order of the keys is not determined.
// This function takes two type parameters, K and V.
// Since the keys of a dictionary must support equal comparisons, K needs to satisfy the comparable constraint.
// The value of the dictionary can be of any type.
func Keys[K comparable, V any](m map[K]V) []K {
	r := make([]K, 0, len(m))
	for k := range m {
		r = append(r, k)
	}
	return r
}

A typical example of use is as follows, with the type parameter determined by derivation.

1
2

k := maps.Keys(map[int]int{1:2, 2:4})
// Now the values of k are []int{1, 2} or []int{2, 1}.

Set Operations

Go’s map itself supports different types of K-V, so you can generally implement collection operations with map. However, with generics, we can also develop specialized collection types.

// sets package implements set functionality, elements need to support equality comparisons.
package sets

// Set is a collection of elements.
type Set[T comparable] map[T]struct{}

// Make constructs a collection object of a certain type.
func Make[T comparable]() Set[T] {
	return make(Set[T])
}

// Add Adds v to the collection.
func (s Set[T]) Add(v T) {
	s[v] = struct{}{}
}

// Delete Removes v from the collection.
func (s Set[T]) Delete(v T) {
	delete(s, v)
}

// Contains the query if the collection contains v.
func (s Set[T]) Contains(v T) bool {
	_, ok := s[v]
	return ok
}

// Len returns the number of collection elements.
func (s Set[T]) Len() int {
	return len(s)
}

// Iterate iterates through each element of the collection, executing the function f.
// The Delete method can be called in function f.
func (s Set[T]) Iterate(f func(T)) {
	for v := range s {
		f(v)
	}
}

Examples of use are as follows.

// Create a new set of integers.
// Since the Make function does not use the type parameter T in its arguments, it is not possible to determine the actual type of T by type derivation
// The actual type of T cannot be determined by type derivation, but can only be specified manually.
s := sets.Make[int]()

// Add 1 to the set
s.Add(1)

// Make sure the set s does not contain the number 2
if s.Contains(2) { panic("unexpected 2") }

In general, however, a new collection defined using a generic type is not much different from using a map directly.

Sorting Operations

Because there are no generics, the Go language’s sort package provides three sort functions, Float64/Ints/Strings. If you want to sort floating point numbers or integer slices, you have to switch to float64/int slices first, which is very annoying. With the generic type, we can handle sorting algorithms of primitive types in a uniform way.

The elements of slices that support sorting need to support the compare size operation. For developers’ convenience, Go officially provides the constraints.Ordered constraint to represent all built-in types that support sorting. So our unified algorithm can be written as follows.

// orderedSlice implements the sort.Interface interface.
// The Less method uses the < operator. constraints.Ordered constraint ensures that type T supports the < operator.
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] }

// OrderedSlice sorts the slices s in ascending order.
// The elements of s need to support the < operator.
func OrderedSlice[T constraints.Ordered](s []T) {
	// Force s into orderedSlice[T], so that sorting can be done using sort.
	sort.Sort(orderedSlice[T](s))
}

Examples of use are as follows.

s1 := []int32{3, 5, 2}
sort.OrderedSlice(s1)
// Now the value of s1 is []int32{2, 3, 5}

s2 := []string{"a", "c", "b"})
sort.OrderedSlice(s2)
// Now the value of s2 is []string{"a", "b", "c"}

The sort package also provides a Slice method, but it requires a reference to the slices being sorted via a closure, which is less convenient.

type Person struct {
	Name string
	Age int
}
people := []Person{
	{"Gopher", 7},
	{"Alice", 55},
	{"Vera", 24},
	{"Bob", 75},
}
sort.Slice(people, func(i, j int) bool { return people[i].Name < people[j].Name })

We can write a unified treatment using the generic type.

// sliceFn implements the sort.Interface interface.
// The Less method actually calls the comparison function saved by cmp.
type sliceFn[T any] struct {
	s   []T
	cmp func(T, T) bool
}

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

// SliceFn sorts slice s according to the comparison function cmp.
func SliceFn[T any](s []T, cmp func(T, T) bool) {
	sort.Sort(sliceFn[T]{s, cmp})
}

So the original comparison function could then be rewritten as follows.

`1`	`sort.SliceFn(s, func(p1, p2 Person) bool { return p1.Name < p2.Name })`

Channel operations

With generic types, we can unify some common channel operations. For example, the following example.

// The chans package implements some channel manipulation algorithms.
package chans

import "runtime"

// Drain discards all elements of the chan.
func Drain[T any](c <-chan T) {
	for range c {
	}
}

// Merge merges two chans and outputs the elements to the other chan.
func Merge[T any](c1, c2 <-chan T) <-chan T {
	r := make(chan T)
	go func(c1, c2 <-chan T, r chan<- T) {
		defer close(r)
		for c1 != nil || c2 != nil {
			select {
			case v1, ok := <-c1:
				if ok {
					r <- v1
				} else {
					c1 = nil
				}
			case v2, ok := <-c2:
				if ok {
					r <- v2
				} else {
					c2 = nil
				}
			}
		}
	}(c1, c2, r)
	return r
}

// Ranger provides a mechanism to notify the sender to quit when the receiver is no longer working.
//
// Ranger returns a Sender/Receiver pair. receiver provides a Next method to receive content.
// Sender provides a Send to send content and a Close method to stop sending.
// Next detects if the Sender is closed, and the Send method detects if the Receiver has exited.
func Ranger[T any]() (*Sender[T], *Receiver[T]) {
	c := make(chan T)
	d := make(chan bool)
	s := &Sender[T]{values: c, done: d}
	r := &Receiver[T]{values: c, done: d}
	// If the receiver has been recalled, the sender will be notified using the finalizer.
	runtime.SetFinalizer(r, r.finalize)
	return s, r
}

// Sender is used to send messages to the Receiver.
type Sender[T any] struct {
	values chan<- T
	done   <-chan bool
}

// Send sends a message to the receiver. Return false for failure to send.
func (s *Sender[T]) Send(v T) bool {
	select {
	case s.values <- v:
		return true
	case <-s.done:
		// The recipient has exited
		return false
	}
}

// Close informs the receiver that the sending of the message has ended.
// The Sender object should not be used after the Close call.
func (s *Sender[T]) Close() {
	close(s.values)
}

// Receiver is used to receive messages from Sender.
type Receiver[T any] struct {
	values <-chan T
	done  chan<- bool
}

// Next returns the received message. If the message is not received, the sender has exited.
func (r *Receiver[T]) Next() (T, bool) {
	v, ok := <-r.values
	return v, ok
}

// finalize will notify the sender to stop sending when the Receiver is destroyed.
func (r *Receiver[T]) finalize() {
	close(r.done)
}

See the next subsection for usage examples.

Container Definition

With generic types, we can define type-safe containers. Instead of converting types back and forth as we did before.

Here we provide an implementation of an ordered map.

// The orderedmaps package implements ordered dictionaries based on binary trees.
package orderedmaps

import "chans"

// Map is an ordered dictionary.
type Map[K, V any] struct {
	root    *node[K, V]
	compare func(K, K) int
}

// node is a node in a binary tree.
type node[K, V any] struct {
	k           K
	v           V
	left, right *node[K, V]
}

// New Constructs a new dictionary.
// Because the type parameter V is only used in the return value, it cannot be confirmed by type inference.
// So the type of all type parameters must be specified when calling the New function.
func New[K, V any](compare func(K, K) int) *Map[K, V] {
	return &Map[K, V]{compare: compare}
}

// find looks up the node of k from the dictionary. If it exists, return the corresponding pointer.
// If it does not exist, return the location where k needs to be saved.
func (m *Map[K, V]) find(k K) **node[K, V] {
	pn := &m.root
	for *pn != nil {
		switch cmp := m.compare(k, (*pn).k); {
		case cmp < 0:
			pn = &(*pn).left
		case cmp > 0:
			pn = &(*pn).right
		default:
			return pn
		}
	}
	return pn
}

// Insert adds a new K-V.
// Existing values will be overwritten.
// Return true if it is a new key.
func (m *Map[K, V]) Insert(k K, v V) bool {
	pn := m.find(k)
	if *pn != nil {
		(*pn).v = v
		return false
	}
	*pn = &node[K, V]{k: k, v: v}
	return true
}

// Find the value corresponding to k, or return the null value corresponding to V if it does not exist.
// If k does not exist, the second argument returns false.
func (m *Map[K, V]) Find(k K) (V, bool) {
	pn := m.find(k)
	if *pn == nil {
		var zero V // Note the use of null values
		return zero, false
	}
	return (*pn).v, true
}

// keyValue k-v pair used when traversing the dictionary
type keyValue[K, V any] struct {
	k K
	v V
}

// InOrder returns a mid-order traversal iterator. Supports concurrent operations.
func (m *Map[K, V]) InOrder() *Iterator[K, V] {
	type kv = keyValue[K, V] // Specify generic parameters to simplify type references
	sender, receiver := chans.Ranger[kv]()
	var f func(*node[K, V]) bool
	f = func(n *node[K, V]) bool {
		if n == nil {
			return true
		}
		// If sender.Send returns false then stop sending the send.
		// because the receiver has stopped working at that point.
		return f(n.left) &&
			sender.Send(kv{n.k, n.v}) &&
			f(n.right)
	}
	go func() {
		f(m.root)
		sender.Close()
	}()
	return &Iterator[K, V]{receiver}
}

// Iterator is used to iterate through an ordered dictionary.
type Iterator[K, V any] struct {
	r *chans.Receiver[keyValue[K, V]]
}

// Next returns the next key-value pair. If the bool value is false, the iteration is complete.
func (it *Iterator[K, V]) Next() (K, V, bool) {
	kv, ok := it.r.Next()
	return kv.k, kv.v, ok
}

Examples of use are as follows.

import "container/orderedmaps"

var m = orderedmaps.New[string, string](strings.Compare)

// Add Add k-v
func Add(a, b string) {
	m.Insert(a, b)
}

i := m.InOrder()
for {
	k, v, ok := i.Next()
	if !ok {
		break
	}
	// ...
}

Append Functions

Go has a built-in append function that allows you to append elements to arbitrary type slices. However, if Go supports generics from the start, there is no need to introduce this built-in function.

// Append appends element t to the end total of slice s, returning the appended slice.
// If s has enough capacity, it is expanded in place; otherwise it is allocated and a new slice is returned.
func Append[T any](s []T, t ...T) []T {
	lens := len(s)
	tot := lens + len(t)
	if tot < 0 {
		panic("Append: cap out of range")
	}
	if tot > cap(s) {
		news := make([]T, tot, tot + tot/2)
		copy(news, s)
		s = news
	}
	s = s[:tot]
	copy(s[lens:], t)
	return s
}

Use the following method.

1
2

s := slices.Append([]int{1, 2, 3}, 4, 5, 6)
// The effect is equivalent to s := append([]int{1, 2, 3}, 4, 5, 6)

Linked List

// lists implements a linked List that supports elements of arbitrary type.
package lists

// List is a linked List object.
type List[T any] struct {
	head, tail *element[T]
}

// element Holds information about the elements of the Linked List
type element[T any] struct {
	next *element[T]
	val  T
}

// Push appends an element to the end of the Linked List.
func (lst *List[T]) Push(v T) {
	if lst.tail == nil {
		lst.head = &element[T]{val: v}
		lst.tail = lst.head
	} else {
		lst.tail.next = &element[T]{val: v}
		lst.tail = lst.tail.next
	}
}

// Iterator supports iterating over the elements of a Linked List.
type Iterator[T any] struct {
	next **element[T]
}

// Range returns an iterative object
func (lst *List[T]) Range() *Iterator[T] {
	return Iterator[T]{next: &lst.head}
}

// Next moves the iterator to the next meta mutual.
// Return false if it has reached the end.
func (it *Iterator[T]) Next() bool {
	if *it.next == nil {
		return false
	}
	it.next = &(*it.next).next
	return true
}

// Val returns the content of the current element.
// If the element is empty bool value is false.
func (it *Iterator[T]) Val() (T, bool) {
	if *it.next == nil {
		var zero T
		return zero, false
	}
	return (*it.next).val, true
}

// Transform iterates through each element of the linked List, executes function f to get the new element, and saves
// into the new Linked List, and return the new Linked List.
func Transform[T1, T2 any](lst *List[T1], f func(T1) T2) *List[T2] {
	ret := &List[T2]{}
	it := lst.Range()
	for {
		if v, ok := it.Val(); ok {
			ret.Push(f(v))
		}
		if !it.Next() {
			break
		}
	}
	return ret
}

Examples of use are as follows.

l := lists.List[int]{}
l.Push(1)
l.Push(2)

l2 := Transform(l, func(i int) float64 { return float64(i) })
// Now the value of l2 is [1.0, 2.0]

Table of Contents

Slicing Operations

Dictionary Operations

Set Operations

Sorting Operations

Channel operations

Container Definition

Append Functions

Linked List