## 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.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 `````` ``````// 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.

 `````` 1 2 3 4 5 6 7 8 9 10 `````` ``````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.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 `````` ``````// 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.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 `````` ``````// 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.

 `````` 1 2 3 4 5 6 7 8 9 10 `````` ``````// 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.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 `````` ``````// 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.

 ``````1 2 3 4 5 6 7 `````` ``````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.

 `````` 1 2 3 4 5 6 7 8 9 10 11 `````` ``````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.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 `````` ``````// 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.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 `````` ``````// 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.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 `````` ``````// 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.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 `````` ``````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.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 `````` ``````// 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) ``````

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 `````` ``````// 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 } ``````
 ``````1 2 3 4 5 6 `````` ``````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] ``````