Collection and Sequence Helpers

Before the next installment about laziness, an aside about sequence and collection helpers.

In the previous article, I used a couple of helper objects to generate sequences without having to implement a whole sequence class. The Swift standard library provides quite a few of these, which I describe below.

I’m omitting the view classes returned by lazy, map, filter, enumerate and reverse, as they are tightly associated with their creating function and probably shouldn’t be used as stand-alone things.

CollectionOfOne
When you have a single variable, and you want a collection containing just it (for example, you want to pass it into a function that expects a collection).

CollectionOfOne uses GeneratorOfOne (see below) as its generator.

let i = 42
let just_one = CollectionOfOne(i)
just_one[just_one.startIndex] // returns 42
countElements(just_one) // returns 1
just_one.element // returns 42

EmptyCollection
When you want an empty collection containing none of a specific type. This is only really useful when you specifically don’t want that collection to be an Array for some reason (like in a unit test).

EmptyCollection uses EmptyGenerator (see below) as its generator.

let empty = EmptyCollection<Int>()
countElements(empty) // returns 0

EmptyGenerator
Has no public init, psych! Use GeneratorOfOne, see below.

GeneratorOf: Use Case 1
When you want a generator that serves up elements based on a closure you supply.

var infinite_ones = GeneratorOf { 1 }
infinite_ones.next() // returns 1?
infinite_ones.next() // returns 1?

var i = 0
var naturals = GeneratorOf { ++i }
naturals.next() // returns 1?
naturals.next() // returns 2?
naturals.next() // returns 3?

GeneratorOf: Use Case 2
When you want to treat different generators that generate the same type as all the same type. GeneratorOf has an init that takes other types of generators and returns the same type based only the type of their Element.1

let r = 1...3
let rg = r.generate()

let a = [11, 22, 33]
let ag = a.generate()

// this won't compile, rg and ag 
// are different types
var generators = [rg, ag]

let g_of_rg = GeneratorOf(rg)
let g_of_ag = GeneratorOf(ag)
// this array will be of type [GeneratorOf<Int>]
var gofgenerators = [g_of_rg, g_of_ag]
gofgenerators[0].next()  // returns 1?
gofgenerators[1].next()  // returns 11?

GeneratorOfOne: Use Case 1
When you want to serve up a single value once from a generator.

let i = 42
var just_one = GeneratorOfOne(i)
just_one.next() // returns 42?
just_one.next() // returns nil

GeneratorOfOne: Use Case 2
When you want to serve up no values from a generator. If you pass in a variable set to nil, it will act like an EmptyGenerator.

let i: Int? = nil
// GeneratorOfOne.init takes T?, unlike 
// CollectionOfOne.init which takes T
var none = GeneratorOfOne(i)
// 'none' is now a GeneratorOfOne<Int>
// that returns no values.
none.next() // returns nil

GeneratorSequence
When you have a generator that isn’t a sequence, but you need a sequence.

let st = stride(from: 1, to: 7, by: 2)
// StrideTo's generator is a rare example
// of a Generator that isn't also a Sequence.
let stg = st.generate()

for i in stg {
    // compiler error, stg
    // is not a Sequence
}

for i in GeneratorSequence(stg) {
    // works OK
}

Be careful! The example above is fine, because the GeneratorSequence is created for a single use and then disposed of. GeneratorSequence doesn’t bestow magical resetting properties on the generator you give it. If you hand over a GeneratorSequence to some other function that requires a Sequence, that function could try and walk the sequence multiple times, which will have undefined results depending on what kind of generator it is. Generators that don’t declare they’re also Sequences probably don’t for a reason.

IndexingGenerator
When you’re implementing a collection, and the generator doesn’t need to do anything more fancy than use the startIndex and subscript methods to serve up each value. Most of the standard library collections use it.

The tiniest working toy collection. Isn’t it cute:

class TenInts: Collection {
    var startIndex: Int { return 0 }
    var endIndex: Int { return 10 }
    subscript(i: Int)->Int { return i }
    typealias GeneratorType = IndexingGenerator<TenInts>
    func generate() -> GeneratorType {
        return IndexingGenerator(self)
    }
}

let ti = TenInts()
reduce(ti, 0, +) // returns 45

PermutationGenerator
When you have a collection, and you want a Sequence or Generator that is made up of elements of that collection served up in an arbitrary order.

let r = 1...10

let tail = PermutationGenerator(elements: r,
            indices: r.startIndex.successor()..<r.endIndex)
// sequence of 2...10

let every_third = PermutationGenerator(elements: r,
                    indices: stride(from: r.startIndex,
                                to: r.endIndex,
                                by: 3))
// sequence of 1, 4, 7

Repeat
When you want a collection of the same values repeated a specific number of times.

You can change the number of times later, but you can’t change the value that repeats.

var finite_ones = Repeat(count: 100,
                    repeatedValue: 1)
countElements(finite_ones) // returns 100
finite_ones.count = 200
countElements(finite_ones) // returns 200
finite_ones.repeatedValue = 2
// compilation error: 
// repeatedValue is read-only

Repeat uses an IndexingGenerator, and then uses endIndex to control how many elements are generated.

SequenceOf: Use Case 1
When you want a sequence whose generator can be based on a closure you supply.

The difference between GeneratorOf and SequenceOf is subtle. GeneratorOf takes a closure that returns the next value. SequenceOf takes a closure that returns a generator, which if you’re following expected behaviour, will be a freshly reset generator. Chances are you’ll want to use GeneratorOf as the return value of your SequenceOf closure:

let naturals = SequenceOf {
    // I can't get the type inference 
    // grooving here for some reason
    _ -> GeneratorOf<Int> in
    // new i to capture for each
    // fresh generator
    var i = 0
    return GeneratorOf {
        ++i
    }
}

// Can now create multiple
// independent generators:
var n1 = naturals.generate()
var n2 = naturals.generate()
n1.next() // returns 1?
n2.next() // returns 1?
n1.next() // returns 2?
n2.next() // returns 2?

Note, you do not have to wrap GeneratorOf inside SequenceOf just to make it a sequence. GeneratorOf implements Sequence. The big difference is, if you need to reset the generator on each call to generate because the closure has state, you need SequenceOf. If your desired sequence is stateless (say it is an infinite sequence of a single constant, or a infinite sequence of the current time), you only need GeneratorOf.

SequenceOf: Use Case 2
Similar to GeneratorOf, when you want to treat different sequences that generate the same type as all the same type. SequenceOf has an init that takes other types of sequences and returns the same type based only the type of their Element.

let a = [1, 2, 3, 4]
let b = lazy(a).filter { $0%2 == 0 }
// this won't compile, a and b are different types
let seqs = [a, b]
// this will, both elements are SequenceOf<Int>
let seqs = [SequenceOf(a), SequenceOf(b)]

So there you go. Hopefully some of these will save you some typing, if you plan on writing your own collections or sequences, or need to generate some makeshift ones on the fly.


  1. My guess is, the second init creates a closure that wraps the supplied generator and returns a GeneratorOf that calls it. That’s probably a pretty interesting idea to play with some other time. 

2 thoughts on “Collection and Sequence Helpers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s