Learning a new programming language is fun, and learning Swift has been no different. We’ve been covering, through brief tutorials, features that most Objective-C programmers will find to be new. As many have observed, Swift borrows from many different languages and brings the “best” features together in a single language. One such feature is generics.
Simply put a generic is code that is agnostic of type, that is, code that can work with any type. One of the most powerful forms of a “generic” is the generic algorithm, i.e., an algorithm that can be used with most any type. By far the most common “example” algorithm is that of sorting. It’s common because its easy-to-grasp (everyone understands sorting and its applicability to software), easy to implement, and actually a useful algorithm to have in ones toolbox.
We’ve been big fans of showing how Swift can be used as a general purpose scripting language on OS X, and this example will be no different. A reality check, however; Swift is not going to displace Python as a scripting language, but we were able to take this Python implementation of Quicksort and convert it into Swift in two shakes of a lamb’s tail.
For this tutorial, however, we’re going to use the most basic sorting algorithms of all, the venerable bubble sort. We like to think of the bubble sorting algorithm as the thing you’d come up with (perhaps on the back of a napkin) given no previous experience thinking about sorting. Let’s think about how to sort an array of Ints in Swift:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
func bubblesort(list:Array<Int>) { var swapped:Bool do { swapped = false for i in 0..list.count - 1 { if (list[i] > list[i+1]) { swap(&list[i], &list[i+1]) swapped = true } } } while swapped } |
The details of the algorithm aren’t necessarily important, but for completeness sake, let’s review it. So you have a list of integers, say: 10, 11, 8, 5, 27, 1, 25, and you want to sort them. Bubble sort says, okay, I will walk along this list one integer at a time, and when I find two integers next to each other that are out of order, I’ll swap them. Once I swap the two, I’ll move to the next pair. After I’ve done that over the whole list, I’ll come back around and do it again, until I haven’t swapped anything, thus knowing I’m done.
Thus in the first pass I compare 10 and 11, and since 10 is less than 11, I don’t have to swap them. Then I look at 11 and 8. 8 is less than 11, so I swap them giving me 10, 8, 11, 5, 27, 1, 25. Now I compare 11 and 5, and since 5 is less than 11, I swap them. And so on. The point is at the end (after passing through the list several times), I’ll have my sorted list: 1, 5, 8, 10, 11, 25, 27. For a visual representation of this happening, check out this cool animation of bubble sort in action.
That’s handy and all, but the bubblesort function we’ve written only handles Int arrays. If we wanted to handle a String array, we would have to duplicate the routine and change out Array for Array. “There has to be a better way!” you say? Of course there is. Enter generics.
We want to write a function that can sort an array of any type. An array of Strings, an array of Doubles, even arrays of object types we haven’t created yet. We do this all through generics. Here’s the definition of our new bubble sort function:
|
1 2 3 |
func bubblesort<T>(list:Array<T>) { // Everything else remains the same } |
Pay attention to the comment we wrote, “Everything else remains the same.” That’s right. The bubble sort algorithm doesn’t change just because we’re sorting SelfSealingStemBolts instead of Strings.
In theory you should be able to enter this code in a text editor and run it from the command line:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
import Foundation func bubblesort<T>(list:Array<T>) { var swapped:Bool do { swapped = false for i in 0..list.count - 1 { if (list[i] > list[i+1]) { swap(&list[i], &list[i+1]) swapped = true } } } while swapped } var listOfNumbers = [10, 11, 8, 5, 27, 1, 25] bubblesort(listOfNumbers) println(listOfNumbers) |
A side bar: to quickly run the code above and all of our examples, add the following to the end of your .bashrc (assuming you are using Beta2, adjust appropriately if not):
|
1 2 |
PATH="/Applications/Xcode6-Beta2.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/":$PATH alias swift='swift -sdk $(xcrun --show-sdk-path --sdk macosx) -i' |
Re-source your .bashrc, add the code to a file called ~/Documents/generics.swift and then just run swift ~/Documents/generics.swift. See our previous post for more details.
We said in theory the above code would work, but in reality it won’t. You will be greeted with the error:
error: could not find an overload for '>' that accepts the supplied arguments
Let’s think about what this means for a minute. Swift has to compile your code and determine how to accomplish the task you’ve requested, namely that Swift can take any type T and apply the algorithm you’ve provided. That algorithm happens to include the greater than comparison between two objects of this generic (there’s that word again) type we are calling T. So in effect, you are making an implicit statement about objects of type T, and that’s that they are comparable. With Swift you need to make that statement explicit, by telling the generic function that types you will be handling adhere to certain protocols. In our case we can use the Swift Standard Library protocol Comparable, like this:
|
1 |
func bubblesort<T:Comparable>(list:Array<T>) |
The inclusion of the :Comparable declaration here is critical, and it tells Swift that elements given to the generic function will implement the Comparable protocol, which requires the definition of the function less-than (and subsequently also provides greater-than, as well as less-than-or-equal and greater-than-or-equal).
With this addition we can now throw an array of integers or array of strings at our bubblesort routine. Since Int and String adhere to the Comparable protocol out of the box, things will “just work.”
Of course, we are not satisfied with sorting just integers and strings! We demand more! Enter our Element class, which holds information about an element, as in the periodic table of elements.
|
1 2 3 4 5 6 7 8 9 10 11 |
class Element : NSObject, Printable { var name:String var number:Int init(name:String, number:Int) { self.name = name self.number = number } override var description:String { return "\(self.name) (\(self.number))" } } |
With this basic definition we can do the following:
|
1 2 3 4 5 6 7 8 |
import Foundation // class Element { // } var e:Element(name:"Gold", number:79) println(e) |
and get Gold (79) printed. Note that we inherit from NSObject and implement the Printable protocol to enable our ability to override var description:String and utilize println to pretty-print our element.
Now, we want to create an array of Elements and sort them with our bubblesort routine:
|
1 2 3 4 5 6 7 8 9 |
var listOfElements = [Element(name:"Gold", number:79), Element(name:"Silver", number:47), Element(name:"Zinc", number:30), Element(name:"Titanium", number:22), Element(name:"Plutonium", number:94)] bubblesort(listOfElements) println(listOfElements) |
This isn’t going to work, and it should be painfully obvious as to why, but Swift will tell you if its not obvious: error: cannot convert the expression's type '()' to type 'Comparable'.
Our bubblesort function says “I accept generic types that adhere to the Comparable protocol”. We have passed in a class that adheres to Printable, but we’ve said nothing about Comparable. So let’s go back add see if we can trick Swift by just adding Comparable to the class definition.
|
1 |
class Element : NSObject, Comparable, Printable { |
If you are following along executing Swift code in the terminal you will see all manner of hell break loose trying to run that. We stopped counting how many notes Swift tossed out, but they are all along the lines of candidate has non-matching type (X, X) -> Bool. In short, the compiler is telling you, I have looked high and low trying to match global comparison functions to your class, but I can’t. We have declared our class to follow the Comparable protocol, but didn’t back it up with an implementation as to what it means to compare two elements. So we have to do that.
So, what does it mean to compare two Elements? We aren’t chemists (thank God), so we’ll just make something up for illustration and say that “a given element X is less than a given element Y if the atomic number of X is less than the atomic number of Y”. That’s a fancy way of saying, “elements are sorted by their atomic number.”
To implement, we add the following outside the class body:
|
1 2 3 |
func < (lhs:Element, rhs:Element) -> Bool { return lhs.number < rhs.number } |
Now Swift will have a function that “matches” when it goes looking for something to fulfill the Comparable protocol for Element. The code embodies what we wrote out, and lhs and rhs are simply abbreviations for “left-hand side” and “right-hand side”, meaning of the equation.
We are almost done. When declaring yourself to adhere to the Comparable, you are also declaring support for the Equatable protocol, which requires you to define == (equality). So, we oblige with:
|
1 2 3 |
func == (lhs:Element, rhs:Element) -> Bool { return lhs.number == rhs.number } |
Add it all up and you should have:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
class Element : NSObject, Comparable, Printable { var name:String var number:Int init(name:String,number:Int) { self.name = name self.number = number } override var description: String { return "\(self.name) (\(self.number))" } } // Support Equatable func == (lhs:Element, rhs:Element) -> Bool { return lhs.number == rhs.number } // Support Comparable func < (lhs:Element, rhs:Element) -> Bool { return lhs.number < rhs.number } // Generic Bubblesort func bubblesort<T:Comparable>(list:Array<T>) { var swapped:Bool do { swapped = false for i in 0..list.count - 1 { if (list[i] > list[i+1]) { swap(&list[i], &list[i+1]) swapped = true } } } while swapped } var listOfElements = [Element(name:"Gold", number:79), Element(name:"Silver", number:47), Element(name:"Zinc", number:30), Element(name:"Titanium", number:22), Element(name:"Plutonium", number:94)] bubblesort(listOfElements) println(listOfElements) |
Run this code and see the magic:
[Titanium (22), Zinc (30), Silver (47), Gold (79), Plutonium (94)]
To recap: Swift’s support of generics allows us developers to write algorithms and data structures that are not bound to a concrete type or the type’s implementation. In the above example we explored only the generic algorithm, but Swift also supports generic types for implementing data structures such as stacks, queues, etc. We will admit, the syntax can be a bit daunting (too many brackets!) and Terse (get it?), but with patience and perseverance you’ll be writing your own generic data structures and algorithms in no time.
Now, we promised an implementation of Quicksort in Swift using generics. You can find a full example on Pastebin.
Define data as an inout parameter:
func quicksort(inout list: Array, start:Int, end:Int) {Then when calling it you have to add an & before the call:
if (start < end) {var split = partition(&list, start, end)
quicksort(&list, start, split-1)
quicksort(&list, split+1, end)
}
}