proposal: maps: helper to loop over the maps in predictable order

[giautm]

Proposal Details

I propose a function to allow a loop over a map in stable order. It takes all keys of the map, sorts them, and loops over the slides, each loop, yields a key-pair.

// SortedByKey returns an iterator for the given map that
// yields the key-value pairs in sorted order.
func SortedByKey[Map ~map[K]V, K cmp.Ordered, V any](m Map) iter.Seq2[K, V] {
	return func(yield func(K, V) bool) {
		for _, k := range slices.Sorted(Keys(m)) {
			if !yield(k, m[k]) {
				return
			}
		}
	}
}

[giautm]

The Iter func will be helpful for the case you need to build an output (text or HCL) that comes from a Map.

func attributes() map[string]string {
	return map[string]string{
		"key1": "val1",
		"key2": "val2",
	}
}

func Example_SortedByKey() {
	for k, v := range SortedByKey(attributes()) {
		fmt.Println(k, v)
	}
	// Output:
	// key1 val1
	// key2 val2
}

Or processing a map with API call.

https://docs.temporal.io/develop/go/core-application#workflow-logic-requirements

In Go, Workflow Definition code cannot directly do the following:

• Iterate over maps using range, because with range the order of the map's iteration is randomized.
  Instead you can collect the keys of the map, sort them, and then iterate over the sorted keys to access the map.
  This technique provides deterministic results.
  You can also use a Side Effect or an Activity to process the map instead.
• Call an external API, conduct a file I/O operation, talk to another service, etc. (Use an Activity for these.)

[giautm]

@cuonglm Sent me this comment, but I think it's for very specific case that only need process on keys. The Iter or SortedIter would be nice for reduce function calls, shorter syntax, drop-in-replacement to fix bugs with loop over map.

You've more than welcome to raise your consent here.

[ianlancetaylor]

It's a bit unfortunate that slices.Sorted and maps.Sorted would have rather different behavior.

[gazerro]

It's a bit unfortunate that slices.Sorted and maps.Sorted would have rather different behavior.

It could be called SortedByKey

for k, v := range maps.SortedByKey(m) {
     fmt.Println(k, v)
}

in this way, you could also have SortedByValue.

[gophun]

It doesn't feel right to have a function that does an allocation and a full copy just for iteration. Those needing such functionality should likely opt for an ordered map data structure from the start.

[apparentlymart]

While I do agree that using this function in a hot path would probably not be a good idea, I've read and written many variations of this behavior in non-performance-sensitive situations, such as to produce predictable results in a test case, and so I think it would be nice to have a more readable shorthand for this seemingly-common need.

There are also plenty of situations where the input map is small, and where the allocation/sorting cost is likely immaterial.

I guess the tradeoff here is, as usual, whether it seems likely that offering this utility in stdlib would make people more likely to use it in situations where the performance tradeoffs are not appropriate. Personally I think in this case it would be sufficient to mention in the function's documentation that it allocates a slice containing all of the keys and sorts it using the natural ordering of the key type, leaving potential callers to make their own conclusions about whether that's acceptable.

(I also prefer the name SortedByKey to make the behavior of the function more explicit at the callsite.)

[jimmyfrasche]

If there were

package maps
func Index[Map ~map[K]V, Slice ~[]K, K comparable, V any](m Map, ks Slice) iter.Seq2[K, V] {
	retun func(yield func(K, V) bool) {
		for _, k := range ks {
			if v, ok := m[k]; ok {
				if !yield(k, v) {
					return
				}
			}
		}
	}
}

then, in the cases where you do need it, it would just be

maps.Index(m, slices.Sorted(maps.Keys(m))...)

[cespare]

I also regularly have the experience of writing the boilerplate code to pull all the keys out of a map into a slice, sort it, and then iterate the map. However, I agree with @gophun: the right answer here is not to make this easier, but to add a sorted map type to the standard library. If it were just as convenient to use the sorted map as a regular map, then there'd be no reason not to reach for that and write the better code right off the bat rather than doing the post hoc key-sorting.

And now that we have both generics and iterator functions, I think we're at the point where we can write an ergonomic implementation that would be appropriate for the standard library. (#60630 is one existing proposal.)

I would like to note that prior to Go 1.23, to iterate over map in predictable order you have to write something like:

import (
	"slices"

	"golang.org/x/exp/maps"
)

...
keys := maps.Keys(m)
slices.Sort(keys)
for _, k := range keys {
    v := m[k]
}

But since Go 1.23, you can just write:

import (
	"maps"
	"slices"
)
...
for _, k := range slices.Sorted(maps.Keys(m)) {
    v := m[k]
}

which seems good enough for me.

[giautm]

which seems good enough for me.

It doesn't change the fact - that we still allocate a new slice for the keys. maps.SortedByKey is convenient for processing the map right returned from the functions.

All of you guys have the right points about this function. Yes, it allocates memory doesn't seem to be the correct way to implement this, but I think we can change it in the future by optimizing from compile.

Creating another map structure sounds like the right way, but the are plenty of libraries that won't change to new maps. - And it should be for memory sensitive optimize

In a lot of cases, maps with under 100 items didn't need such optimization.

import (
	"maps"
	"slices"
)
// ...
m := getattributes()
for _, k := range slices.Sorted(maps.Keys(m)) {
	v := m[k]
	// ...
}

for k, v := range maps.SortedByKey(getattributes()) {
	// ...
}

[apparentlymart]

The point about slices.Sorted(maps.Keys(m)) is fair. I hadn't noticed that combination was now possible in Go 1.23.

One small advantage of maps.SortedByKey is that it can know exactly how large a slice it needs to allocate because a map has a known length, whereas slices.Sorted is backed by slices.AppendSeq that can't predict how long its input iterator will be and so could potentially reallocate multiple times.

However, we already discussed that this proposed function is not intended for performance-sensitive situations anyway, so that argument doesn't seem very convincing to me.

I do still think that this is a common enough pattern that it could be justified to offer it as a single function, and so I'm leaving my 👍 upvote on it, but I'd also be sympathetic to the argument that we should wait and see how the ecosystem responds to slices.Sorted(maps.Keys(m)) before assuming that a single-function shorthand is warranted. 🤔