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.
- The most important question facing the Swift community today: how do you split long function footprints over multiple lines? ↩
-
In fact, the Swift standard library docs explicitly state that
BoolandObjCBoolshould really only be the two types that ever implementBooleanType, so maybe you could say screw it and just make the predicate return aBool. That’s what the predicates for std lib functions likefilterdo. But then, that wouldn’t make for quite so educational a blog post. ↩ -
You might be thinking, I know, I’ll extend
CollectionType! ButCollectionTypeis 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). ↩
Airspeed Velocity 