maps: add iterator-related functions

[rsc]

We propose to add the following functions to package maps, to provide good support for code using iterators.

This is one of a collection of proposals updating the standard library for the new 'range over function' feature (#61405). It would only be accepted if that proposal is accepted. See #61897 for a list of related proposals.

All serves as a “source” for iterators.

// All returns an iterator over key-value pairs from m.
func All[Map ~map[K]V, K comparable, V any](m Map) iter.Seq2[K, V] {
	return func(yield func(K, V) bool) bool {
		for k, v := range m {
			if !yield(k, v) {
				return false
			}
		}
		return true
	}
}

Keys and Values are like All: not terribly useful by themselves but useful as inputs to other iteration adapters.
In particular, we expect that x := slices.Sorted(maps.Keys(m)) will be a common pattern.

// Keys returns an iterator over keys in m.
func Keys[Map ~map[K]V, K comparable, V any](m Map) iter.Seq[K] {
	return func(yield func(K) bool) bool {
		for k := range m {
			if !yield(k) {
				return false
			}
		}
		return true
	}
}

// Values returns an iterator over values in m.
func Values[Map ~map[K]V, K comparable, V any](m Map) iter.Seq[V] {
	return func(yield func(V) bool) bool {
		for _, v := range m {
			if !yield(v) {
				return false
			}
		}
		return true
	}
}

Insert and Collect serve as “sinks” for iterators.

// Insert adds the key-value pairs from seq to m.
func Insert[Map ~map[K]V, K comparable, V any](m M, seq iter.Seq2[K, V]) {
	for k, v := range seq {
		m[k] = v
	}
	return m
}

// Collect collects key-value pairs from seq into a new map
// and returns it.
func Collect[K comparable, V any](seq iter.Seq2[K, V]) map[K]V {
	m := make(map[K]V)
	Insert(m, seq)
	return m
}

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

[rsc]

Finishing this proposal discussion is blocked on #61405.

[gopherbot]

Change https://go.dev/cl/558736 mentions this issue: maps: add All, Keys, Values, Insert, Collect

[earthboundkid]

It is unfortunate that slices.Sorted(maps.Keys(m)) won't get a length hint from m and may end up doing unnecessary allocations and copies. What if there were also maps.SortedKeys(m) that did the right thing?

[Merovius]

@earthboundkid ISTM if that is a concern, it should maybe rather be slices.SortedLength[E any](int, iter.Seq[E]) (modulo name), as any use of "make a sorted slice from an iterator" would suffer the same issue.

I get, FWIW, that "get the sorted keys from a map" is a fairly common use case, to try and get deterministic order from the specifically non-deterministic maps. But it still seems a more general problem.

[gophun]

maps.Keys could return a sequence implementation with a length hint and slices.Sorted could type assert for that, similar to what some io.Reader functions do.

[gophun]

Nevermind, iter.Seq is a concrete type, not an interface.

[rsc]

It's true that slices.Sorted(maps.Keys(m)) will not pre-size the slice, but that's not necessarily a strike against the iterator forms. We could have a separate discussion about maps.KeysSorted and maps.KeysSortedFunc as optimizations, if that became a concern.

[rsc]

Have all remaining concerns about this proposal been addressed?

The full godoc is:

func All[Map ~map[K]V, K comparable, V any](m Map) iter.Seq2[K, V]
    All returns an iterator over key-value pairs from m.

func Collect[K comparable, V any](seq iter.Seq2[K, V]) map[K]V
    Collect collects key-value pairs from seq into a new map and returns it.

func Insert[Map ~map[K]V, K comparable, V any](m Map, seq iter.Seq2[K, V])
    Insert adds the key-value pairs from seq to m.

func Keys[Map ~map[K]V, K comparable, V any](m Map) iter.Seq[K]
    Keys returns an iterator over keys in m.

func Values[Map ~map[K]V, K comparable, V any](m Map) iter.Seq[V]
    Values returns an iterator over values in m.

[earthboundkid]

SortedKeys can wait and be a separate proposal.

[zephyrtronium]

It's true that slices.Sorted(maps.Keys(m)) will not pre-size the slice, but that's not necessarily a strike against the iterator forms.

More wordy, but slices.Sorted(slices.Append(make([]T, 0, len(m)), maps.Keys(m))) does preallocate the slice, as long as T can be named. And an extra generic helper func PreallocKeys[Map ~map[K]V, K comparable, V any](m Map) []K { return make([]K, 0, len(m)) } addresses the situations where it can't.

[rsc]

Based on the discussion above, this proposal seems like a likely accept.
— rsc for the proposal review group

The full godoc is:

func All[Map ~map[K]V, K comparable, V any](m Map) iter.Seq2[K, V]
    All returns an iterator over key-value pairs from m.

func Collect[K comparable, V any](seq iter.Seq2[K, V]) map[K]V
    Collect collects key-value pairs from seq into a new map and returns it.

func Insert[Map ~map[K]V, K comparable, V any](m Map, seq iter.Seq2[K, V])
    Insert adds the key-value pairs from seq to m.

func Keys[Map ~map[K]V, K comparable, V any](m Map) iter.Seq[K]
    Keys returns an iterator over keys in m.

func Values[Map ~map[K]V, K comparable, V any](m Map) iter.Seq[V]
    Values returns an iterator over values in m.

[magical]

func Keys[Map ~map[K]V, K comparable, V any](m Map) iter.Seq[K]
Keys returns an iterator over keys in m.

func Values[Map ~map[K]V, K comparable, V any](m Map) iter.Seq[V]
Values returns an iterator over values in m.

What, if anything, is guaranteed about the iteration order of Keys and Values (EDIT: and All)? I believe this should be specified in the docs.

Does these two for loops yield the same key order? I would assume not, based on analogy to range-over-map.

for k := range maps.Keys(m) {
    println(k)
}
for k := range maps.Keys(m) {
    println(k)
}

What about this?

seq := maps.Keys(m)

for k := range seq {
    println(k)
}
for k := range seq {
    println(k)
}

I can see why it might make sense from an implementation standpoint for this to also be randomized. However it also seems weird for a value of type Seq, which nominally represents a sequence, to in fact yield multiple different sequences.

[jimmyfrasche]

Insert should clearly specify whether it overwrites existing keys

[fzipp]

@earthboundkid An iter.Seq is not an iterator and does not exhaust.

[earthboundkid]

Yes, I deleted my comment but you beat me to it. 😄

[rsc]

Happy to update docs to say that iteration order is undefined (different each time) and Insert does overwrite keys.

[rsc]

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group

The full godoc is:

func All[Map ~map[K]V, K comparable, V any](m Map) iter.Seq2[K, V]
    All returns an iterator over key-value pairs from m.

func Collect[K comparable, V any](seq iter.Seq2[K, V]) map[K]V
    Collect collects key-value pairs from seq into a new map and returns it.

func Insert[Map ~map[K]V, K comparable, V any](m Map, seq iter.Seq2[K, V])
    Insert adds the key-value pairs from seq to m.

func Keys[Map ~map[K]V, K comparable, V any](m Map) iter.Seq[K]
    Keys returns an iterator over keys in m.

func Values[Map ~map[K]V, K comparable, V any](m Map) iter.Seq[V]
    Values returns an iterator over values in m.

[magical]

@rsc I don't see any doc changes