List Comprehensions and Performance With Swift

This post written on August 15, 2015 to be compatible with Xcode 6 and Swift 1.2

List comprehensions provide a concise way to create lists. You can accomplish list comprehension-like operations in Swift even though list comprehensions are not mentioned in the Swift language guide.

Say you want to create a list of squares, like:

var squares = [Int]()
for x in 1..<10 {
    squares.append(x*x)
}

In Python you could use a list comprehension instead

squares = [x**2 for x in range(10)]

In Swift you can do

let squares = Array(map(1..<10) { $0 * $0 })

To get the sum of all the elements in the list you could do this

var sum = 0
for square in squares {
    sum = sum + square
}

Or use the reduce function

let sum = squares.reduce(0, { $0 + $1 })

Like list comprehensions in some other languages, you can use any Sequence or Collection as the input, not just a Range.

You can use map/reduce/filter/stride depending on what kind of list you are trying to create.

The two main perks of list comprehensions are conciseness and being able to generate faster bitcode.

My imitation list comprehension was more concise. I was curious whether it would also generate faster bitcode.

This article showed me how to analyze Swift assembly code using Hopper, an OSX and Linux disassembler. You can try Hopper for free without buying a license.

The code snippets without list comprehensions and with the imitation list comprehensions generated the same assembly code.

The assembly code from Hopper

Since both snippets created the same assembly code I assumed their execution time would be the same. We can demontrate this by measuring the execution of our program using XCTest.

My test for the code snippet with no list comprehension

func testNoListComprehensionPerformance() {
    self.measureBlock() {
        var squares = [Int]()
        for x in 1...5 {
            squares.append(x)
        }
    }
}

The relevant output

Test Case '-[speedTestTests.speedTestTests testNoListComprehensionPerformance]' started.

:0: Test Case '-[speedTestTests.speedTestTests testNoListComprehensionPerformance]' measured [Time, seconds] average: 0.000, relative standard deviation: 236.965%, values: [0.000154, 0.000005, 0.000004, 0.000004, 0.000004, 0.000004, 0.000004, 0.000004, 0.000004, 0.000004], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
Test Case '-[speedTestTests.speedTestTests testNoListComprehensionPerformance]' passed (0.262 seconds).

My test for the code snippet with the imitation list comprehension

Test Case '-[speedTestTests.speedTestTests testSortaListComprehensionPerformance]' started.

:0: Test Case '-[speedTestTests.speedTestTests testSortaListComprehensionPerformance]' measured [Time, seconds] average: 0.000, relative standard deviation: 160.077%, values: [0.000045, 0.000005, 0.000004, 0.000003, 0.000003, 0.000003, 0.000003, 0.000004, 0.000003, 0.000003], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
Test Case '-[speedTestTests.speedTestTests testSortaListComprehensionPerformance]' passed (0.255 seconds).

On average they only differ by only 0.007 seconds.

The coolest application of list comprehensions I've seen is in a spelling corrector. Airspeed Velocity wrote a Swift version of Peter Norvig's Python spelling corrector.

Conciseness is the main benefit of using list comprehension-like operations in Swift. Paul Graham wrote a great essay about how conciseness in programming languages is power. Since each programmer can only write a certain number of lines of code per day, you can accomplish more each day if you can accomplish more in the same number of lines. This power also makes you rethink what programs are possible. In a more verbose language this spelling corrector example could have seemed like an overwhelming project. I love how how something as technically complex and mysterious as a spelling corrector can be expressed in so few lines of code in Swift.

Did this tutorial help you?

Support my Patreon

Your support on Patreon allows me to make better tutorials more often.

Subscribe via RSS

Function Currying in Swift

Function Currying in Swift

The concept of currying is that instead of accepting multiple arguments, a function accepts only one, and returns a function which acepts the remaining arguments. The returned function will also accept only one argument, and returns another function. This process continues until all arguments are exhausted and we are left only with a single return value.

For example, usually we define a function that returns the sum of two integers as follows:

func add1(x: Int, y: Int) -> Int {
    return x + y
}
add1(1, 2) // Output: 3

We can always transform a function taking multiple arguments into a curried one, by separating the function into a series of function that each takes only one argument. The curried version of add1 is as follows:

func add2(x: Int) -> (Int -> Int) {
    return { y in return x + y }
}
add2(1)(2) // Output: 3

This function has this type specified: Int -> Int -> Int. This may seem a little strange to newcomers to functional programming. Which part is the argument, and which part is the return type?

Here, add2 is taking an Int, and returning a Function which takes another Int, which in turn returns a third Int. You could say it’s something like this: Int -> (Int -> Int), or we could use typealias to make (Int -> Int) more clear:

typealias IntTransformer = (Int -> Int)

