A custom iterator pattern for Go

Posted on May 31 2012

I have been working on a substantial web application that will be deployed on Google AppEngine’s Go runtime. Learning and programming in Go has been a very rewarding experience. It is a terrific language. I feel enormously productive with it, and it’s easy to keep the whole thing in my head at one time. It is not without its foibles and hills to climb, of course. All languages have quirks and intentional design decisions that one runs up against.

In my case, I found myself needing to create a custom iterator for a type that I had created. My custom type Foo was commonly found in collections, and it is easy enough in Go to make a slice of any type: []Foo. I was able to iterate over the collections easily with Go’s range. I was all set.

Before long, I found myself needing to add a function that would take my []Foo as a receiver, but Go does not allow me to have a slice of anything as the receiver in a function definition:

func (this []Foo) Gronk() int {} // not allowed!

I needed to declare a type for my slice:

type FooList []Foo

I can now declare my method:

func (this FooList) Gronk() int {}

But now that the slice of Foo is its own type, I can no longer use it with range:

// where fooVals is a FooList populated with values...
for idx, val := range fooVals {} // not allowed!

Unfortunately, Go does not provide a mechanism that allows me to make my custom type compatible with range. In C#, I can have any class implement the interface IEnumerable, and it will work with for...in or any other iteration mechanism. I’ve always been a little uncomfortable with the idea that a basic language mechanism is tied to an interface that is imported from a DLL, but it is very pragmatic and works well. I wouldn’t hold my breath for Go to do something similar, so I knew that I’d have to find an alternative or roll my own iteration mechanism.

One alternative that I explored is turning FooList into a struct and exposing my slice as a public member:

type FooList struct {
    Items []Foo
}

With that, I could use range to iterate over fooListInstance.Items, but I didn’t really want to make the slice public. It’s probably a bit of an artificial restraint, as I am not writing the code to be part of a redistributable library, and I can probably trust myself not to abuse the compromise of encapsulation, but I decided to stand on principle and find a better solution.

I tried adding methods that would allow me to iterate over the items while keeping the slice private:

  • Reset() // Move to the beginning of the collection
  • HasNext() // is there another item available?
  • Next() // Get the next item in the collection.
That worked rather nicely until I found myself needing to use the collection with two simultaneous and different iteration points. I followed several different lines of inquiry and experimentation before settling on what I think is a very workable solution.

One of Go’s greatest features is its support for closures, first-class functions and higher-order functions. A good programmer can make a lot of beautiful magic happen with those capabilities, and they provided me with the answer that I needed.

Given a FooList definition of

type FooList struct {
    items []Foo
}

I add the following type and method:

type FooListIterator func() (Foo, bool)
// Calling the FooListIterator function returns a Foo and a
// bool that tells me if the returned value is valid. If it is false,
// I have iterated off the end of the list and the Foo has some
// useless default value.
func (this FooList) GetIterator() FooListIterator {
    return func(list []Foo) FooListIterator {
        index := 0
        return func() (Foo, bool) {
            if index >= 0 && index < len(list) {
                val := list[index]
                index++
                return val, true
            }
            return 0 ,false
        }
    }(this.items)
}

In my code, I use it like this:

func DoSomething(someFoos FooList) {
    iter := someFoos.GetIterator()
    val, good := iter()
    for good {
        // Do something useful with val
        val, good = iter()
    }
}

A complete example that you can play with and run is available in the Go Playground.

It’s not as neat and simple as range, but it seems to me that this approach is reasonably straightforward and pragmatic as well as flexible. I’m using it now in my large codebase, and I hope that it may provide some utility to my fellow Gophers.

Update:
While nosing around on the golang-nuts Google Group, I came across a post that asked the same question that I did, and lo-and-behold, Steve Blenkinsop came up with the exact same solution that I did. You can see his working example in the Go Playground. I think that it is wonderful that someone else had the same idea that I did, as it affirms my belief in the usefulness of the approach.