Swift: The joy of sequences

I am really happy with how SE-0094 turned out. I helped with the paperwork but it was all Kevin Ballard‘s brain child, putting together the two new sequence functions. If you haven’t been playing with these yet, they’re available in the latest developer snapshots (both the main trunk and the public branch) and they’re delightful.

There are two variations:

public func sequence<T>(first: T, next: (T) -> T?) -> 
    UnfoldSequence<T, (T?, Bool)>

public func sequence<T, State>(state: State, next: (inout State) -> T?) -> 
    UnfoldSequence<T, State>

The first one just takes a value, and then keeps applying a function to it, the second allows you to store associated state, meaning you can build functions like this:

extension Sequence {
    // Not to spec: missing throwing, noescape
    public func prefix(
        while predicate: (Self.Iterator.Element) -> Bool) -> 
            UnfoldSequence<Self.Iterator.Element, Self.Iterator> {
        return sequence(state: makeIterator(), next: {
            (myState: inout Iterator) -> Iterator.Element? in
            guard let next = myState.next() else { return nil }
            return predicate(next) ? next : nil
        })
    }
}

The preceding example showcases a very rough preview of the prefix(while:) function that will appear when SE-0045 gets implemented. In this version, I used  sequence to generate a series of elements while a predicate returns true. And yes, a few items are still less than ideal: you have to use a full type signature when using inout parameters in a closure, so things get a little wordy.

If you were using the old AnySequence/AnyGenerator (or Sequence/AnyIterator) approach, you’d create the iterator separately. Something along these lines:

public func prefix(while predicate: (Self.Iterator.Element) -> Bool) -> AnySequence<Self.Iterator.Element> {
    var iterator = self.makeIterator()
    return AnySequence {
        return AnyIterator {
            guard let next = iterator.next() else { return nil }
            return predicate(next) ? next : nil
        }
    }
}

Incorporating the state into the sequence generator simplifies nearly any stream of data that’s more complex than a mathematical progression:

sequence(first: 1, next: { $0 + 2 })

You can imagine any kind of function being used here, whether additive, multiplicative, etc. Pairing prefix with sequence lets a few tiny fireworks get started:

Count to 10:

for i in sequence(first: 1, next: { $0 + 1 })
    .prefix(while: { return $0 <= 10 }) {
    print(i)
}

Powers of 3 to 59049:

for i in sequence(state: 0, next: { 
    (idx: inout Int) -> Int in
    defer { idx += 1 }; return Int(pow(3.0, Double(idx)))})
    .prefix(while: {return $0 <= 59049})
{
    print(i)
}

Speaking of wordiness, Swift still doesn’t support x^n exponentiation, and when chaining in this way, you can’t use trailing closure syntax due to compiler confusion.

Any further exercise in state-based sequences is left as an exercise for the reader because I’m busy making lunch for the family.

Update: Back from lunch, here you go.

typealias PointType = (x: Int, y: Int)
func cartesianSequence(xCount: Int, yCount: Int) -> UnfoldSequence<PointType, Int> {
    assert(xCount > 0  && yCount > 0, 
    "Must supply positive values to Cartesian sequence")
    return sequence(state: 0, next: {
        (index: inout Int) -> PointType? in
        guard index < xCount * yCount else { return nil }
        defer { index += 1 }
        return (x: index % xCount, y: index / xCount)
    })
}

for point in cartesianSequence(xCount: 5, yCount: 3) {
    print("(x: \(point.x), y: \(point.y))")
}

4 Comments

  • Can’t wait to get started using those 😀
    Do you really need the state version for exponentiation though? Wouldn’t something like sequence(first: 1, next: { $0 * 3 }) work? I’ll have to try this out.

  • I always thought this use of unfolding was cool:

    func toDigits(number: Int, base: Int) -> [Int] {
      return sequence(number) { n in
        defer { n /= base }
        return n > 0 ? n % base : nil
      }.reverse()
    }
    
    toDigits(1234, base: 10) // [1, 2, 3, 4]
    toDigits(7, base: 2)     // [1, 1, 1]
    • That is cool.

  • […] Erica Sadun: […]