proposal: iter: add method to perform delegated yield with returned bool

[DeedleFake]

Proposal Details

The blog post about range-over-func gives the following example of a recursive iter.Seq over the values of a binary tree:

func (t *Tree[E]) All() iter.Seq[E] {
    return func(yield func(E) bool) {
        t.push(yield)
    }
}

func (t *Tree[E]) push(yield func(E) bool) bool {
    if t == nil {
        return true
    }
    return t.left.push(yield) &&
        yield(t.val) &&
        t.right.push(yield)
}

I have built recursive iterators of similar patterns on several occasions, including one recently. The secondary method is necessary because iter.Seq does not return a final boolean indicating if it exited early or not. I remember that the original prototype had an extra boolean, but it was completely ignored by the iterator mechanism. However, every time I write a recursive iterator, it requires a function of a similar design, and I've been starting to think that having something like that in the standard library would be nice. It's essentially the equivalent of yield* in Python and similar things in a lot of other languages with generator functions.

For example,

package iter

// Push iterates over seq, calling yield for each value. It returns
// false if yield ever does and returns true otherwise.
//
// Push is primarily useful for building iter.Seq implementations that
// at some point yield all of the values of a different iter.Seq
// instance such as iterators over recursive data structures.
func (seq Seq[T]) Push(yield func(T) bool) bool {
	for v := range seq {
		if !yield(v) {
			return false
		}
	}
	return true
}

and the equivalent for iter.Seq2.

This would change recursive binary tree iterator example to just

func (t *Tree[E]) All() iter.Seq[E] {
	return func(yield func(E) bool) {
		if t == nil {
			return true
		}
		_ = t.left.All().Push(yield) &&
			yield(t.val) &&
			t.right.All().Push(yield)
	}
}

The need for _ = is a bit weird, but overall I'll take that minor awkwardness over rewriting this function all over the place.

I also considered a top-level function, something like func YieldAll[T any](seq iter.Seq[T], yield func(T) bool), but the method feels a bit nicer to me.

Edit: Forgot to mention alternative method names. I also thought of Via(), YieldTo(), and a few others. I'm very much not too picky about the bikeshed's color, though.

[gabyhelp]

Related Issues

• iter: new package for iterators #61897 (closed)
• proposal: iter: Enumerate, Keys and Values functions #68887 (closed)
• proposal: iter: add Empty function #66187
• proposal: iter: add New #67930 (closed)

Related Documentation

• Range Over Function Types > Iterating on iterators > Binary tree
• Range Over Function Types > Standardize the approach > Standard (push) iterators
• Go Wiki: Rangefunc Experiment > What will idiomatic APIs with range functions look like?

Related Discussions

• user-defined iteration using range over func values

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

[mateusz834]

As an alternative, we can also add func iter.Concat[T](...iter.Seq[T]) iter.Seq[T], but then this will not allow to easily chain yield(t.val).

[adonovan]

I agree that there is an unfortunate impedance mismatch between the signature of the top-level iterator function func (T) All() iter.Seq[E] and that of the func (T) all(yield func(E) bool) bool method that must be used internally to express the recursion. If they had been one and the same, then you could avoid the need to write the additional wrapper function, and you could also get the boolean result of the traversal for free, without having to add a trivial loop to recompute it. There's also a nice symmetry between the two meanings of the name "all": t.all(f) reports whether predicate f(x) is true for all x in the sequence, and range t.all {...}, syntactic sugar for all(func(E) bool {...}), would give you all the elements of the sequence (for which you didn't execute a break or return). But that's not the design that was chosen: IIRC the objection was that it would be easy to return the wrong final boolean value (i.e. not consistently folding with &&), and that it's easy to recompute the boolean. It may also have been stated that we don't want to encourage using range t.all, we want to see t.All()--in other words, methods should return sequence iterators, not be sequence iterators.

All that said, I'm not convinced by the Seq.Push function you have above because it would inevitably result in nested calls to Push, each of which has an active range-over-func statement in it, leading to a tower of iterators. This is demonstrably much less efficient than expressing the recursion using a T.all method, in part because each range-over-func statement must heap-allocate at least one variable.

(P.S. I hope @jba won't mind if I point out a comment from a recent review that includes an example of the difference in the dynamic behaviors of the two approaches.)

[DeedleFake]

All that said, I'm not convinced by the Seq.Push function you have above because it would inevitably result in nested calls to Push, each of which has an active range-over-func statement in it, leading to a tower of iterators. This is demonstrably much less efficient than expressing the recursion using a T.all method, in part because each range-over-func statement must heap-allocate at least one variable.

I was thinking about that as I rewrote the tree traversal example. That might be enough to not make this worth it. On the other hand, given the comment in the review, it might not be that uncommon for people to do this in a loop manually anyways. I had actually just done that recently myself. Maybe having a standard function/method to do it would allow the compiler to more easily recognize that situation and optimize it.

[adonovan]

All that said, I'm not convinced by the Seq.Push function you have above because it would inevitably result in nested calls to Push, each of which has an active range-over-func statement in it, leading to a tower of iterators. This is demonstrably much less efficient than expressing the recursion using a T.all method, in part because each range-over-func statement must heap-allocate at least one variable.

FYI: I just put together https://go-review.googlesource.com/c/tools/+/674438 to add a static check to gopls for this mistake.