Generic Data Structures

The Type Constraints lesson showed that a binding is built in two layers: the operations a constraint allows sit in the declaration, which concrete type those operations will work for is built at the use site. This lesson measures the same two layers over a data structure, but with one difference: a generic function’s type parameter was inferred at the call site, it was never written in the source at all. A generic data structure’s type parameter, by contrast, is written explicitly in the caller’s own declaration — whoever writes Stack[int] places [int] with their own hand, the compiler does not read it from an argument. Same question, two different answers: the binding is still built outside the source (outside the function’s own definition), but this time not by inference, by a declaration the caller writes.

The source of this difference sits in the same place as the difference between a function call and a type declaration. In a function call, arguments already exist — the compiler can look at their type and infer T. In a type declaration, there is no argument yet at all; Stack[int] is not a value, it is a type name, and there is no argument at all for the compiler to infer which type parameter that type name is instantiated with. The compiler needs something to read in order to infer; in a generic function this is the call’s arguments, in a generic type there is no such argument — the caller itself has to write it.

Instantiation Sits in the Caller’s Declaration

A generic data structure is a type declaration that adds a type parameter list right after its name: type Stack[T any] struct{ items []T }. This single source builds a type-safe container pattern usable both for Stack[int] and for Stack[string] — but before it can be used, it first has to be instantiated, and this instantiation is always written in the using side’s own declaration: in a variable definition, a field type, or a return type.

Stack‘s methods do not redefine their own type parameter; the (s *Stack[T]) receiver expression carries the T already opened in the type’s own declaration into the method. Push(v T) and Top() (T, bool) therefore open no new square brackets — the T they use is already bound to int the moment Stack[int] is instantiated, together with Stack itself. Instantiation happens once, in the type’s own declaration; every method bound to that type shares this single instantiation.

// stack.go — the instantiation of a generic data structure sits in the caller's declaration
package main

import "fmt"

type Stack[T any] struct{ items []T }

func (s *Stack[T]) Push(v T) { s.items = append(s.items, v) }

func (s *Stack[T]) Top() (T, bool) {
	var zero T
	if len(s.items) == 0 {
		return zero, false
	}
	return s.items[len(s.items)-1], true
}

func main() {
	var intStack Stack[int]
	intStack.Push(3)
	intStack.Push(5)

	var stringStack Stack[string]
	stringStack.Push("apple")

	i, _ := intStack.Top()
	s, _ := stringStack.Top()

	fmt.Printf("%-24s type=%-16T value=%v\n", "intStack", intStack, i)
	fmt.Printf("%-24s type=%-16T value=%v\n", "stringStack", stringStack, s)
	fmt.Println("arithmetic on the result:", i+1)
}

intStack                 type=main.Stack[int]  value=5
stringStack              type=main.Stack[string] value=apple
arithmetic on the result: 6

GE9. The line var intStack Stack[int] is itself a declaration stating that T will be int — compared with the firstElement([]int{7, 2, 9}) call from the Generic Functions lesson, the difference is plain: there, what T was got inferred from the argument’s type, and nowhere in the source did int ever appear written at all; here, int sits right in the line, visible to the eye. %T confirms this: intStack and stringStack were produced from the same source, but their dynamic types at run time are main.Stack[int] and main.Stack[string] — two entirely separate types, just as [4]int and [3]int are separate types (Arrays and Slices, M09/K01). In the common measurement, this binding counts as one of the declaration examples under the name “instantiation of a generic type.”

It is also worth noting that the line var intStack Stack[int] contains no call at all — this is a zero-value declaration; no New-like constructor is called. As the Zero Values lesson (M09/K01) measured, a struct’s zero value is built from its own fields’ zero values: the items field here starts as a nil slice. This shows the difference between instantiation and being given an initial value: writing Stack[int] binds T, but it does not fill items; the first Push call runs append on a nil slice, and as the Variadic Functions lesson (M09/K01) measured, this works without a problem — appending to a nil slice grows it, it does not panic.

The Measurable Counterpart of Type Safety

The two instantiations being separate types has a consequence: one cannot substitute for the other. The measurement below counts this, and the cost of writing the same job with the empty interface, by asking the compiler.

// safety.go — the measurable counterpart of type safety: how many type assertions are needed
package main

import (
	"fmt"
	"os"
	"os/exec"
	"path/filepath"
)

func compiles(source string) bool {
	dir, err := os.MkdirTemp("", "trial")
	if err != nil {
		return false
	}
	defer os.RemoveAll(dir)
	os.WriteFile(filepath.Join(dir, "go.mod"), []byte("module trial\n\ngo 1.24\n"), 0o644)
	os.WriteFile(filepath.Join(dir, "code.go"), []byte(source), 0o644)
	cmd := exec.Command("go", "build", "./...")
	cmd.Dir = dir
	cmd.Env = append(os.Environ(), "GOTOOLCHAIN=local")
	return cmd.Run() == nil
}

