# Tree walking with range-over-fun

### August 20, 2024

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)