proposal: spec: generic type constraint for iterables

[adam-azarchs]

Go Programming Experience

Experienced

Other Languages Experience

go, c, c++, rust, c#, python, javascript...

Related Idea

• Has this idea, or one like it, been proposed before?
• Does this affect error handling?
• Is this about generics?
• Is this change backward compatible? Breaking the Go 1 compatibility guarantee is a large cost and requires a large benefit

Has this idea, or one like it, been proposed before?

Not that I've been able to find.

Does this affect error handling?

No.

Is this about generics?

This is about generic type constraints.

Proposal

The proposal would be to add a new keyword, similar to comparable, for iterable types. That is, iterable[T] would constrain the type to one of iter.Seq[T], map[T]<anything>, or <-chan T - that is, anything for which reflect.ValueOf(y).Seq() would return a sequence for with the elements can be treated as T.

The go 1.23 iterable support is great! However, the need to use e.g. maps.Keys to convert a map[T]any to a iter.Seq[T] makes writing certain kinds of common iterator utilities difficult. In many cases, the caller can simply wrap the argument themselves with e.g. slices.Values() or maps.Keys(). However, this adds boilerplate, and is problematic if the iterator in question is nested inside some other type.

Take for example the flatten (or chain) adaptor that is common in other languages.

In go, you could implement this as several functions, e.g.

func FlattenSlice[S ~[]V, V any](outer iter.Seq[S]) iter.Seq[V] {
	return func(yield func(V) bool) {
		for inner := range outer {
			for v := range slices.Values(inner) {
				if !yield(v) {
					return
				}
			}
		}
	}
}

func FlattenMap[S ~map[V]T, V comparable, T any](outer iter.Seq[S]) iter.Seq[V] {
	return func(yield func(V) bool) {
		for inner := range outer {
			for v := range inner {
				if !yield(v) {
					return
				}
			}
		}
	}
}

func FlattenChan[S ~<-chan V, V any](outer iter.Seq[S]) iter.Seq[V] {
	return func(yield func(V) bool) {
		for inner := range outer {
			for v := range inner {
				if !yield(v) {
					return
				}
			}
		}
	}
}

func FlattenIter[V any](outer iter.Seq[iter.Seq[V]]) iter.Seq[V] {
	return func(yield func(V) bool) {
		for inner := range outer {
			for v := range inner {
				if !yield(v) {
					return
				}
			}
		}
	}
}

However, there's no way to write one implementation that works in all such cases.

Under this proposal, Flatten could be implemented as

func Flatten[S iterable[T], T any](s iter.Seq[S]) iter.Seq[V] {
	return func(yield func(V) bool) {
		for inner := range outer {
			for v := range inner {
				if !yield(v) {
					return
				}
			}
		}
	}
}

One could imagine writing a function like

func IntoIter[V any](s any) iter.Seq[V] {
	switch s := s.(type) {
	case []V:
		return slices.Values(s)
	case <-chan V:
		return func(yield func(V) bool) {
			for v := range s {
				if !yield(v) {
					return
				}
			}
		}
	case iter.Seq[V]:
		return s
	default:
		v := reflect.ValueOf(s)
		rs := v.Seq()
		return func(yield func(V) bool) {
			for rv := range rs {
				if !yield(rv.Interface().(V)) {
					return
				}
			}
		}
	}
}

However:

1. One needs to use reflection to handle map types (and some other edge cases), because we don't know the value type for the map, nor do we want to have to constrain V to be comparable in cases where the sequence is not a map.
2. There's the compiler can't infer the type for V in a call.
3. There isn't any compile-time checking of the input type, leading to possible panics in the reflection pathway.
4. This still doesn't really solve the problem for implementing Flatten, unless its input parameter is iter.Seq[any]. That means that functions which want to use this converter are also left without type-checking for their input arguments.

One important thing to note here about slices: reflect.Value.Seq() on a slice will return the indices. This is entirely consistent with the behavior of range, and it would be surprising for it to work otherwise. However, I have a hard time imagining a case where you'd want it to work that way in contexts where you are intending to iterate over some sequence of values where you don't know that the source is a slice. It certainly wouldn't be desirable behavior in the above Flatten example.

