Go 1.23’s Iter package.

Writing a custom iterator that returns a map’s values in a constant order.

5 min read1 day ago

Maps are notoriously known for changing their iteration order during each range loop. “When iterating over a map with a range loop, the iteration order is not specified and is not guaranteed to be the same from one iteration to the next.” The solution proposed by the Go team was to define a separate data structure that explicitly specifies the order of iteration; this may be a slice or array with the keys in the desired order.

In this post, we’ll look at a recent approach to solving the iteration order problem; as well as understand how to define a really basic iterator with the iter package.

Overview

The problem at hand is that I have a map with scores tied to a unique user ID. The user IDs are defined in incremental nature, where the first ID would be 1 , the second 2 and so on.

For this solution, I will define a custom type with the underlying type being map[string]int. Since I’ve defined this type, I can define a method named SortedKeys that will return the Seq2 (Seek 2) type from the iter package. This method can then be passed as the range operand and thus guaranteeing the order of iteration on each call.

It’s important to note that the “tried and proven” solution of defining a separate data structure will be hidden within the SortedKeys method. Let’s start with the custom type.

CustomMapType

Prior to defining the type, I’ll need a utility function to sort the map keys into a string array. Since I’m not the first person to have this issue, I prompted Chat GPT to write this code for me. Here is the function outlined in this paragraph:

func SortMapKeysByNumericalOrder(m map[string]int) []string {
 keys := make([]string, 0, len(m))
 for k := range m {
  keys = append(keys, k)
 }

 sort.Slice(keys, func(i, j int) bool {
  num1, _ := strconv.Atoi(keys[i])
  num2, _ := strconv.Atoi(keys[j])
  return num1 < num2
 })

 return keys
}

Function SortMapKeysByNumericalOrder will sort a map’s numerical string keys from lowest to greatest. The expectation here is that the map keys are strings that can be parsed as numbers with Go’s strconv package.

Next, I’ll define the custom map type:

type CustomMapType map[string]int

Just like that, I’ve defined a type that inherits all of the properties of a map. Go is great.

Next, I need to add the SortedKeys method. Here is the initial version of the method:

func (cm CustomMapType) SortedKeys() iter.Seq2[string, int] {
  // this will return a compile error
}

Before going any further, let’s look at the Seq2 type from the iter package. Seq2 is a generic type that is ideal for maps as it can return the key and value of a map entry. Here is the type definition:

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

According to the type definition, the SortedKeys method should return the following func(yield func(string, int) bool) (to match the return type specified by the SortedKeys method). Here is the updated code:

func (cm CustomMapType) SortedKeys() iter.Seq2[string, int] {

   return func(yield func(string, int) bool) {
    
   }
}

Although the compilation issues are solved, the previous code will not return any values because I’m not calling the yield function. Here is the following code in action:

Yield

When I first saw the signature of the Seq2 type, I thought that Go had a new keyword. Turns out it's the name of the function used to send values back to the range loop (how cool is that!). Here is a revised version of the SortedKeys method with the yield function being called:

func (cm CustomMapType) SortedKeys() iter.Seq2[string, int] {

   sortedKeys := SortMapKeysByNumericalOrder(cm)
  
   return func(yield func(string, int) bool) {
      for _, k := range sortedKeys {
          // this will result in a compilation warning
          // as the loop will never stop.
          yield(k, cm[k])
      }
   }
}

In the revised code, I’m calling the utility function SortMapKeysByNumericalOrder to sort the keys and then using the yield function to return the values back to the range loop calling the SortedKeys method. The first parameter of the yield function becomes the key within the calling range loop, and the second parameter is the value.

However, we’re not out of the woods yet; this is due to the fact that my custom Seq2 function should return early when the value returned by the yield function is false. yield will return false if the range loop is interrupted and so, it is important to stop calling the yield function after the loop has exited. Here is the revised code:

func (cm CustomMapType) SortedKeys() iter.Seq2[string, int] {

   sortedKeys := SortMapKeysByNumericalOrder(cm)
  
   return func(yield func(string, int) bool) {
      for _, k := range sortedKeys {
         // yield function will run
         // during cond. statement.
         if !yield(k, cm[k]) {
          return
         }
      }
   }
}

Putting it together

With most aspects of the program defined, I’ll need a main function that ties the functionality together. The program will be simple, I will:

Initialize a variable with type CustomMapType and populate it with some scores.
Add a range loop with the SortedKeys method as the range operand and print each key-value pair to confirm if the map iteration order is consistent.

Here is the code for the main function:

func main() {

   cm := CustomMapType{
    "2":   500,
    "1":   1000,
    "3":   400,
    "6":   300,
    "0.1": 200,
   }
  
   for k, v := range cm.SortedKeys() {
      fmt.Println(k, v)
   }

}

Here is the full code in action:

Conclusion

The example provided in this post is quite simple and offers some insight into the yield function and how it passes values to a calling range loop. One of the benefits I see for library providers is it will give you more control over the experience you provide to your end users; it also abstracts away the code required to sort map keys into the desired order.

Another perceived benefit I can foresee is drastically reducing memory occupied by arrays; this can be achieved by fetching (during iteration) and passing memory intense values through the yield function. I have yet to test this theory.

Thank you for reading, you can find more information about the sources used for this post below:

Sources

Go maps in action (2013) — https://go.dev/blog/maps

Iter Package — https://pkg.go.dev/iter

Go Playground session — https://go.dev/play/p/ky36Y6KCf6R