func classifySource(source string) string {
	if compiles(source) {
		return "compiled"
	}
	return "did not compile"
}

func main() {
	substitution := `package trial
type Stack[T any] struct{ items []T }
func F() {
	var a Stack[int]
	var b Stack[string]
	b = a
	_ = b
}`

	anyNoAssertion := `package trial
type AnyStack struct{ items []any }
func (s *AnyStack) Push(v any) { s.items = append(s.items, v) }
func (s *AnyStack) Top() any { return s.items[len(s.items)-1] }
func F() {
	var s AnyStack
	s.Push(3)
	t := s.Top()
	_ = t + 1
}`

	anyWithAssertion := `package trial
type AnyStack struct{ items []any }
func (s *AnyStack) Push(v any) { s.items = append(s.items, v) }
func (s *AnyStack) Top() any { return s.items[len(s.items)-1] }
func F() {
	var s AnyStack
	s.Push(3)
	t, ok := s.Top().(int)
	_ = ok
	_ = t + 1
}`

	genericNoAssertion := `package trial
type Stack[T any] struct{ items []T }
func (s *Stack[T]) Push(v T) { s.items = append(s.items, v) }
func (s *Stack[T]) Top() T { return s.items[len(s.items)-1] }
func F() {
	var s Stack[int]
	s.Push(3)
	t := s.Top()
	_ = t + 1
}`

	fmt.Printf("%-50s %s\n", "case", "result")
	fmt.Printf("%-50s %s\n", "Stack[string] = Stack[int] (substitution)", classifySource(substitution))
	fmt.Printf("%-50s %s\n", "any stack, arithmetic with 0 type assertions", classifySource(anyNoAssertion))
	fmt.Printf("%-50s %s\n", "any stack, arithmetic with 1 type assertion", classifySource(anyWithAssertion))
	fmt.Printf("%-50s %s\n", "generic stack, arithmetic with 0 type assertions", classifySource(genericNoAssertion))
}

case                                               result
Stack[string] = Stack[int] (substitution)          did not compile
any stack, arithmetic with 0 type assertions       did not compile
any stack, arithmetic with 1 type assertion        compiled
generic stack, arithmetic with 0 type assertions   compiled

GE10. The first line directly shows that the two instantiations cannot substitute for each other: b = a does not compile, because Stack[string] and Stack[int] are, to the compiler, as separate as [4]int and [3]int. This is the direct consequence of instantiation sitting in the caller’s declaration — the type written in the declaration becomes part of that variable’s permanent identity.

GE11. The last three lines compare the same job written two ways. AnyStack, written with the empty interface, returns any from Top(); trying to add +1 directly to this value does not compile, because any’s concrete type is not known in the source. The only way out is writing a type assertion (s.Top().(int)) — the same mechanism the Type Assertion and Type Switch lesson measured, appearing here as a burden that has to be written over and over at every read point of a container. The generic Stack[int], by contrast, returns int directly from Top(), and +1 compiles with no type assertion written at all — this is the measurable counterpart of type safety: the number of type assertions needed to do the same job is at least one in the any writing, zero in the generic writing.

This difference compounds as the container grows. Every read point of AnyStack — Top, the return of a Bottom method if one were added, every element of a slice a Contents method might return — has to carry its own type assertion, because the container hides type information behind any, and every reader has to recover this information on its own. In Stack[T], type information is part of the container’s own type; no matter how many new methods are added, none of them ever has to write a type assertion, because their return types are already T — a concrete type known at compile time. A type assertion is not free either: if a value of the wrong type was added (which is possible for an any container with no compile error at all), the assertion either panics at run time or silently fails in its two-value form — in the generic writing this entire class of error never exists at all, because adding an element of the wrong type is already rejected at compilation.

The Limiting Measurement: Comparability Depends on Both the Structure and T

Type safety is not free. Whether a generic type can be compared with == depends not only on the type parameter, but also on the container’s own field structure — and these two factors work independently.

// comparison.go — a generic type's comparability depends on both its own field structure and T
package main

import (
	"fmt"
	"os"
	"os/exec"
	"path/filepath"
)

func compiles(source string) bool {
	dir, err := os.MkdirTemp("", "trial")
	if err != nil {
		return false
	}
	defer os.RemoveAll(dir)
	os.WriteFile(filepath.Join(dir, "go.mod"), []byte("module trial\n\ngo 1.24\n"), 0o644)
	os.WriteFile(filepath.Join(dir, "code.go"), []byte(source), 0o644)
	cmd := exec.Command("go", "build", "./...")
	cmd.Dir = dir
	cmd.Env = append(os.Environ(), "GOTOOLCHAIN=local")
	return cmd.Run() == nil
}