Language Spec Changes

A new keyword, valid in the scope of a generic type constraint, for specifying that the type in question is iterable.

Informal Change

No response

Is this change backward compatible?

Adding a new keyword is always a potential breaking change. However this keyword would only be valid in the context of a generic type constraint, so it would only affect code which defines a type iterable (or whatever we want to name that bikeshed) which is being used as a generic type constraint, which seems unlikely.

Orthogonality: How does this change interact or overlap with existing features?

This is essentially fills a gap in the interaction between go1.23 range over functions and the generic type system.

Would this change make Go easier or harder to learn, and why?

Having access to a common library of iterator adaptors like what is found in other languages would help bring new developers up to speed quickly.

On the other hand, the above-mentioned caveats about handling of slice types could be considered a sharp edge.

Cost Description

Mostly implementation complexity. I'm not really sure how one would implement it, since I am not familiar with the implementation details of generics in the compiler. Possibly some "magic" runtime-internal function that works like IntoIterator above, injected into every place that a value with the constrained type is used.

Changes to Go ToolChain

Just the compiler

Performance Costs

No response

Prototype

No response

[gabyhelp]

Related Issues and Documentation

• proposal: Go 2: range-over-function + range over types implementing iterator interface #65742 (closed)
• proposal: package collection and iterator design for go #50112 (closed)
• proposal: Go 2: add a new iterator syntax, package, interfaces #54047 (closed)
• proposal: Go 2: alternate function call syntax to improve ergonomics of chainable top-level functions #47680 (closed)
• proposal: Go 2: function values as iterators #43557 (closed)
• proposal: Go 2: generic types (GT) #39669 (closed)
• proposal: Go 2: spec: for range with defined types #47707 (closed)

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[adonovan]

(Nitpick: this would have to be a new predeclared name (like comparable), not a new keyword, because adding a new keyword is not a backward compatible change: it breaks any program that has used it as an identifier.)

Go already has a type that expresses an abstract iterator: iter.Seq[T]. If you want to write the equivalent of Python's itertools.chain, its signature should be:

func Chain[T any](sequences ...iter.Seq[T]) iter.Seq[T]

(Let's ignore for now the issue of variations in the element type T.)

To call this function with a sequence of different iterators, you would have to adapt each type to iter.Seq, for example:

func f(ch chan int, m map[int]int, slice []int) {
       for x := range Chain(
            chanElems(ch),
            maps.Keys(m),
            maps.Values(m),
            slices.Values(slice)) {
            ...
       }
}

func chanElems[T any](ch chan T) iter.Seq[T] { ... }

This proposal is essentially an objection to the need to explicitly inject each sequence type to an iter.Seq. The maps example makes very clear why this is the wrong choice: there are two different possible single-valued iterators (Keys and Values). The design of Go values explicitness when conversions are nontrivial, so I don't think this feature makes sense.

[generikvault]

You could write a FlattenFunc instead. That would give you a lot more felxibillity.

func FlattenFunc[S, T any](s iter.Seq[S], func(S) iter.Seq[T]) iter.Seq[T]

Could be called with the existing functions like map.Keys, maps.Values etc.

[adam-azarchs]

Yes, we have an interface for abstract iterables. The problem is that the built-in types don't implement that interface.

@adonovan that example of Chain is similar to same as python's itertools.chain but not to itertools.chain.from_iterable, which is I guess more what I was thinking of as it allows the outer iterator to be lazy. In your form, sure, the conversion is easy enough, but in the sequence-of-sequences case, e.g. like

func FlattenIter[V any](outer iter.Seq[iter.Seq[V]]) iter.Seq[V] {
	return func(yield func(V) bool) {
		for inner := range outer {
			for v := range inner {
				if !yield(v) {
					return
				}
			}
		}
	}
}

it's not so easy.

@generikvault 's suggestion of having a converter function is a good one, which I'd say 80% solves the problem. It's not as convenient, but then I suppose it's good enough to not be worth adding a new pre-defined type.

[timothy-king]

FWIW this is related to relaxing the core type restriction of range statements.