Code from my blog post "Writing type parametric functions in Go."

01-possible-generic-map.go

// This is *not* valid Go!

func Map(f func(A) B, xs []A) []B {
    ys := make([]B, len(xs))
    for i, x := range xs {
        ys[i] = f(x)
    }
    return ys
}
Map(func(x int) int { return x * x }, []int{1, 2, 3})
// Returns: [1, 4, 9]

02-no-reflection.go

package main

import "fmt"

func Map(f func(interface{}) interface{}, xs []interface{}) []interface{} {
	ys := make([]interface{}, len(xs))
	for i, x := range xs {
		ys[i] = f(x)
	}
	return ys
}

func main() {
	square := func(x interface{}) interface{} {
		return x.(int) * x.(int)
	}
	nums := []int{1, 2, 3, 4}

	gnums := make([]interface{}, len(nums))
	for i, x := range nums {
		gnums[i] = x
	}
	gsquared := Map(square, gnums)
	squared := make([]int, len(gsquared))
	for i, x := range gsquared {
		squared[i] = x.(int)
	}
	fmt.Printf("%v\n", squared)

	// Run time type safety is questionable.
	// Map(func(a interface{}) interface{} { return len(a.(string)) },
		// []interface{}{1, 2, 3})
}

03-reflection-in-1.0.x.go

package main

import (
	"fmt"
	"reflect"
)

func Map(f interface{}, xs interface{}) []interface{} {
	vf := reflect.ValueOf(f)
	vxs := reflect.ValueOf(xs)
	ys := make([]interface{}, vxs.Len())

	for i := 0; i < vxs.Len(); i++ {
		ys[i] = vf.Call([]reflect.Value{vxs.Index(i)})[0].Interface()
	}
	return ys
}

func main() {
	square := func(x int) int {
		return x * x
	}
	nums := []int{1, 2, 3, 4}

	gsquared := Map(square, nums)
	squared := make([]int, len(gsquared))
	for i, x := range gsquared {
		squared[i] = x.(int)
	}
	fmt.Printf("%v\n", squared)

	// Run time type safety is still questionable.
	// Map(func(a string) int { return len(a) }, []int{1, 2, 3}) 
}

04-reflection-in-1.1.x.go

package main

import (
	"fmt"
	"reflect"
)

func Map(f interface{}, xs interface{}) interface{} {
	vf := reflect.ValueOf(f)
	vxs := reflect.ValueOf(xs)

	tys := reflect.SliceOf(vf.Type().Out(0))
	vys := reflect.MakeSlice(tys, vxs.Len(), vxs.Len())

	for i := 0; i < vxs.Len(); i++ {
		y := vf.Call([]reflect.Value{vxs.Index(i)})[0]
		vys.Index(i).Set(y)
	}
	return vys.Interface()
}

func main() {
	squared := Map(func(x int) int { return x * x }, []int{1, 2, 3}).([]int)
	fmt.Printf("%v\n", squared)

	// Run time type safety is *still* questionable.
	// _ = Map(func(a string) int { return len(a) }, []int{1, 2, 3}).([]int) 
}

05-run-time-type-safety.go

package main

import (
	"fmt"
	"log"
	"reflect"
)

func Map(f interface{}, xs interface{}) interface{} {
	vf := reflect.ValueOf(f)
	vxs := reflect.ValueOf(xs)

	ftype := vf.Type()
	xstype := vxs.Type()

	// 1) Map's first parameter type must be `func(A) B`
	if ftype.Kind() != reflect.Func {
		log.Panicf("`f` should be %s but got %s", reflect.Func, ftype.Kind())
	}
	if ftype.NumIn() != 1 {
		log.Panicf("`f` should have 1 parameter but it has %d parameters",
			ftype.NumIn())
	}
	if ftype.NumOut() != 1 {
		log.Panicf("`f` should return 1 value but it returns %d values",
			ftype.NumOut())
	}

	// 2) Map's second parameter type must be `[]A1` where `A == A1`.
	if xstype.Kind() != reflect.Slice {
		log.Panicf("`xs` should be %s but got %s", reflect.Slice, xstype.Kind())
	}
	if xstype.Elem() != ftype.In(0) {
		log.Panicf("type of `f`'s parameter should be %s but xs contains %s",
			ftype.In(0), xstype.Elem())
	}

	// 3) Map's return type must be `[]B1` where `B == B1`.
	tys := reflect.SliceOf(vf.Type().Out(0))

	vys := reflect.MakeSlice(tys, vxs.Len(), vxs.Len())
	for i := 0; i < vxs.Len(); i++ {
		y := vf.Call([]reflect.Value{vxs.Index(i)})[0]
		vys.Index(i).Set(y)
	}
	return vys.Interface()
}

