Generic Collections, SubSequences and Overloading

So, you’ve figured out the whole indices versus distances situation, and now you’re feeling pretty happy and you start trying out some more generic collection algorithms. And before long you smack your head against one of the more confusing things about generic collections: a sequence’s SubSequence doesn’t necessarily contain the same element type as that sequence. This usually manifests itself in one of those compiler errors that has you yelling “what are you talking about you infernal machine” at the compiler before eventually realizing what you’ve done wrong and sheepishly fixing it.

For example, suppose you want to find the location of the first subsequence in a collection. Like indexOf, but for another sequence rather than an element. The simple brute-force approach would be to iterate over every subsequence, trying to match it. Something like this – except it won’t compile:

extension CollectionType
  where 
  Generator.Element: Equatable {

    func search<
      Other: SequenceType 
        where 
        Other.Generator.Element == Generator.Element
    >(pattern: Other) -> Index? {

        for idx in self.indices {
            // error: cannot convert value of type 'Other' 
            // to expected argument type...
            if suffixFrom(idx).startsWith(pattern) {
                return idx
            }
        }
        return nil
    }
}

Until you know why, this can be very confusing. You’ve constrained the other sequence to have the same elements as the collection, so why can’t you use startsWith on it?

Except you’re not calling startsWith on Self. You’re calling it on Self.SubSequence, because that’s what suffixFrom returns – it’s a slicing operation. And SubSequence.Generator.Element isn’t guaranteed to be the same as Self.Generator.Element.

Here’s the relevant declaration:

protocol CollectionType {
    typealias SubSequence : Indexable, SequenceType = Slice<Self>
}

There’s nothing about this definition that forces the elements of SubSequence to be anything specific. Really, this needs a where clause on the typealias – something that Swift doesn’t currently support:1

protocol CollectionType {
    typealias SubSequence : Indexable, SequenceType
       // not (yet?) valid Swift
       where SubSequence.Generator.Element == Generator.Element
}

So, in the mean-time, the way around this is to specify any requirements like this as part of the declaration. A fix that might seem to work, but is over-constraining, would be to require subsequences be the same type:

extension CollectionType
  where
  Generator.Element: Equatable,
  SubSequence == Self {
    // etc
}

This would compile, and it would work fine with types whose slices are the same type as themselves, like strings:

// a slice of a String.CharacterView is
// a String.CharacterView, so this is fine 
"hello".characters.search("ll".characters)

but not for arrays, who have an ArraySlice type, or arbitrary collections, that have the default Slice implementation.

// "type of expression is ambiguous without more context", apparently
[1,2,3,4].search(2…4)
// "ambiguous reference to member '..<'" uhhh what?
(0..<5).search(2...4)

Instead, you can constrain the elements to be the same while allowing the slice type itself to differ:

extension CollectionType
  where
  Generator.Element: Equatable,
  // guarantee subsequences contain the same element
  SubSequence.Generator.Element == Generator.Element {
    
    func search<
      Other: SequenceType
        where
        Other.Generator.Element == Generator.Element
    >(pattern: Other) -> Index? {
            
            for idx in self.indices {
                // and now this line will happily compile...
                if suffixFrom(idx).startsWith(pattern) {
                    return idx
                }
            }
            return nil
    }
}

[1,2,3,4].search(2...4) // returns 1
(0..<5).search([3,4])   // returns 3

Optimizing for Random Access

It’s often the case that you can optimize a collection algorithm if you know it has random access. For example, given the above algorithm, you can tweak it to avoid searching for a pattern that is longer than what remains of the collection, so long as both the collection and the pattern are random access and therefore able to calculate their lengths (and the lengths of their collection) in constant time. OK, maybe it’s not Boyer-Moore, but it’s better than nothing and the code to do this is pretty simple, in fact it’s more constraints than code at this point:

extension CollectionType
  where
  Generator.Element: Equatable,
  Index: RandomAccessIndexType,
  SubSequence.Generator.Element == Generator.Element {
    func search<
      Other: CollectionType
      where
      Other.Index: RandomAccessIndexType,
      Other.Index.Distance == Index.Distance,
      Other.Generator.Element == Generator.Element
    >(pat: Other) -> Index? {
            
        // if pattern is longer, this cannot match, exit early
        guard !isEmpty && pat.count <= count else { return nil }
        
        // otherwise, search from the start up to the 
        // end less the space for the pattern
        for i in startIndex...endIndex.advancedBy(-pat.count) {
            // check if a slice from this point
            // starts with the pattern
            if self.suffixFrom(i).startsWith(pat) {
                // if it does, we've found it
                return i
            }
        }
        // otherwise, not found
        return nil
    }
}

(one part of the where clause, Other.Index.Distance == Index.Distance, is maybe overconstraining, but the alternative would be fiddling around with casts – non-Int distances aren’t exactly common, even Bit’s distance is an Int).

We’ve talked about overload priority a long time ago, and it still pertains even with protocol extensions. The most specific function wins. Here, if your two collections are random access, this version will be called because it is more tightly constrained than the first version. So:

// calls the version that works for any index
"hello".characters.search("ll".characters)
// calls the version optimized for random-access
[1,2,3,4].search(2…4) // returns 1?

Now, there is a potentially nasty bug you could stumble into here, and the compiler won’t save you from it. Try removing the constraints requiring the indices be random access on the second version. It still compiles! Except, now this version will be called strings as well. But in the case of non-random indices, it’s not an optimized version, it’s potentially slower. The reason being, pat.count and endIndex.advancedBy aren’t constant time, they’re linear, because they involve incrementing the index one by one. Now it could be worse – at least it’s not accidentally quadratic, but other examples could easily be (imagine implementing a sort that assumed constant-time advance but didn’t get it), so it’s something to watch out for.

Protocols, Extensions and Dynamic Dispatch

Once upon a time, it was harder to have made this mistake. In earlier versions of the standard library there were two ways to advance an index: a free advance function, that was O(1) for random access indices and O(n) otherwise, and then there was an advancedBy method on only the RandomAccessIndexType.

As part of the great extensionizing, the free advance function went away, and advancedBy moved into ForwardIndexType. So now you can call it on any index type, but you’ll get different performance characteristics depending on the type you call it on.

If you look at the declaration of ForwardIndex.advancedBy, you’ll see that it’s declared twice. Once inside the protocol:

public protocol ForwardIndexType : _Incrementable {
    public func advancedBy(n: Self.Distance) -> Self
}

and then again just below, as an extension:

extension ForwardIndexType {
    public func advancedBy(n: Self.Distance) -> Self
}

This seems a little weird. Why declare it twice? Why not just declare it once as an extension? It has to do with static versus dynamic dispatch, and which actual implementation is called.

To show this, let’s create our own toy index, initially without random access:

struct MyIndex {
    let i: Int
}

extension MyIndex: BidirectionalIndexType {
    func successor() -> MyIndex {
        print("successing!")
        return MyIndex(i: i+1)
    }
    func predecessor() -> MyIndex {
        print("predecessing!")
        return MyIndex(i: i-1)
    }
}

// indices need to be Equatable
func == (lhs: MyIndex, rhs: MyIndex) -> Bool {
    return lhs.i == rhs.i
}

I’ve put prints in there so you can tell when the functions are called. Now, this index type will have the default advancedBy implementation, which just calls successor() multiple times. And because of the print, you can see it happening:

func castHolyHandGrenadeOfAntioch<
  I: ForwardIndexType
>(idx: I) {
    idx.advancedBy(3)
}

let idx = MyIndex(i: 1)
castHolyHandGrenadeOfAntioch(idx)
// prints “successing!” 3 times

OK, now, we conform the type to be random access by giving it advance and distance functions:

extension MyIndex: RandomAccessIndexType {
    func advancedBy(n: Int) -> MyIndex {
        return MyIndex(i: i+n)
    }
    func distanceTo(end: MyIndex) -> Int {
        return end.i - i
    }
}

and now, when we call the castHolyHandGrenadeOfAntioch, we see nothing printed. Instead, even though the function only required a forward index, it uses the better advancedBy implementation of the random-access index.

But… this only works because advancedBy had been declared in the original ForwardIndexType protocol declaration. If, on the other hand, we added another method as an extension to different index types – say, a retreatedBy function – this would not happen.

First, let’s do that for BidirectionalIndexType:

extension BidirectionalIndexType {
    // just an example, you don't have to do this!
    // since BidirectionalIndexType also supports
    // advancedBy(-distance)
    func retreatedBy(n: Distance) -> Self {
        var i = n
        var result = self
        // since Distance isn’t strideable, this
        // is a rare case where you might mourn the
        // loss of C-style for and the ++ operator…
        while i > 0 {
            result = result.predecessor()
            i -= 1
        }
        return result
    }
}

and then, an optimized version for RandomAccessIndexType:

extension RandomAccessIndexType {
    func retreatedBy(n: Distance) -> Self {
        return self.advancedBy(-n)
    }
}

But now, if we repeat our earlier experiment but calling this function, we get a different result:

// only requires bidirectional access
func runAway<I: BidirectionalIndexType>(idx: I) {
    idx.retreatedBy(10)
}

// and even though MyIndex is random access
let braveSirRobin = MyIndex(i: 10)

// the bidirectional version is called...
runAway(braveSirRobin)
// prints “predecessing!” 10 times

So we can see the difference between default implementations that are also declared as part of the protocol, versus ones just created as extensions. With the former, generic functions get to take advantage of specialized implementations, whereas with the latter, only the implementation that matches the generic constraint will be called. This is why you often see functions declared twice in the standard library. For example, on SequenceType, underestimateCount is declared like this, so that if you pass in a collection to a function that takes a sequence, it can check it’s length if it’s a collection, without risking consuming the sequence.


  1. That’s assuming that there isn’t a legitimate reason to vary elements in subsequences which I don’t… think… there is? 

Sorting Nibbles in Swift

A couple of months back, John Regehr posted a challenge on his blog – write the fastest possible sorting algorithm for all the nibbles in a 64-bit word.

The problem is to sort the 4-bit pieces of a 64-bit word with (unsigned) smaller values towards the small end of the word. The nibble sort of 0xbadbeef is 0xfeedbba000000000. The function you implement will perform this sorting operation on a buffer of 1024 64-bit integers:

void nibble_sort(unsigned long *buf);

The challenge was in C, but it made me wonder about solving the same problem in Swift. Here’s a straight port of the supplied reference version in Swift:

func read_nibble(w: UInt64, i: UInt64) -> UInt64 {
    let res = w >> (i * 4)
    return res & 0xf
}

func write_nibble(inout w: UInt64, i: UInt64, v: UInt64) {
    var mask: UInt64 = 0xf
    mask <<= (i * 4);
    w &= ~mask
    var prom = v;
    prom <<= (i * 4)
    w |= prom
}

func nibble_sort_word_ref(var arg: UInt64) -> UInt64 {
    for var i: UInt64 = 0; i < 16; ++i {
        var min = i;
        for var j = i+1; j < 16; ++j {
            if read_nibble(arg, j) < read_nibble(arg, min) {
                min = j
            }
        }
        if (min != i) {
            var tmp = read_nibble(arg, i)
            write_nibble(&arg, i, read_nibble(arg, min))
            write_nibble(&arg, min, tmp)
        }
    }
    return arg;
}

func nibble_sort_ref(buf: UnsafeMutablePointer<UInt64>) {
    for var i=0; i<1024; i++ {
        buf[i] = nibble_sort_word_ref(buf[i])
    }
}