Now, any time we see IntTransformer, it’s easier to comprehend that it’s a function that transforms an Int value. With that, we could redfine add2 like this:

func add2Aliased(x: Int) -> IntTransformer {
...

This probably looks a little more familiar, but under the hood this is exactly the same as the add2 function we defined with the data type Int -> Int -> Int. This is just a more familiar looking way to write it.

Calling add2() with just a single argument returns a function that takes another (Int -> Int) function, which means we can store that function in a separate variable if we so choose:

let addTwentyTransformer = add2(20)
addTwentyTransformer(5) // Output: 25

Now, add2(20) is a function that takes one integer and returns the value of that integer plus 20.

The -> operator is defined as associativity right. Instead of writing A -> (B -> (C -> D)), we can simply write A -> B -> C -> D.

Swift also supports another way to define a curried function:

func add3(x: Int)(y: Int) -> Int {
    return x + y
}
add3(1)(y: 2) // Output: 3

This is helpful if you want named parameters, which can sometimes help your code easier to read. It’s also easy to make the syntax the same as add2 and remove the explicit argument name.

func add4(x: Int)(_ y: Int) -> Int {
    return x + y
}
add4(1)(2) // Output: 3

Benefits of Currying

What are the benefits currying provides? Let’s look at the add functions above.

With add1 the regular function, we cannot apply this function until both of its arguments are ready. With the curried add2, we can apply one or two arguments.

Let’s see an example that uses add1 and add2 with mapto transform an array of integers by adding 7 to each.

// Apply map to the array using the two functions
let xs = [1, 2, 3]
let addSeven1 = { add1($0, 7) }
map(xs, addSeven1) // Output: [8, 9, 10]
let addSeven2 = add2(7)
map(xs, addSeven2) // Output: [8, 9, 10]

The curried function add2 is much cleaner in this case.

There is another case when curried functions have obvious advantages. To demonstrate the example, first we define a function (a custom operator) that composes two functions together:

// Define a new operator |> that has left associativity
infix operator |> { associativity left }
func |> <A, B, C>(f: B -> C, g: A -> B) -> A -> C {
    return { x in
        f(g(x))
    }
}

Let’s say we want to transform an array of integers by adding 7 to each element, and then adding 3 again. We could write:

let xs = [1, 2, 3]
 
// Returns a function that adds three to it's only argument
let addThree = add2(3)
 
// Apply addSeven1 to every item in xs
// Then apply addThree to every item in that list
xs.map(addSeven1).map(addThree) // Output: [11, 12, 13]

It first adds 7 to each element in xs, wraps the results into a temporary array, then add 3 to each in the temporary array, and return the last results in a new array. This creates a temporary array that we never need.

By composing the curried functions, addSeven2 and addThree, we can eliminate the creation of the temporary array.

xs.map(addSeven1 |> addThree) // Output: [11, 12, 13]

Builtin Currying Functions in Swift

In the Swift standard library there is a function on the Int type called advancedBy that takes an amount, and returns an Int that has been adjusted by that amount.

extension Int : RandomAccessIndexType {
    func advancedBy(amount: Distance) -> Int
}

It’s simple enough to use this function on an Int and get the advanced value:

5.advancedBy(6) // Output: 11

But because of function currying, we could get the partial application of this function by not specifying the initial value to be advanced:

let add6 = Int.advancedBy(6)
add6(5) // Output: 11
add6(10) // Output: 10

Let’s look at the following example. To insert another string at the end of the given string, we could call the splice function on an instance of String:

var s = "Hello"
s.splice(", world", atIndex: s.endIndex)
// Output: "Hello, world"

Or we can call it on String data type, and pass the String instance as its only argument:

String.splice(&s)("!!!", atIndex: s.endIndex)
s // Output: "Hello, world!!!"

The splice function on a String instance is not a curried function. s.splice("!!!")(atIndex: s.endIndex) will not compile.

The term partial application, is a function that accepts only some of its arguments, and returns another function that takes the rest of arguments. While a curried function takes only one argument.

Don’t confuse partial application with another term called partial function. Partial function is a function that cannot provide a valid result for all its possible inputs. In Objective-C, if we call [[NSString alloc] initWithString:nil], it will compile but throw a NSInvalidArgumentException at runtime. -initWithString: is a partial function, because there is no return value for nil.

Next Steps

Is this all making sense? This can all be quite a chunk of new information to take in if you are new to functional programming in general. For that reason we are preparing a free functional programming course that is in private beta testing right now. If you want to be part of the beta, or just want us to let you know when it’s ready, sign up for the beta here.

Did this tutorial help you?

Support my Patreon

Your support on Patreon allows me to make better tutorials more often.

Subscribe via RSS