func classifySource(source string) string {
	if compiles(source) {
		return "compiled"
	}
	return "did not compile"
}

func main() {
	stackWithSlice := `package trial
type Stack[T any] struct{ items []T }
func F() bool { var a, b Stack[int]; return a == b }`

	boxComparableT := `package trial
type Box[T any] struct{ Value T }
func F() bool { var a, b Box[int]; return a == b }`

	boxIncomparableT := `package trial
type Box[T any] struct{ Value T }
func F() bool { var a, b Box[[]string]; return a == b }`

	fmt.Printf("%-48s %s\n", "case", "result")
	fmt.Printf("%-48s %s\n", "Stack[int] == Stack[int] (slice field)", classifySource(stackWithSlice))
	fmt.Printf("%-48s %s\n", "Box[int] == Box[int] (T direct, T=int)", classifySource(boxComparableT))
	fmt.Printf("%-48s %s\n", "Box[[]string] == Box[[]string] (T=slice)", classifySource(boxIncomparableT))
}

case                                             result
Stack[int] == Stack[int] (slice field)           did not compile
Box[int] == Box[int] (T direct, T=int)           compiled
Box[[]string] == Box[[]string] (T=slice)         did not compile

GE12. The three lines separate two independent factors. Stack[T] can never be compared — even when T is int — because items is a slice field, and as the Maps and Arrays and Slices lessons (M09/K01) measured, slices cannot be compared with ==; this restriction comes from the container’s own field structure, not from the type parameter. Box[T] builds a different structure — its Value field holds T directly, not a slice — and here comparability is handed entirely over to T: Box[int] is comparable because int is comparable, Box[[]string] is not comparable because this time T itself ([]string) is a type that cannot be compared. A generic type’s comparability therefore cannot be reduced to a single question; it requires looking at both the container’s own design and the T it is filled with.

This also shows why constraints are not enough on their own: turning the Stack[T any] constraint into Stack[T comparable] would work for Box, but changes nothing at all for Stack — however comparable T is, as long as items is a slice, Stack remains uncomparable. A type constraint bounds only T, not the field layout of the type carrying T.

This distinction has a concrete counterpart: the Maps lesson (M09/K01) measured that a map’s key type must be comparable. Stack[int] can never be a map key — no matter what T is — because the incomparability comes from the items field, and this field stays exactly as it is at every instantiation. Box[int], on the other hand, can be a key, because its Value field holds int directly, and int is comparable; Box[[]string] cannot, because this time the T it carries is itself incomparable. The same two container patterns answer, in advance, the question “can this type be a map key” just by looking at the field structure in the source — with no need at all to try a key at run time.

Across three lessons, genericity stayed inside the source the whole time: the type parameter was either inferred or written explicitly, but in both cases, someone reading the source, looking in the right place, could see which concrete type was being used. This is the exact opposite posture of the implicit satisfaction the Interface Concept lesson measured: there, a type satisfying an interface was never written anywhere at all; here, which type a container works with can always be read either from the call’s argument or from the declaration’s square brackets. Stack[int]‘s dynamic type can be known without ever asking %T at all, because it is written right in the source itself; an interface value’s dynamic type, by contrast, could only be learned by asking the value. The course’s closing lesson places these two postures — always readable versus learnable only by asking the value — side by side by doing the same job.

This readability is not free: someone reading Stack[int] learns that T is int from the line itself, but this information cannot be inferred anywhere else — like from an argument, as in the Generic Functions lesson; it is not possible for the writer to forget to write it, because the syntax makes it mandatory. The predictability genericity gives comes with this small writing burden the caller takes on.

Summary

• A generic data structure’s type parameter, unlike a generic function’s, is written explicitly in the caller’s own declaration — it is never inferred.
• Stack[int] and Stack[string], even though produced from the same source, are two separate dynamic types read at run time with %T, and one cannot substitute for the other.
• The measurable counterpart of type safety: writing the same job with the empty interface requires at least one type assertion, in the generic writing this count is zero.
• A generic type’s comparability depends on two independent factors: the container’s own field structure (if it carries a slice field, it can never be compared) and — if the container holds T directly — T’s own comparability.
• A type constraint bounds only the type parameter; it cannot change the limits coming from the container’s own field layout.

Next Step

Across three lessons, genericity was always measured on one side: the binding was built either in the declaration or at the use site, and it never entered the value. The interface topic measured the exact opposite — type information was carried inside the value and could only be read by asking the value. The course’s final lesson places these two writings, and the interface contract standing between them, side by side by doing the same job three times: how many type assertions each writing requires, which one stays at compile time and which one falls to run time, and whether genericity always wins.