The first bit of good news is that on my machine, when compiled with -Ounchecked, this version performs with pretty much the same speed as the original C version. Sticking with -O instead gives up about ~20% performance, which is not too bad for the sake of safety.

So, this version has two functions to read and write the nibble at a given index, and a function to sort it using them. Get/set at a given index? That sounds a lot like a collection type. What if we were to wrap the word in a collection, and use subscript instead of the read/write functions? Something like this:

struct NibbleCollection: MutableCollectionType {
    var val: UInt64
    
    var startIndex: UInt64 { return 0 }
    var endIndex: UInt64 { return 16 }
    
    subscript(idx: UInt64) -> UInt64 {
        get {
            return (val >> (idx*4)) & 0xf
        }
        set(n) {
            let mask = 0xf << (idx * 4)
            val &= ~mask
            val |= n << (idx * 4)
        }
    }
    
    typealias Generator = IndexingGenerator<NibbleCollection>
    func generate() -> Generator { return Generator(self) }
}

Once you have this, you can then use the standard library sorting function on it to implement the challenge:

func nibble_sort_word_col(arg: UInt64) -> UInt64 {
    var col = NibbleCollection(val: arg)
    sort(&col)
    return col.val
}

“Does all this Collection overhead mean it won’t be as fast as the raw function implementation?” you might worry. But there really is no overhead – since NibbleCollection is a struct, not a class, it really isn’t anything more than the raw underlying UInt64 and some functions. All of the scaffolding sloughs away at compile time, leaving you with pretty much identical code to the function-based version.

With one big difference: Swift.sort is way better than the reference sort implementation above.1 So this version outperforms it, both in Swift and in C. With -O, the collection version is faster than the Swift reference, and the same speed as the C version. With -Ounchecked it outperforms the C version by about 25%.

Which tells you two things you should bear in mind when writing Swift:

  1. Structs implementing protocols, and generic functions, are a good way of getting abstraction without giving up performance.
  2. Always check if the code you want exists as a library function. Using it won‘t just save time and make your code clearer, it could be better optimized than the version you might write.

Of course, the competitive entries in C were orders of magnitute faster than the reference version, using bit-twiddling techniques like bucket sorts and lookup tables that take advantage of the problem being constrained to values less than 16 held in a single word. But since Swift also supports most of the operations they use, many of them can be ported too. A quick and dirty translations I did of a couple of the simpler ones suggests that, like the reference version, Swift can match or almost match them in performance too.


  1. Naming the two sort algorithms in question is an exercise for the reader. They might not be the one you’d guess first. 

Always write a generalized version of your algorithm

Suppose you want to find the minimum value in an array. Well, the Swift standard library has you covered:

let a = [6, 2, 4, 7, 8, 10]
minElement(a)  // returns 2

Ok that’s cool. But suppose you have an array of strings of integers and you want the minimum numeric value.

Well, I guess you could map them to Int and then use the same function:

let a = ["6", "2", "4", "7", "8", "10"]
minElement( a.map { $0.toInt() })

Nope, compiler error. String.toInt returns an Int?, because maybe the string isn’t a number.

Fair enough. I happen to know with my intimate knowledge of the problem domain that we can just ignore non-numeric values. So maybe filter those out?

minElement( a.map { $0.toInt() }.filter { $0 != nil } )  // hmmm

Nope, more compiler errors, because now we have only non-nil values, but they’re still optionals and an Int? doesn’t conform to Comparable. So maybe another map to force-unwrap the results (force unwrap is OK because the filter will guarantee no non-nil elements):1

minElement( a.map{ $0.toInt() }.filter { $0 != nil }.map { $0! } )  // yuck

Ok that compiles now and does return the minimum numeric value. But what if we wanted the result to still be a string?

"\(minElement( a.map{ $0.toInt() }.filter { $0 != nil }.map { $0! } ))" // bleurgh

That’s pretty horrible, and at this point I’m thinking of registering GiveUpAndUseAforLoop.com,2 and Marco Arment is yelling at you kids with your new language to get off his lawn.

