Introduction
In my previous post, I discussed the current state of looping in Go. In this post, we’re going to look into a future feature for the Go programming language called range-over function experiment. Go lacks a standard iterator protocol and this is an attempt to provide one. We’ll discuss the motivation for adding this new feature and see some examples on how to use it.
NOTE: In order to run the code, you need to set the GOEXPERIMENT environment variable to rangefunc (e.g. export GOEXPERIMENT=rangefunc).
NOTE: If you are familiar with Python’s iterators and generators, this blog post will seem familiar. ☺
Before we dive into the details of range-over functions, let’s take a look at two common iteration patterns: container iterators and inversion of control
Container Iterators
Let’s start with a basic container type. Here is an example of a stack that is implemented using a linked list.
Listing 1: Stack
10 type node[T any] struct {
11 value T
12 next *node[T]
13 }
14
15 type Stack[T any] struct {
16 head *node[T]
17 }
18
19 func (s *Stack[T]) Push(v T) {
20 s.head = &node[T]{v, s.head}
21 }
22
23 var ErrEmpty = errors.New("empty stack")
24
25 func (s *Stack[T]) Pop() (T, error) {
26 if s.head == nil {
27 var v T
28 return v, ErrEmpty
29 }
30
31 n := s.head
32 s.head = s.head.next
33 return n.value, nil
34 }
Listing 1 shows a stack implementation. On lines 10-13, we define a node type with a value and next field. Then on lines 15-17, we define a Stack type that has a head field of type node. Finally on lines 19-21, we define the Push method and on lines 25-34, we define a Pop method.
We don’t want the Stack type to keep track of any iteration location. If we have more than one iteration going at the same time, the bookkeeping of where each individual iteration is currently happening becomes complex. To keep things simple, we are going to define an iterator that is responsible for a single iteration at a time.
Listing 2: StackIterator
36 func (s *Stack[T]) Items() *StackIterator[T] {
37 return &StackIterator[T]{s.head}
38 }
39
40 type StackIterator[T any] struct {
41 node *node[T]
42 }
43
44 func (s *StackIterator[T]) Next() (T, bool) {
45 if s.node == nil {
46 var v T
47 return v, false
48 }
49
50 n := s.node
51 s.node = s.node.next
52 return n.value, true
53 }
Listing 2 shows the implementation of an iterator for the stack. On lines 36-38, we define a method named Items that returns a pointer to a value of the StackIterator type. On lines 40-42, we define the StackIterator type which holds the current node being iterated over. Finally on lines 44-53, we define the Next method that returns the next value in the stack from the current iteration position.
Listing 3: Using the Iterator
128 it := s.Items()
129 for v, ok := it.Next(); ok; v, ok = it.Next() {
130 fmt.Println(v)
131 }
Listing 3 shows how to use the iterator. On line 128, we create an iterator using the Item method from the Stack type. Then on lines 129-131, we iterate over the items in the stack using the Next method from the StackIterator type. When the Next method returns false for the second value, it means there are no more items left to iterate over.
Now that you understand how separating iterators from containers simplifies iteration support, we can look at how inversion of control helps us write a single iterator implementation.
Inversion of Control
Inversion of control is an old and established idea. It lets the framework (in our case, the “for” loop) do the flow so the user only needs to supply the business logic.
Say we want to print all the items in the stack, we can write the following code:
Listing 4: PrintItems
55 func (s *Stack[T]) PrintItems() {
56 for n := s.head; n != nil; n = n.next {
57 fmt.Println(n.value)
58 }
59 }
Listing 4 shows the PrintItems method. On line 56, we use a for loop to iterate over the nodes and then on line 54, we print the value of each node that exists.
Now, what if instead of printing values we want to save the values to a file, or maybe send them as a response in an HTTP request handler?
We’re not going to write multiple implementations for each scenario I just mentioned. Instead we will write one implementation named Do that performs the for loop and executes a second function named yield which is passed in by the user to provide the business logic.
Listing 5: Do Method
61 func (s *Stack[T]) Do(yield func(v T)) {
62 for n := s.head; n != nil; n = n.next {
63 yield(n.value)
64 }
65 }
Listing 5 shows the Do method. On line 61, we define the Do method that accepts a yield function that will process a value of some type T. Then on line 62, we iterate over the nodes and then on line 63, we pass the current value to the yield function.
Listing 6: Using The Do Method
134 s.Do(func(n int) {
135 fmt.Println(n)
136 })
Listing 6 shows how to use the Do method. On line 134, we call Do with an anonymous function that accepts a parameter of type int and then prints the value. In this case, the value of some type T is a value of type int.
You can see this Do pattern in several places in the standard library. For example: fs.WalkDir and ring.Do.
What happens if we want to stop the iteration after the first 5 values? The current implementation can’t be stopped, but if we change the yield function to return a boolean value, it can indicate that the iteration should stop. Which brings us to the topic at hand: range-over function.
Range-Over Functions
To try out range-over functions in Go 1.22, you need to set the GOEXPERIMENT environment variable to rangefunc. Then we need to use the new standard library package named iter that defines two new types:
Listing 7: iter.Seq and iter.Seq2
type Seq[V any] func(yield func(V) bool)
type Seq2[K, V any] func(yield func(K, V) bool)
Listing 7 shows the new iter.Seq & iter.Seq2 types.
Let’s start with the iter.Seq type. It defines a function that accepts a yield function as a parameter. The yield function is defined to accept a value and return a bool. It’s very much like our Do method implementation from above, but now the for statement directly supports it.
Let’s make changes to our stack implementation to support this new range-over function support.
Listing 8: Iter
67 func (s *Stack[T]) Iter() func(func(T) bool) {
68 iter := func(yield func(T) bool) {
69 for n := s.head; n != nil; n = n.next {
70 if !yield(n.value) {
71 return
72 }
73 }
74 }
75
76 return iter
77 }
Listing 6 shows the new Iter method we are adding to the stack implementation. On line 67, we define the Iter method which returns a function that matches the iter.Seq type. On line 68, we define a literal function that will be returned from Iter. On line 69, we use a for loop to iterate over the stack nodes. On line 70, we pass the current node value to the yield function, and if the yield function returns false the iteration stops on line 71. Finally on line 76, we return the iteration function.
Now let’s use the Iter method.
Listing 9: Using Iter
139 for v := range s.Iter() {
140 fmt.Println(v)
141 }
Listing 9 shows how to use the new Iter method. One line 139, we use a regular for-range to print each value of the stack. In this case, the fmt.Println function on line 140 represents the yield function. Since this function can never return a bool, this loop will iterate over the entire stack.
In some cases, we need both values that can be returned from a for-range loop. For example, getting the index position and the value, or in the case of a map both the key and the value. For these cases, we can use iter.Seq2
Listing 10: Iter2
79 func (s *Stack[T]) Iter2() func(func(int, T) bool) {
80 iter := func(yield func(int, T) bool) {
81 for i, n := 0, s.head; n != nil; i, n = i+1, n.next {
82 if !yield(i, n.value) {
83 return
84 }
85 }
86 }
Listing 10 shows the new Iter2 method we are adding to the stack implementation. On line 79, we define the Iter2 method, which returns a function that matches the iter.Seq2 type. On line 80, we define a literal function that will be returned from Iter2. On line 81, we use a for loop to iterate over the stack nodes. On line 82, we pass the index and current node value to the yield function, and if the yield function returns false the iteration stops on line 83.
Listing 11: Using Iter2
144 for i, v := range s.Iter2() {
145 fmt.Println(i, v)
146 }
Listing 11 shows how to use the new Iter2 method. One line 144, we use a regular for-range loop to print each value of the stack. Once again, the fmt.Println function on line 145 represents the yield function, but this time we pass both the index and value to the function. Since this function can never return a bool, this loop will iterate over the entire stack.
Pulling Values
Another interesting piece of functionality included in the new iter package are these pull functions.
Listing 12: Pull and Pull2
func Pull[V any](seq Seq[V]) (next func() (V, bool), stop func())
func Pull2[K, V any](seq Seq2[K, V]) (next func() (K, V, bool), stop func())
These pull functions are passed a Seq value and return a next and stop function. The next function is used to pull the next value from Seq and stop is used to force the iteration to stop. The stop function works by passing a yield function that returns false at the next iteration.
One example of why we might need these functions is if we wanted to find the max value currently stored in the stack. Remember, we don’t know the length of the stack (and it could potentially be infinite) and we can’t index directly into the stack.
Let’s see how we can use Pull to write our Max functionality.
Listing 13: Max
91 func Max[T cmp.Ordered](seq iter.Seq[T]) (T, error) {
92 pull, stop := iter.Pull(seq)
93 defer stop()
94
95 max, ok := pull()
96 if !ok {
97 return m, fmt.Errorf("Max of empty sequence")
98 }
99
100 for v, ok := pull(); ok; v, ok = pull() {
101 if v > max {
102 max = v
103 }
104 }
105
106 return max, nil
107 }
Listing 13 shows the Max function. On line 91, we define Max to receive an iter.Seq value as a parameter and return the max value or an error. On line 92, we use iter.Pull to get the pull and stop functions. On line 93, we defer the stop function to signal that we want to stop the iteration once the Max function returns. On line 95, we use the pull function to get the first value and then on line 96, we check if there was a value returned.
On line 100, we use a for loop to iterate over the rest of the values by using the pull function. On line 101 we check if the current value is bigger than our current max value and if so we update the max value on line 102. Finally, on line 106, we return the maximal value and nil for error.
Listing 14: Using Max
148 m, err := Max(s.Iter())
149 if err != nil {
150 fmt.Println("ERROR:", err)
151 } else {
152 fmt.Println("max:", m)
153 }
Listing 14 shows how to use the Max function. On line 148, we call Max passing the value returned by the stack’s Iter method. On line 149, we check for an error and print the error on line 150. Otherwise on line 152, we print the maximal value.
Conclusion
The range-over function experiment tries to give Go a general way to provide custom iterators. Using iter.Seq and iter.Seq2 allow you to use the familiar for loop, burdening the implementation of the iter package on the library writer.
I hope I shed some light on why we have this experiment and also on how to use it. You can read more about it on the wiki page.
I’d love to hear from you if you have more ideas on how to use this experiment. For me, coming from Python, there are many examples such as linear spaces, generic filters, generic mapper and more.
Contact me at miki@ardanlabs.com.