logo

This course serves as an introduction to generics and iterators, two closely related features of the Go programming language. Generics hold the promise efficient and reusable data structures and functions without sacrificing correctness. As for iterators, which are built on generics, they promote flexibility and performance.

Duration

2 days (14 hours)

Prerequisites

  • Fluency in English
  • Experience with Go and a good understanding of functions, interfaces, and methods
  • A basic knowledge of Git
  • A personal computer (preferably running macOS or Linux) on which the following tools have been installed (ahead of the course):
  • A stable Internet connection

Outline

Day 1: Generics

  • Preamble
    • Generics (a.k.a. parametric polymorphism)
    • Use cases for generics
    • A brief history of the advent of generics in Go
  • Type parameters
    • Syntax
    • Naming conventions
    • Type arguments and instantiation
    • Type inference
  • Generic functions
    • Syntax
    • The slices and maps packages
  • Generic types
    • Syntax
    • Methods of generic types
    • Current restrictions on methods of generic types
  • Generic type aliases
    • Refresher about type aliases
    • Syntax
  • Type constraints
    • A kind of meta-type expressed as interfaces
    • Interfaces viewed as a set of types
    • The predefined any type constraint
    • The predefined comparable type constraint
    • Beware of comparable types composed of values for which equality is non-reflexive
    • Type union
    • Set of types based on a common underlying type (e.g. ~string)
    • The cmp package and the cmp.Ordered type constraint
    • The golang.org/x/exp/constraints package
    • Restrictions on type constraints
    • To constrain or not to constrain: that is the question
  • Advanced techniques
    • Pointer-type constraints
    • Recursive type constraints
    • Phantom types
  • When not to use generics
    • Alternative approaches: reflectionm, code generation
    • A case study of generics abuse
  • Learning resources

Labs:

  • “Generify” a function meant to validate each element of a slice
  • “Générify” a cancelable channel send
  • “Generify” a set data structure
  • “Generify” a function so that it operate either on a string or a slice of bytes
  • “Generify” a binary search tree
  • Redesign a generic binary-search-tree type thanks to a recursive type constraint
  • Redesign a generic binary-search-tree type to free it of type constraints

Day 2: Iterators

  • Preamble
    • What do we mean by “iterator”?
    • Motivations: decoupling, flexibility, performance, security
    • Why did Go take so long to add native support for iterators?
    • Iterators prior to Go 1.23
  • The iter package and the three forms of push iterators
    • iter.Seq: a sequence of values
    • iter.Seq2: a sequence of pairs
    • What about iter.Seq0?
  • Consuming an iterator
    • Loop syntax
    • Consuming an iter.Seq
    • Consuming an iter.Seq2
  • Iterator factories
    • Iterator factory: a function or method that returns an iterator
    • Naming conventions
    • Review of iterator factories in the standard library
    • “Single-use” iterators and other iterators
  • Implementing iterators
    • Purpose and mechanics of the function conventionally named “yield”
    • Implementing an iter.Seq
    • Implementing an iter.Seq2
    • Pitfalls related to the “yield” function
  • Performance considerations
    • Pure and impure iterators
    • Efficient and inefficient implementation of an iterator on a recursive data structure
    • Optimizing an iterator for partial consumption
  • Advanced techniques
    • Iterator combinators
    • Iterator representing a conceptually infinite sequence
    • The pipeline pattern revisited with iterators
  • Pull iterators
    • Push iterators vs. pull iterators
    • Use cases for pull iterators
    • Conversion of a push iterator into a pull iterator
    • Consuming a pull iterator
    • Pitfalls related to pull iterators
  • When not to use iterators
  • Learning resources

Labs:

  • Write and run benchmarks pitting an iterator against a function returning a slice
  • Implement an iterator meant for paginated consumption of a REST API
  • Implement and optimize iterators meant for traversing a generic binary tree
  • Implement an iterator combinator
  • Refactor a pipeline pattern so its steps be connected by iterators rather than by channels
  • Implement an iterator that represents a conceptually infinite sequence
  • Use a pull iterator to check whether two binary trees yield the same elements when traversed in order