Looking back at the classics: Generic data types in Swift (Part 2)
by Javier De Silóniz Sandino- •
- May 29, 2015
- •
- swift• generics• ios• abstract• data• types• stacks• code tutorials
- |
- 7 minutes to read.
Last week, we briefly discussed generic development in Swift and some of the things we can achieve with them. Specifically, we addressed how we can use this powerful feature to implement data types in our iOS and MacOS apps. Then we went back in time, riding in our DeLoreans to take a look at one of the greatest achievements in Computer Science, the discovery of a long-time friend of developers: the singly-linked list.
First, let’s dig a bit deeper into generics following the same structure as we’ve previously used. We’ll first explore how we can apply nuances to tell Swift our intentions while using generic types. Then, we’ll use our singly-linked list implementation to bring back another old pal from the past, the Stack!
Once again, we’re giving you the chance to play with the source code of this article. Just download our interactive playground and start changing stuff around!
Expressing ourselves better with generics
We’ve already learned how we can create small algorithms that take parameters of any kind of data, but there’s more we can do to express ourselves. For example, imagine we need a function that handles two data types for some reason:
func «algorithm»<T, U>(a: T, b: U) -> U {
// do your magic...
}
algorithm("fortyseven", 47)
algorithm(47, 47)
algorithm("foo", "bar")
»Several generic types|The <code>algorithm</code> function now takes two data types: <code>T</code> and <code>U</code>. Notice that we can use <code>T</code> and <code>U</code> not only in the parameters of the function but also in its return type. Swift will correctly infer the data types in the corresponding function calls below.«
When handling our generic data types, we can also ask the compiler to restrain them, forcing them to conform to certain protocols. Imagine that we have a function and we need to use the description property of a generic type. As you’ll already know, objects with a description computed property conform to the Printable protocol. So we can define our function like this:
func printDescription<T: «Printable»>(item: T) {
println(«item.description»)
}
«printDescription»(item: "47 Degrees")
«printDescription»(item: somethingNotConformingToDescription)
»Protocol conformation|We tell the compiler that we only want to have <code>Printable</code> types as our main data type, by using the colon symbol.«
»Access to methods|The compiler now knows that T will contain a <code>description</code> computed property, so we can use it freely in our code.«
»Compilation|This will compile OK, as String conform to Printable.«
»Compilation|However this function call won't be allowed by the compiler, as we're passing over an object that doesn't conform to Printable.«
By combining both features, we can start creating generic algorithms allowing us to transform our data with ease. For example, this would be a simplification of the signature of the map higher-order function in Swift:
func map<S : SequenceType, T>(source: S, transform: (S) -> T) -> [T]
That would read: “map takes two parameters: source is anything that conforms to the SequenceType protocol, and transform is a function that takes anything conforming to SequenceType and returns another type called T. This function also will return an array of things of type T.” In all actuality, if you read the documentation, this signature is a little more complicated. We’ll come back to it when we talk about associated types next week.
So now we know a little bit more about generics, and we have our cool singly-linked list that we implemented last week. Let’s use this knowledge and travel back in our time machines! This round we’ll let you choose between a DeLorean DMC-12 or a Chron-O-John, whichever time-travel reference floats your boat.
Meet the Stack
Stacks, as a theoretical concept, were first proposed by Alan M. Turing, and are even older than linked lists. Turing, you know, the genius that helped break the Enigma machine and created concepts such as the Turing machine and the Turing test . . . No big deal. Stacks just might be the most essential abstract data types in the history of computer science. There are stacks all around us: they handle the functions call inside your code, they live inside the CPU registers in your computer, and they even allow us to perform undo in our daily minion tasks!
Think of stacks as narrow baskets that can hold many items, but each basket must be piled on top of the others. So, if you want to get an item near the bottom of the stack, you have to take out the ones above it first. That’s called a LIFO as in “Last-In First-Out”. When you want to put something inside the stack you push it, and when you want to get something out of the stack you pop it. It’s THAT simple.
You can implement stacks using arrays, but if you think about it, it makes more sense to use a linked-list, doesn’t it? Performing a push, resemble our prepend operation (the cons method), and popping something out the stack would be as easy as separating the head of the list from its tail. We really don’t need anything else! So our stack will hold an internal list to make its magic work:
struct Stack<T> {
private var «internalList» : List<T>
init() {
self.internalList = List<T>()
}
private init(internalList : List<T>?) {
if let list = internalList {
self.internalList = list
} else {
self.internalList = List()
}
}
}
»Implementation using a list|We keep a private internal singly-linked list to handle our data. You'll notice that our <code>Stack</code> type is just going to be a reconceptualization of the list itself.«
Our stack has a public initializer to create an empty stack and a private one that we’ll be using to perform the pop operation. Now that we can create stacks, let’s implement our push and pop operations:
extension Stack {
func «push»(item: T) -> Stack {
return Stack(internalList: internalList.cons(item))
}
func «pop»() -> (item: T?, stack: Stack?) {
return (item: internalList.head, stack: Stack(internalList: internalList.next()))
}
func «top»() -> T? {
return self.internalList.head
}
var count : Int {
get {
return internalList.count
}
}
}
»Push operation|Pushing in terms of our list is directly translated as a <code>cons</code> operation.«
»Pop operation|When popping we perform two actions: return the head of the list as the popped item and the tail of the list as the popping-out resulting list.«
»Top operation|Letting the user peek at the top of our Stack can be done by just returning the head of the internal list.«
Again, it’s pretty straight-forward. We always operate on our internal list: when pushing, we prepend the new item to the list. When popping, we return the head and the tail of the internal list in a nice tuple. That’s about it! Of course, our methods return new stacks all the time, guaranteeing immutability. We’ve also added two convenience methods that return the top item and the number of elements in the stack. They’re not essential, but really useful. Now that we’ve got our stack ready, let’s use it!
var stack = Stack<Int>()
stack = «stack.push(0)»
stack = «stack.push(1)»
stack = «stack.push(2)»
let tuple = «stack.pop()»
let item = «tuple.item!»
stack = «tuple.stack»
»Push operation|<code>top -> 0 <- bottom|</code>«
»Push operation|<code>top -> 1, 0 <- bottom</code>«
»Push operation|<code>top -> 2, 1, 0 <- bottom</code>«
»Pop operation|<code>(item: Optional(2), stack: top -> 1, 0 <- bottom)</code>«
»Pop operation|<code>2</code>«
»Pop operation|<code>top -> 1, 0 <- bottom</code>«
As you can see, our Stack can be viewed as a reconceptualization of the list it stores. We don’t care if there’s a singly-linked list or an array behind the scenes (we could change our implementation to handle that case). When a user works with the stack itself, he/she will use the same operations, receiving the same results. In summary, generic development makes it really easy to encapsulate an existing data type to create a new one that better suits our needs.
Don’t forget that you can play with the source code by downloading the Playground file for this article. We look forward to hearing your thoughts or answering your questions if you have any! Contact us through Facebook, Twitter or the comments section below. Stay tuned for more generic goodness!