Go 1.18 generics

What you will learn from this topic

• A summary of the release note of go 1.18 generics with source code
• More example that didn't provide within official pages

How to install

$ go install golang.org/dl/go1.18rc1@latest
$ go1.18rc1 download

$ go1.18rc1 
Go is a tool for managing Go source code.
Usage:
	go <command> [arguments]
...

Generics are not 100% generic

constraints

• Any
  • Define with language level
  • IT IS INTERFACE{}
  • PR is here https://github.com/golang/go/issues/33232
• Compareable
  • Define with language level
  • follow the defination of https://go.dev/ref/spec#Comparison_operators
    • ==
    • !=
• Ordered
  • Define with constraints package
    • < less
    • <= less or equal
    • > greater
    • >= greater or equal

e.g, interface are not Ordered but Compareable.

// Copyright 2021 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package constraints defines a set of useful constraints to be used
// with type parameters.
package constraints

// Signed is a constraint that permits any signed integer type.
// If future releases of Go add new predeclared signed integer types,
// this constraint will be modified to include them.
type Signed interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64
}

// Unsigned is a constraint that permits any unsigned integer type.
// If future releases of Go add new predeclared unsigned integer types,
// this constraint will be modified to include them.
type Unsigned interface {
	~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}

// Integer is a constraint that permits any integer type.
// If future releases of Go add new predeclared integer types,
// this constraint will be modified to include them.
type Integer interface {
	Signed | Unsigned
}

// Float is a constraint that permits any floating-point type.
// If future releases of Go add new predeclared floating-point types,
// this constraint will be modified to include them.
type Float interface {
	~float32 | ~float64
}

// Complex is a constraint that permits any complex numeric type.
// If future releases of Go add new predeclared complex numeric types,
// this constraint will be modified to include them.
type Complex interface {
	~complex64 | ~complex128
}

// Ordered is a constraint that permits any ordered type: any type
// that supports the operators < <= >= >.
// If future releases of Go add new ordered types,
// this constraint will be modified to include them.
type Ordered interface {
	Integer | Float | ~string
}

Reference: https://cs.opensource.google/go/x/exp/+/bbda1eaf:constraints/constraints.go

What can we do?

return max value

package main

import "fmt"
import "golang.org/x/exp/constraints"

func Max[Elem constraints.Ordered](a Elem, b Elem) Elem {
    if a >= b {
        return a
    }
    return b
}

func main() {
    fmt.Println(Max(1, 2))
	fmt.Println(Max(2.2, 1.1))
}
//go1.18rc1 run main.go
//2
//2.2

Insert multiple value into slice

package main

import "fmt"

func Insert[S ~[]E, E any](s S, i int, v ...E) S {
	s2 := make(S, len(s) + len(v))
	copy(s2, s[:i])
	copy(s2[i:], v)
	copy(s2[i+len(v):], s[i:])
	return s2
}

func main() {
	s1 := []int{1, 2, 3, 4}
	s2 := Insert(s1, 1, 5, 6, 7)
	fmt.Println(s2)
}

// go1.18rc1 run main.go
// [1 5 6 7 2 3 4]

package main

import "fmt"

func Insert[S ~[]E, E interface{}](s S, i int, v ...E) S {
	s2 := make(S, len(s)+len(v))
	copy(s2, s[:i])
	copy(s2[i:], v)
	copy(s2[i+len(v):], s[i:])
	return s2
}

func main() {
	s1 := []int{1, 2, 3, 4}
	s2 := Insert(s1, 1, 5, 6, 7)
	fmt.Println(s2)
}

BinarySearch

func BinarySearch[Elem constraints.Ordered](x []Elem, target Elem) int {
  return search(len(x), func(i int) bool { return x[i] >= target })
}

func search(n int, f func(int) bool) int {
  // Define f(-1) == false and f(n) == true.
  // Invariant: f(i-1) == false, f(j) == true.
  i, j := 0, n
  for i < j {
    h := int(uint(i+j) >> 1) // avoid overflow when computing h
    // i ≤ h < j
    if !f(h) {
      i = h + 1 // preserves f(i-1) == false
    } else {
      j = h // preserves f(j) == true
    }
  }
  // i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
  return i
}

Sort

package main

import "fmt"
import "golang.org/x/exp/constraints"

func Sort[Elem constraints.Ordered](x []Elem, f func(a, b Elem) bool) {
	n := len(x)
	sortFunction(x, 0, n, f)
}

// insertionSortLessFunc sorts data[a:b] using insertion sort.
func sortFunction[Elem any](data []Elem, a, b int, less func(a, b Elem) bool) {
	for i := a + 1; i < b; i++ {
		for j := i; j > a && less(data[j], data[j-1]); j-- {
			data[j], data[j-1] = data[j-1], data[j]
		}
	}
}

