ComposableTypes.md

Composable Types

This proposal describes a new composable type system for Go. It follows the design ideas of the already built-in composable types map and chan and should be understood as an alternative way to implement basic generic data structures.

The following is an example of a queue implemented as a composable type (boring code has been removed):

func main() {
	// compose a queue of integers
	q := comp[int]Queue{}
	
	// reset queue
	q.Reset(size)

	// push items
	q.Push(1)
	q.Push(2)

	// pop first item
	q.Pop()
	// => int(1)
	
	// pop second item
	q.Pop()
	// => int(2)
}

// ---

// Queue is a composable FIFO queue.
type Queue comp Item struct {
	items []Item
	// ...
}

// Reset will reset the queue
func (q *Queue) Reset(capacity int) {
	q.items = make([]Item, 0, capacity)
	// ...
}

// Push will add an item to the queue.
func (q *Queue) Push(item Item) {
	// ...
}

// Pop will get an item of the queue.
func (q *Queue) Pop() Item {
	// ...
}

Details

A composable types is declared by adding the comp keyword and at least one generic type in a struct type declaration:

// A composable type with a single generic type.
type Queue comp Item struct {}

// A composable type with three generic types.
type Foo comp Bar Baz Qux struct {}

The generic types can be used in the struct definition to define properties:

type Foo comp Bar struct {
	bar []Bar
}

And in method declarations as parameters, arguments and variables:

func (s *Foo) Add(bar Bar) Bar {
	var b Bar
}

The composable type can then be constructed when needed using the comp keyword:

// compose a queue of ints
queue := comp[int]Queue

// compose a set of strings
set := comp[string]Set

// compose a type with multiple generic types
foo := comp[int,string]Foo

Composable types are designed to be used for allowing code reuse when implementing generic data structures as for example queues, stacks etc. A good example is the sync.Map that currently uses interface{} for keys and values. With composable types the key and value types could be checked on compile time and allow catching errors early.

Notes

• Similar to maps comp[int]Queue is in itself already a pointer and thus can be safely shared.
• Once the compiler sees a composition it compiles it and reports errors if the supplied types are not compatible with the implementation (functions as map keys and similar).

A) I have always liked the syntax

type Item generic
type Queue struct { items []Item }

B) AFAICT, this doesn’t allow writing eg max(a, b), which seems to be a desired outcome for the Go team.