A look at iterators in Go

🎅🏻 This post is part of the Eureka Advent Calendar 2023 🎅🏻

Introduction

Extensions to the for-range statement for both ints (range-over-int) and iterator functions (range-over-func) appeared in Go 1.22, and discussion regarding an iterator library and coroutines is also ongoing.

This post takes a look at the motivation for iterators in Go, and the current state of the related proposals and implementations.

As of 7th Feb 2024, the status for each feature is as below [0][1][2].

• range-over-int: released in 1.22
• range-over-func: added behind GOEXPERIMENT=rangefunc in Go 1.22 (continued revisions expected)
• iterator library: currently trying to reach consensus on spec
• coroutines: added internally but not yet released (no external API decided yet)

If you want to try out the code samples yourself, check out the below repository. Setup instructions are included in the README.

GitHub - Jimeux/iter: Go iterators

Why iterators?

The Go team is very conservative about adding new features to the language, even those taken for granted in other “modern” languages. So what makes iterators different?

The need for consistency

For-range loops can be used to iterate over certain built-in types, but other types aren’t so intuitive. bufio introduces multiple iteration patterns.

// bufio.Reader
r := bufio.NewReader(...)
for {
    line, _ , err := r.ReadLine()
    if err != nil {
        break
    }
    // do something
}


// bufio.Scanner
scanner := bufio.NewScanner(...)
for scanner.Scan() {
    line := scanner.Text()
    // do something
}

Building on generics

Generics allow for the definition of custom container types, but there are no guidelines for iteration. Can we say the below API is idiomatic or not?

tree := radix.NewTree[int]()
for ptr := tree.Traverse(); ptr.HasNext(); ptr = ptr.Next() {
    // do something
}

Reusability, composition and performance

Writing loops on the fly to filter or transform data in container types is common in Go codebases.

var even []int 
for _, n := range ints {
    if n % 2 == 0 {
        even = append(even, n)
    }
}

With a sequence of such operations, care needs to be taken not to allocate unnecessarily, or loop through items multiple times. There’s no standard for achieving this.

Iterators in Go 1.22

Overview

Let’s take a look at the iterator specification as it stands for Go 1.22 with GOEXPERIMENT=rangefunc, starting with the type definition for an iterator with individual return values.

// Seq is an iterator over sequences of individual values.
// When called as seq(yield), seq calls yield(v) for each value v 
// in the sequence, stopping early if yield returns false.
type Seq[V any] func(yield func(V) bool)

An iterator is a higher-order function that takes a function argument (yield) with the signature func(V) bool. Here are some key points:

• The iterator (Seq function) controls the iteration
• The iterator pushes each value back to the caller by calling yield (the iterator also yields control flow back to the caller by calling yield)
• The caller (or for-range loop) defines how each value will be handled in the yield function
• The caller can stop iteration early by returning false from yield

Iterator sequence

Syntactic sugar

Seq functions can be used in for-range statements.

mySeq := func(yield func(n int) bool) { ... }

for v := range mySeq {
    // do something with v
}

The compiler rewrites the loops like below, as detailed in rewrite.go.

mySeq(func(n int) bool {
    if breakCondition {
        return false // break
    }
    // do something with n
    return true // continue
})

The return value of yield is the equivalent of continue (true) and break (false), respectively, inside a for-range loop.

Implementing a custom iterator

We now have a list of requirements for implementing an iterator:

1. Implement the Seq signature
2. Control iteration of a sequence of values
3. Push each value to the caller via yield
4. Return early when yield returns false

Let’s implement an iterator, All, that returns all elements from a custom slice type, secret.Ints.

package secret

// Int is a secret int that may be hidden (not visible).
type Int struct {
    Val     int
    Visible bool
}

type Ints []Int

The first requirement is to implement the Seq signature correctly.

func (ii Ints) All(yield func(Int) bool) { ... }

Next, control iteration of the slice elements; that is, loop over them.