func comp(a int64, b int64) bool {
	if a <= b {
		return true
	}
	return false
}

func main() {
	s1 := []int64{1, 9, 5, 2}
	fmt.Println(s1)
	Sort(s1, comp)
	fmt.Println(s1)
}
//go1.18rc1 run main.go
//[1 9 5 2]
//[1 2 5 9]

Can interface do the samething?

Yes, just a little uglier and more complicated

And not type safe

Insert multiple value into slice

package main

import "fmt"

func Insert(s []interface{}, i int, v ...interface{}) []interface{} {
	s2 := make([]interface{}, len(s)+len(v))
	copy(s2, s[:i])
	copy(s2[i:], v)
	copy(s2[i+len(v):], s[i:])
	return s2
}

func main() {
	s := []int{1, 2, 3, 4}
	s1 := make([]interface{}, len(s), len(s))
	for i := range s {
		s1[i] = s[i]
	}
	s2 := Insert(s1, 1, 5, 6, 7)
	fmt.Println(s2)
}

// output [1 5 6 7 2 3 4]

Seems works?
Let's try to use this function like this

func main() {
	s := []int{1, 2, 3, 4}
	s1 := make([]interface{}, len(s), len(s))
	for i := range s {
		s1[i] = s[i]
	}
    
    s2 := Insert(s1, 1, 5, 0.0, []int{1,2,3})
	fmt.Println(s2)
    
    s3 := make([]int, len(s2))
    for i := range s2 {
        s3[i] = s2[i].(int)
	}
}
//go run main.go
//
//panic: interface conversion: interface {} is float64, not int
//goroutine 1 [running]:
//main.main()
//        /Users/rance/go/src/github.com/rancejen/generic_test/main.go:22 +0x388
//exit status 2

How about generic?

$ go1.18rc1 run main.go

# command-line-arguments
./main.go:15:14: []int does not implement [][]int
./main.go:15:22: cannot use 5 (untyped int constant) as []int value in argument to Insert
./main.go:15:25: cannot use 6 (untyped int constant) as []int value in argument to Insert
./main.go:15:28: cannot use 7 (untyped int constant) as []int value in argument to Insert

It can detect problem in compile time

binary search

package main

import (
	"fmt"
)

func BinarySearch(x []interface{}, f func(int) bool) int {
	return search(len(x), f)
}

func search(n int, f func(int) bool) int {
	// Define f(-1) == false and f(n) == true.
	// Invariant: f(i-1) == false, f(j) == true.
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1) // avoid overflow when computing h
		// i ≤ h < j
		if !f(h) {
			i = h + 1 // preserves f(i-1) == false
		} else {
			j = h // preserves f(j) == true
		}
	}
	// i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
	return i
}

func main() {
	s := []int{1, 3, 5, 7, 9, 11}
	s1 := make([]interface{}, len(s), len(s))
	for i := range s {
		s1[i] = s[i]
	}
	fmt.Println(BinarySearch(s1, func(i int) bool { return s1[i].(int) >= 11 }))
}
// go run main.go
// [1 5 6 7 2 3 4]

Limitation

reference https://tip.golang.org/doc/go1.18#generics

1. The Go compiler cannot currently handle type declarations inside generic functions or methods. We hope to provide support for this feature in Go 1.19.

func Max[Elem constraints.Ordered](a Elem, b Elem) Elem {
	type c int
	if a >= b {
		return a
	}
	return b
}
//go1.18rc1 run main.go
//./main.go:7:2: type declarations inside generic functions are not currently supported

2. The Go compiler currently does not accept arguments of type parameter type with the predeclared functions real, imag, and complex. We hope to remove this restriction in Go 1.19.
   I can't get it.
3. The Go compiler currently only supports calling a method m on a value x of type parameter type P if m is explicitly declared by P's constraint interface. Similarly, method values x.m and method expressions P.m also are only supported if m is explicitly declared by P, even though m might be in the method set of P by virtue of the fact that all types in P implement m. We hope to remove this restriction in Go 1.19.
4. Embedding a type parameter, or a pointer to a type parameter, as an unnamed field in a struct type is not permitted. Similarly, embedding a type parameter in an interface type is not permitted. Whether these will ever be permitted is unclear at present.
5. A union element with more than one term may not contain an interface type with a non-empty method set. Whether this will ever be permitted is unclear at present.

This doesn't work

type vector struct {
    values []any
}

func main {
    v := vector{[]int{1,2,3}}
}