func main() {
	squared := Map(func(x int) int { return x * x }, []int{1, 2, 3}).([]int)
	fmt.Printf("%v\n", squared)

	// Run time type safety is *still* questionable.
	_ = Map(func(a string) int { return len(a) }, []int{1, 2, 3}).([]int)
	// _ = Map(5, []int{1, 2, 3}).([]int)
}

06-ty-check-map.go

package main

import (
	"fmt"
	"reflect"

	"github.com/BurntSushi/ty"
)

// Map has a parametric type:
//
//	func Map(f func(A) B, xs []A) []B
//
// Map returns the list corresponding to the return value of applying
// `f` to each element in `xs`.
func Map(f, xs interface{}) interface{} {
	chk := ty.Check(
		new(func(func(ty.A) ty.B, []ty.A) []ty.B),
		f, xs)
	vf, vxs, tys := chk.Args[0], chk.Args[1], chk.Returns[0]

	xsLen := vxs.Len()
	vys := reflect.MakeSlice(tys, xsLen, xsLen)
	for i := 0; i < xsLen; i++ {
		vy := vf.Call([]reflect.Value{vxs.Index(i)})[0]
		vys.Index(i).Set(vy)
	}
	return vys.Interface()
}

func main() {
	squared := Map(func(x int) int { return x * x }, []int{1, 2, 3}).([]int)
	fmt.Printf("%v\n", squared)

	_ = Map(func(a string) int { return len(a) }, []int{1, 2, 3}).([]int)
}

07-shuffle.go

package main

import (
	"fmt"
	"math/rand"
	"reflect"
	"time"

	"github.com/BurntSushi/ty"
)

// Shuffle has a parametric type:
//
//	func Shuffle(xs []A)
//
// Shuffle shuffles `xs` in place using a default random number
// generator.
func Shuffle(xs interface{}) {
	chk := ty.Check(
		new(func([]ty.A)),
		xs)
	vxs := chk.Args[0]

	// Used for swapping in the loop.
	// Equivalent to `var tmp A`.
	tmp := reflect.New(vxs.Type().Elem()).Elem()

	// Implements the Fisher-Yates shuffle: http://goo.gl/Hb9vg
	for i := vxs.Len() - 1; i >= 1; i-- {
		j := rand.Intn(i + 1)

		// Swapping is a bit painful.
		tmp.Set(vxs.Index(i))
		vxs.Index(i).Set(vxs.Index(j))
		vxs.Index(j).Set(tmp)
	}
}

func main() {
	rand.Seed(time.Now().UnixNano())

	words := []string{
		"the", "quick", "brown", "fox",
		"jumps", "over", "the", "lazy", "dog",
	}
	Shuffle(words)
	fmt.Printf("%v\n", words)
}

08-set-union.go

package main

import (
	"fmt"
	"reflect"

	"github.com/BurntSushi/ty"
)

// Union has a parametric type:
//
//	func Union(a map[A]bool, b map[A]bool) map[A]bool
//
// Union returns the union of two sets, where a set is represented as a
// `map[A]bool`. The sets `a` and `b` are not modified.
func Union(a, b interface{}) interface{} {
	chk := ty.Check(
		new(func(map[ty.A]bool, map[ty.A]bool) map[ty.A]bool),
		a, b)
	va, vb, tc := chk.Args[0], chk.Args[1], chk.Returns[0]

	vtrue := reflect.ValueOf(true)
	vc := reflect.MakeMap(tc)
	for _, vkey := range va.MapKeys() {
		vc.SetMapIndex(vkey, vtrue)
	}
	for _, vkey := range vb.MapKeys() {
		vc.SetMapIndex(vkey, vtrue)
	}
	return vc.Interface()
}

func main() {
	A := map[string]bool{
		"springsteen": true,
		"j. geils": true,
		"seger": true,
	}
	B := map[string]bool{
		"petty": true,
		"seger": true,
	}
	AandB := Union(A, B).(map[string]bool)

	fmt.Printf("%v\n", AandB)
}

09-func-memo.go

package main

import (
	"fmt"

	"github.com/BurntSushi/ty/fun"
)

func main() {
	// Memoizing a recursive function like `fibonacci`:
	// Write it like normal but with a type assert.
	var fib func(n int64) int64
	fib = func(n int64) int64 {
		switch n {
		case 0:
			return 0
		case 1:
			return 1
		}
		return fib(n-1) + fib(n-2)
	}

	// Wrap it with a memoizing function.
	// The type assert here is the *only* burden on the caller.
	fib = fun.Memo(fib).(func(int64) int64)

	// Will keep your CPU busy for a long time
	// without memoization.
	fmt.Println(fib(80))
}