Hi Gophers, so for my first post, I’ll do a short introduction to go version 1.23.0 iterators and some examples including how to create recursive iterators.

What is an iterator?

An iterator allows you to loop through a collection of objects. This collection can be anything, a slice, a map, any data structure, even an infinite sequence (like the Fibonacci Sequence) etc.

How is this implemented in Go?

Go provides the iterator construct in the new iter package.

`iter` Package

The iter package defines 4 new types. Let’s go through them one by one.

`Seq` type

type Seq[V any] func(yield func(V) bool)

The Seq (pronounced Seek) type is responsible for returning a single value.

The yield function here, is responsible for pausing the iterator at some value passing the control flow back to the calling loop. The iterator picks up from this paused point whenever it’s called next.

Consider the implementation of a binarytree package. Let’s say we want to give the users an option to traverse the tree in a in-order fashion.

// binarytree.go

type Node[T any] struct {
	Left  *Node[T]
	Right *Node[T]
	Val   T
}

func NewNode[T any](t T) *Node[T] {
	return &Node[T]{
		Left:  nil,
		Right: nil,
		Val:   t,
	}
}

func (n *Node[T]) InOrder() iter.Seq[T] {
	return func(yield func(T) bool) {
		var rec func(*Node[T])
		rec = func(n *Node[T]) {
			if n == nil {
				return
			}

			rec(n.Left)

			if !yield(n.Val) {
				return
			}

			rec(n.Right)
		}
		rec(n)
	}
}

We can now use this iterator directly using a for-range loop.

// main.go

func main() {
	root := NewNode(1)
	root.Left = NewNode(2)
	root.Left.Left = NewNode(4)
	root.Right = NewNode(3)
	root.Right.Right = NewNode(5)

	for k := range root.InOrder() {
		fmt.Println(k)
	}
}

The response here is as expected:

Why does the yield function return a `bool` ?

The yield function will return false to the iterator whenever the iterator should stop returning a value. In other words, it might be triggered in cases where the loop exits early due to a break statement.

The iterator is responsible for any cleanup that may be required after yield returns false.

When does the iteration stop?

The iteration stops whenever the iterator function returns.

`Seq2` type

type Seq2[K, V any] func(yield func(K, V) bool)

The Seq2 (pronounced Seek2) is responsible for returning Key-Value pairs with the same semantics as Seq.

Notable example of Seq2 are the new map.All() and slices.All() functions which return this iterator.

`Pull` function

func Pull[V any](seq Seq[V]) (next func() (V, bool), stop func())

What if we want to use the iterators outside of a for-range loop construct?

That’s what the Pull function is for. It can change the semantics of using the iterators by providing a next() and stop() function.

This is opposite to the Push style Seq iterator, which pushes the value to the yield function.

func main() {
	root := NewNode(1)
	root.Left = NewNode(2)
	root.Left.Left = NewNode(4)
	root.Right = NewNode(3)
	root.Right.Right = NewNode(5)

	next, stop := iter.Pull(root.InOrder())

	for {
		defer stop()
		val, ok := next()
		if !ok {
			break
		}
		fmt.Println(val)
	}
}

The stop function needs to be called by the consumer similar to closing a io.Reader. It is equivalent to the yield function returning false to the iterator.

The next function returns false for stopped iterators.

`Pull2` type

func Pull2[K, V any](seq Seq2[K, V]) (next func() (K, V, bool), stop func())

This is the Pull function for Seq2 objects with the exact same semantics.

Package Changes

Both the maps and slices package have been added to provide support for iterators.

slices

`slices.All` : Returns all index-value pairs from slice

arr := []string{"a", "b", "c", "d", "e"}
for i, v := range slices.All(arr) {
  fmt.Println(i, v)
}
// 0 a
// 1 b
// ...

`slices.Values` : Returns all values of slice

arr := []string{"a", "b", "c", "d", "e"}
for v := range slices.Values(arr) {
  fmt.Println(v)
}
// a
// b
// ...

`slices.Backward` : Returns all index-value of slice in reverse order

arr := []string{"a", "b", "c", "d", "e"}
for i, v := range slices.Backward(arr) {
  fmt.Println(i, v)
}
// 4 e
// 3 d
// ...

`slices.Collect` : Collects all values from a `Seq` iter to a slice

arr := []string{"a", "b", "c", "d", "e"}
arrCopy := slices.Collect(slices.Values(arr))
// arrCopy = []string{"a", "b", "c", "d", "e"}

`slices.AppendSeq` : Appends all values from a `Seq` iter to a slice

arr := []string{"a", "b", "c", "d", "e"}
arr2 := []string{"1", "2", "3"}
slices.AppendSeq(arr, slices.Values(arr2))

You can find the rest of this list in the release notes.

FAQs

Are Iterators Goroutine Safe?

No, iterators are not supposed to be goroutine safe.

How to mutate data using iterators?

Since iterators don’t directly provide a mechanism to update the underlying values, one of the ways of achieving this would be to use a Mutator / Position objects.

These object can point to the underlying objects and change their values.

type NodePosition[T any] struct {
  node *Node[T]
}

func (n *NodePosition) SetVal(t T) {
  n.node.Val = t
}

We can then make iterators for these NodePosition objects.

That’s it for now.

Go Iterators

What is an iterator?

How is this implemented in Go?

iter Package

Seq type

Why does the yield function return a bool ?

When does the iteration stop?

Seq2 type

Pull function

Pull2 type