Generators in Swift

In my last post on Swift I examined sequences and generators. Today we’ll implement our own sequence.

Many languages have a function like Clojure’s interpose, which takes an item and a sequence, and inserts the item between each two subsequent elements of the sequence:[1]

Array(interpose("in", ["San Francisco", "California", "the USA"]))
=> ["San Francisco", "in", "California", "in", "the USA"]

There are three things we need here: The interpose function itself, which must return a Sequence, which, in turn, generates a Generator, which does the actual work of producing the items.

Let’s start with the Generator:

struct InterposeGenerator<G: Generator, T where T == G.Element>
        : Generator {
    let sep: T
    var gen: G
    var needSep: Bool
    var nextOrNil: T?

    init (sep: T, gen: G) {
        self.sep = sep
        self.needSep = false
        self.gen = gen
        self.nextOrNil = self.gen.next()
    }

    mutating func next() -> T? {
        if needSep {
            needSep = false
            return sep
        } else {
            let n = nextOrNil
            if n {
                nextOrNil = gen.next()
                needSep = nextOrNil != nil
            }
            return n
        }
    }
}

InterposeGenerator is a little state machine that alternates between producing either an element of the original generator or the separator. A bit of care is required to make sure that it doesn’t produce the separator again after the generator is exhausted.

One noteworthy thing here is the invocation of self.gen.next() in init. If we try to call next on the constructor argument gen instead of the property self.gen we get a compiler error:

immutable value of type 'G' only has mutating members named 'next'

This makes sense: the Generator is a value type, and it’s passed in here as an argument, which apparently makes it immutable, and next is a mutating function. At least, that is how it would typically happen—the compiler doesn’t seem to have any information to that effect, though. Generator is a protocol, which can be implemented by reference as well as value types:

protocol Generator {
    typealias Element
    func next() -> Element?
}

As you can see, next is not marked as mutating, either. I suspect there are two things going on here: the protocol definition that Xcode shows is probably incorrect, in that the mutating modifier is missing. The definition that Swift actually uses contains the modifier. In addition, the compiler doesn’t know whether the Generator we are using to create InterposeGenerator is a value type or not, so it must assume that it is, for the sake of safety in the case of mutating functions.

Let’s move on to the Sequence. It doesn’t really have to do anything other than creating an InterposeGenerator when asked to, so apart from all the type fiddling involved it’s rather simple:

struct InterposeSequence<S: Sequence, T
                         where T == S.GeneratorType.Element>
        : Sequence {
    let sep: T
    var seq: S
    func generate () -> InterposeGenerator<S.GeneratorType, T> {
        return InterposeGenerator(sep: sep, gen: seq.generate())
    }
}

Finally, the interpose function just creates an InterposeSequence:

func interpose<S: Sequence, T
               where T == S.GeneratorType.Element>
        (sep: T, seq: S) -> InterposeSequence<S, T> {
    return InterposeSequence(sep: sep, seq: seq)
}

It seems to be a pattern in the base library for the Sequence and Generator to be implemented in the same type, which we could easily do here, as well. I’ll leave it as an exercise for the reader.

Languages with a yield operator, like C# or Python, allow sequence generation to be expressed much more succinctly, with the compiler taking over the task of managing the state machine:

static IEnumerable<T> Interpose<T> (T sep, IEnumerable<T> seq) {
    var en = seq.GetEnumerator ();
    if (!en.MoveNext ())
        yield break;
    for (;;) {
        yield return en.Current;
        if (!en.MoveNext ())
            yield break;
        yield return sep;
    }
}

  1. It doesn’t modify the original sequence, of course, but rather returns a new one.  ↩

5 thoughts on “Generators in Swift

  1. Very insightful post. Thank you! In the WWDC Advanced Swift session at 32:00, David Abrahams notes “some popular languages” implement generics with “Any” plus downcasts. I was wondering if having a yield operator, while being a more succinct mechanism, forces some kind of type erasure to happen.

    • I don’t know of any connection between a `yield` operator and generics. C# has `yield` and doesn’t do type erasure. But maybe we’re talking about different things?

Comments are closed.