Day 024 — Generic Data Structures: Stack & Set

Month 1 · Week 4 · ⬅ Day 023 · Day 025 ➡ · Journal index

🎯 Learning Objective

Implement reusable, type-safe container types — a Stack[T any] and a Set[T comparable] — and reason about their zero values, receivers, and method sets.

📚 Topics

• Generic types: type Stack[T any] struct{ items []T }
• The right constraint per container (any for a stack, comparable for a set)
• Comma-ok methods, returning the zero value of T
• Pointer receivers for mutation · constructor functions

📖 Reading / Sources

• Go blog — When To Use Generics
• pkg.go.dev/slices and pkg.go.dev/maps (stdlib generic helpers, Go 1.21+)
• Re-read [[Day 023]] notes on constraints

📝 Notes

• A generic type lists its type parameters once on the type; methods then refer to them without re-declaring constraints: func (s *Stack[T]) Push(v T). The receiver carries [T].
• A stack only stores/returns values → T any is enough. Build on a slice; Push is append, Pop reslices s.items[:n-1]. Connects to [[slice-internals]] (watch capacity, but for a stack we never alias the popped tail).
• Pop/Peek use the comma-ok idiom and must return var zero T on empty — you can't return a typed nil/0 literal generically. Links to [[zero-values]].
• A set needs map keys, so its element type must be comparable: type Set[T comparable] struct{ m map[T]struct{} }. The struct{} value uses zero bytes — the idiomatic set. Connects to [[maps-sets]].
• Use pointer receivers so mutation (Push, Add, Remove) persists, and keep all receivers pointers for consistency (same rule as [[methods]]).
• Provide a constructor (NewSet[T]()) that allocates the inner map — a Set with a nil map can read (Contains is false) but panics on Add (write to nil map), the classic nil-map trap from [[maps-sets]].
• Set algebra (Union, Intersect, Difference) returns a new set, leaving operands untouched — easier to reason about and test.
• The stdlib now ships generic helpers: slices.Contains, slices.Index, slices.Sort, maps.Keys/maps.Values (iterators, Go 1.23). Don't reinvent these in real code; we build our own here to learn.

💻 Code Examples

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

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

func (s *Stack[T]) Pop() (T, bool) {
    var zero T // generic zero value — works for any T
    if len(s.items) == 0 {
        return zero, false
    }
    last := len(s.items) - 1
    v := s.items[last]
    s.items[last] = zero      // avoid retaining a reference (GC hygiene)
    s.items = s.items[:last]
    return v, true
}

func (s *Stack[T]) Len() int { return len(s.items) }

Full code: examples/month-01/generic-ds/main.go · Run: go run ./examples/month-01/generic-ds

🏋️ Exercises / Practice

Exercise	Status	Link
Generic Stack[T] with comma-ok Pop/Peek	✅	exercises/month-01/week-4/genstack
Generic Set[T] with Union/Intersect/Difference	✅	exercises/month-01/week-4/genset

🐛 Mistakes Made

• Declared type Set[T any] then used T as a map key → compile error: map keys must be comparable. Changed the constraint to comparable.
• Returned nil, false from a generic Pop → won't compile for non-nilable T. Used var zero T instead.
• Forgot to allocate the map in the constructor; first Add panicked with "assignment to entry in nil map".

❓ Open Questions

• Should Set methods take/return *Set[T] or value Set[T]? (Went with pointer for mutators; set-algebra returns a fresh *Set[T].)

🧠 Active Recall (answer without looking)

1. Q: Why must a generic Set's element type be comparable but a Stack's only any?
   

   A

   A set stores elements as **map keys**, and map keys must support `==`/`!=` → `comparable`. A stack only stores and returns values in order, never compares them, so `any` suffices.

2. Q: How do you return "no value" from a generic Pop() (T, bool)?
   

   A

   Declare `var zero T` and return `zero, false`. You can't write `nil`/`0` because `T` might be any type; the zero value is the only universally valid "empty".

🪶 Feynman Reflection

A generic container is a blueprint: I describe how a stack or set works once, and the compiler builds a concrete, type-checked Stack[int], Stack[string], Set[User], etc. The constraint picks how much the element type must "promise" — any for a pure box, comparable when I need it as a map key.

🕳️ Knowledge Gaps

• Iterator support (iter.Seq, range-over-func, Go 1.23) for these containers — note for Month 2.

✅ Summary

I built type-safe Stack[T] and Set[T] containers, chose constraints deliberately, handled empty cases with generic zero values, and used pointer receivers + constructors to dodge the nil-map trap.

⏭️ Next Steps / Prep for Tomorrow

• Day 025: start the Week-4 capstone — a task CLI: domain model + JSON file storage.

---

Time spent	Difficulty	Confidence
90 min	🟦🟦⬜⬜⬜	🟦🟦🟦🟦⬜

Suggested commit: feat(examples): generic stack and set data structures (day 024)