Really, what we need is for minElement to take a predicate instead of only using the default <. It doesn't (mutter, grumble) but if it did, we could write this:

minElement(a) {
    switch ($0.toInt(), $1.toInt()) {
    case (_, nil): return true
    case (nil, _): return false
    case (let i, let j): return i < j
    }
}

Ahh. Faith in the functional programming style restored.3 This takes each element, checks if the toInt() of either is nil using pattern matching, always preferring the non-nil version, and if neither are, compares them. Since all it's doing is comparing the converted value, not returning one, the minimum returned is a string.4

There's nothing stopping you from implementing your own overload of Apple's minElement that takes a predicate:5

func minElement
  <E, R: Sequence
  where E == R.GeneratorType.Element>
  (range: R, pred: (E,E)->Bool) -> E {

    var gen = range.generate()
    var min_so_far = gen.next()!

    while let next = gen.next() {
        if(pred(next,min_so_far)) {
            min_so_far = next
        }
    }

    return min_so_far
}

This version copies the Swift library version's questionable practice of exploding in flames if you pass it an empty sequence – the (better?) alternative being make the return value optional to force the caller to acknowledge this possibility.

The moral here is that if you ever write a high-order function, write it as generally as possible. It's only a few extra lines to declare the common case using the general case:6

func minElement
  <E: Comparable, R: Sequence
  where E == R.GeneratorType.Element>
  (range: R) -> E {
    return myMinElement(range, <)
}

