We’ve been looking at Go 1.23’s new range-over-func feature. And we’re just about through what the spec has to say about it. Except for one thing. The example code!

// iteration support for a recursive tree data structure
type Tree[K cmp.Ordered, V any] struct {
	left, right *Tree[K, V]
	key         K
	value       V
}

func (t *Tree[K, V]) walk(yield func(key K, val V) bool) bool {
	return t == nil || t.left.walk(yield) && yield(t.key, t.value) && t.right.walk(yield)
}

func (t *Tree[K, V]) Walk(yield func(key K, val V) bool) {
	t.walk(yield)
}

// walk tree t in-order
var t Tree[string, int]
for k, v := range t.Walk {
	// process k, v
}

Now anything but a straight-forward example of an iterator function if I ever saw one!

But we’re here to learn about Go, so let’s dissect this thing until it makes sense.

So Tree is a struct type, that defines a recursive tree data structure. And the method Walk defined on that type is the range-over-func iterator function. So let’s start there.

Walk accepts a single argument, yield, of type func(K, V) bool, meaning that Walk is of type iter.Seq2.

When Walk is called, it immediately calls an unexported method, walk, which has almost the exact same signature. And leads to the first WTF I experienced while reading this code: Why does t.walk return a bool value that’s ignored?

After consideration, it’s not actually ignored. Yes, t.Walk ignores the return value, but t.walk calls itself recursively, and does consider the value.

Second, the fact that t.walk returns bool affords the possibility of using boolean logic to turn it into a one-liner. Written without that, we’d have something like:

func (t *Tree[K, V]) walk(yield func(key K, val V) bool) bool {
	if t == nil {
		return false
	}
	if !t.left.walk(yield) {
		return false
	}
	if !yield(t.key, t.value) {
		return false
	}
	return t.right.walk(yield)
}

And honestly, I think this version is quite helpful to make it more explicit what’s going on. But also helps explain why it was written the way it was, because once it does make sense, of course you want to simplify!

So what is going on?

Well, for each node in the tree, we consider:

• Is the node nil? If so, we’re done (with that node), so we return false. Otherwise…
• Pass the yield callback to the node’s left child, which goes through this same checklist for that node. If that returns true…
• Call the yield call back with this node’s key and value, and check its return value to determine if we should continue iterating. If yield returns true…
• Pass the yield callback to the node’s right child, which goes through this same checklist for that node. If that returns true…
• Return control to the parent node, or to t.Walk, if this was the root node.

Does that all make sense?

I hope so. Spend a few minutes going over it if you need to.

While I think this is a rather arcane example to include in the spec, it is an interesting one to be sure.

Quotes from The Go Programming Language Specification Language version go1.23 (June 13, 2024)