func (ii Ints) All(yield func(Int) bool) {
    for _, n := range ii { ... }
}

Finally, we need to push each value back to the caller via yield, terminating when yield returns false.

func (ii Ints) All(yield func(Int) bool) {
    for _, s := range ii {
        if !yield(s) {
            return
        }
    }
}

And that’s how you write an iterator in Go 1.22. Let’s try it out.

ints := secret.Ints{ {1, true}, {2, false}, {3, true} }

for n := range ints.All {
    fmt.Println(n)
}
// {1 true}\n {2 false}\n {3 true}\n

rewrite.go should convert the loop to something like below.

ints.All(func(n Int) bool {
    fmt.Println(n)
    return true 
})

Additional signatures

Seq2 will also be added to Go 1.22, and works the same way as Seq, but yields two values rather than one.

Here’s a Seq2 iterator for secret.Ints that returns both the index and element together.

func (ii Ints) AllWithIndex(yield func(int, Int) bool) {
    for i, s := range ii {
        if !yield(i, s) {
            return
        }
    }
}

...

for i, n := range ints.AllWithIndex {
    fmt.Println(i, n)
}
// 0 {1 true}\n 1 {2 false}\n 2 {3 true}\n

Iterator summary

With a little imagination, you could define other iterators like ints.ReverseAll or ints.Visible. There are some examples using lists and trees in the GitHub repository.

GitHub — Jimeux/iter: Go iterators

What we gain from Seq/Seq2 is a consistent design pattern for iteration over a sequence of values in Go. However, some people may not be happy with the syntax, or clear on how error handling should work. Hopefully we have a final spec in Go 1.23 that suits everyone.

The iterator library

To make iterators more convenient, an iterator library proposal is also under discussion. It aims to add functions like Filter, Map, Zip, and Reduce to the standard library. Here’s an example with secret.Ints.

ints := secret.Ints{ {1, true}, {2, false}, {3, true} }

filter := xiter.Filter(func(s secret.Int) bool {
    return s.Visible
}, ints.All)

mapped := xiter.Map(func(s secret.Int) string {
    return strconv.Itoa(s.Val) + "!"
}, filter)

result := xiter.Reduce(nil, func(sum []string, s string) []string {
    return append(sum, s)
}, mapped)

fmt.Println(result) // ["1!", "3!"]

It may not be immediately clear, but we can see from the implementation of Filter that it doesn’t allocate a slice, but instead wraps ints.All (seq).

// Filter returns an iterator over seq that only includes
// the values v for which f(v) is true.
func Filter[V any](f func(V) bool, seq Seq[V]) Seq[V] {
    return func(yield func(V) bool) {
        for v := range seq {
            if f(v) && !yield(v) {
                return
            }
        }
    }
}

Map works in a similar way. Even though there are multiple chained operations, there are exactly len(ints) iterations, and no intermediary slice allocations.

There is a chain of yield calls, triggered from ints.All, that operates on the values one at a time. Map/Reduce will not see values that don’t pass the Filter condition, keeping redundant work to a minimum.

Iterator Chain

Note that call chaining (ints.All(…).Filter(…)) isn’t possible due to type parameters not being supported on methods, but those who find the Reduce syntax ugly might be interested in this proposal that would provide more concise alternatives.

result := slices.Collect(mapped)

Summary

Iterators may be the biggest development in Go since generics, and have the potential to change the way a lot of Go code is written. Much is still undecided, but hopefully this post gives an idea of what to expect iterators to look like, and how the standard library may expand to support them.

In addition, we’re already seeing how iterators may be built upon with concurrency in Russ Cox’s in-depth blog post about coroutines in Go. I hope to cover this topic in a future post.

Cover photo by Daniele Levis Pelusi on Unsplash.

References

• Go 1.22 Release Notes
• spec: add range over int, range over func | GitHub
• proposal: x/exp/xiter: new package with iterator adapters | GitHub
• proposal: slices: add iterator-related functions | GitHub
• Coroutines for Go | research!rsc