Apple does this for most functions (such as sort), just not minElement. But then it is only beta 3, hang in there.


  1. “I thought it was guaranteed not to be nil at this point” is what you could write to the log file in the outer exception handler you can’t have. 
  2. Just kidding, I didn’t think about it, I registered it straight away. 
  3. This code would be even neater if the Swift switch statement would implicitly return the values of single-line cases, i.e. if all the returns in that closure were removed, the switch would evaluate to the value of the selected case statement, and the closure would return it. They closed my radar as a dupe of 16169366 (don't file another duplicate though). 
  4. It's still not perfect – if none of the elements are numeric, it'll return the first one. Also, it'll convert each element twice. Hold that thought for a later post though. 
  5. Actually, there might be some compiler bugs stopping you, but I'll leave you to discover those on your own. 
  6. If the language would let you, you could even default the last parameter to <, but it won't, so you can't. More dynamic default arguments (including ones derived from other arguments to the same function) could be pretty useful in cutting down the amount of code you need to write for these general- and special-case versions. 

Writing Algorithms on Collections in Swift

edit: this post has been updated to Swift as of Xcode 6.1 (Swift 1.1).

Suppose you want a new algorithm that checks if every member of an array fulfills a given criteria.

Your first thought might be to add it as an extension of Array:1

extension Array {
    func all_of<B: BooleanType>
        (predicate: (Element) -> B) -> Bool {
            for e in self {
                if !predicate(e) {
                    return false
                }
            }
            return true
    }
}

This function takes a predicate (a function that takes an element and returns true or false), and applies it to every member of the array, only returning true if it was true for every member.

Note we specify a template argument, B: BooleanType, that allows the predicate to return not just a Bool but any type that can behave like a Bool (such as ObjCBool)2.

We can test it works easily:

let isEven = { ($0 % 2) == 0 }
let mixed = Array(1...4)     // [1, 2, 3, 4]
let doubled = map(1...4) { $0 * 2 }
let evens = Array(doubled)   // [2, 4, 6, 8]

mixed.all_of(isEven)  // false
evens.all_of(isEven)  // true

Incidentally, the above shows a nice trick that’s useful for testing collection algorithms, which is that arrays can be initialized with sequences, such as ranges. So if you quickly want an array of increasing numbers, you can write Array(begin...end). If you want something more complicated, you can pass a range to map or filter to alter the range first.

This implementation is nice because it’s now built into Array, but there are a few downsides.

Firstly, what if you wanted a slightly different version all_of_equal, that just took a value and confirmed if every entry was equal to that value? You’ll need to test for equality, so Element will need to be Equatable. You might think you’d specify a function that goes like this:

extension Array {
    func all_of_equal<Element: Equatable>
    (value: Element) -> Bool {
        return self.all_of { $0 == value }
    }
}

Nope, that won’t work. The problem is that you can’t further constrain Element within Array to be Equatable. What if you created an array of something that didn’t conform to Equatable? Would this no longer be allowed now you’ve added this method? Or should this method not be callable? Neither of these are palatable so the language just won’t let you do it.

Instead, you need to define a non-member function that takes an Array and an Element. Then you can constrain that element as much as you like:

func all_of<E, B: BooleanType>
    (a: Array<E>, predicate: (E) -> B) -> Bool {
        for e in a {
            if !predicate(e) {
                return false
            }
        }
        return true
}

func all_of_equal<E: Equatable>
    (a: Array<E>, rhs: E) -> Bool {
        return all_of(a) { $0 == rhs }
}

In fact, because of Swift’s operator overloading, you can even give it the same name:

func all_of<E: Equatable>
    (a: Array<E>, rhs: E) -> Bool {
        return all_of(a) { $0 == rhs }
}

// calls the version that takes an equatable value
all_of([1,1,1], 1)

// calls the version that takes a closure
all_of([1,1,1]) { $0%2 == 1 }

The second benefit of defining this as a non-member function is you can generalize it to apply not just to arrays, but any kind of collection.3 To do this, you need to extend the generic parameter clause in a couple of ways:

func all_of<E, C: CollectionType, L: BooleanType
    where E == C.Generator.Element>
    (c: C, predicate: (E) -> L) -> Bool {
        for e in c {
            if(!predicate(e)) {
                return false
            }
        }
        return true
}

First, we swap out Array for a type of Collection, by specifying a generic placeholder C that must be a collection. Then, we further constrain the collection to contain types E, which are the type of input our predicate will take.

Strictly speaking, we don’t need to include the placeholder E. You could replace it in the predicate definition with C.Generator.Element. But you might find it’s cleaner to create a placeholder for it, especially if you apply further constraints to E.

Now, we can use this function on not just arrays, but any type of collection, such as ranges directly:

let isEven = { ($0 % 2) == 0 }
all_of(1...4, isEven)  // returns false

or other types of collection:

let doubled = map(1...4) { $0 * 2 }
all_of(doubled, isEven)  // returns true

There’s one final improvement that could be made. Collections implement the Sequence protocol, which also gives us enough to iterate over the elements, checking the predicate. So we could rewrite all_of even more generally:

func all_of<E, S: SequenceType, B: BooleanType
where E == S.Generator.Element>
(sequence: S, predicate: (E) -> B) -> Bool {
    for e in sequence {
        if(!predicate(e)) {
            return false
        }
    }
    return true
}

Because Sequences behave differently, we don’t need to mandate a ForwardIndex to make them work with the for.

There are some times you still want to use collections rather than sequences. If we were writing a different algorithm, say find_first_of, that we wanted to return an index into the collection of the first occurrence, we’d want to stick with an algorithm that works on collections. Also, collections imply deterministic results over multiple iterations, and consistent size, which some algorithms might rely on. But not in the case of all_of, so SequenceType is a better choice.


  1. The most important question facing the Swift community today: how do you split long function footprints over multiple lines? 
  2. In fact, the Swift standard library docs explicitly state that Bool and ObjCBool should really only be the two types that ever implement BooleanType, so maybe you could say screw it and just make the predicate return a Bool. That’s what the predicates for std lib functions like filter do. But then, that wouldn’t make for quite so educational a blog post. 
  3. You might be thinking, I know, I’ll extend CollectionType! But CollectionType is a protocol, and you can’t extend protocols with implementations. What you want is something like traits or mixins. Swift doesn’t have those (yet, hopefully).