Higher Order Functions In Swift

What can we learn from ‘map’, ‘filter’ and ‘reduce’?

Imagine that we need to calculate the sum of all the numbers from 1 to 100 whose squares are divisible by 4. In Swift, we could do that in the following way:

let result = reduce(1...100, 0) { 
($1 * $1) % 4 == 0 ? $0 + $1 : $0
}
println(result) // 2550

But what does this cryptic syntax mean? The syntax is actually very easy to understand once we know what ‘reduce’ is and how it works. It’s just a simple higher order function. Higher order function is a fancy name for a function that accepts another function as an argument or returns another function. While reading and listening about functional programming, I can't avoid remembering what Richard Feynman once said:

“Don’t say ‘reflected acoustic wave.’ Say [echo].”
“Forget all that ‘local minima’ stuff. Just say there’s a bubble caught in the crystal and you have to shake it out.”
(Source)

These functions are nothing new, of course. In fact, Cocoa and Cocoa Touch developers had been using some of them even before Swift was introduced. NSArray’s ‘enumerateObjectsUsingBlock:’ is one such example. So why would anyone bother to write about higher order functions in Swift? Because Swift promoted functions into first-class citizens, making higher order functions much more pleasurable to work with. Its standard library has already taken advantage of that, offering few particularly useful higher order functions, namely ‘map’, ‘filter’ and previously mentioned ‘reduce’ (also known as ‘fold’ in some other languages). This trio of functions is very powerful and can help with solving surprisingly many problems easily and elegantly. But the real power comes from the ability to create our own higher order functions and use them in many different ways. Swift is a great opportunity to popularise this, still somewhat underground, style of programming and there have already been some very good first steps in that direction.

Implementing higher order functions

The best way to learn how something works is to make it. So let’s make our own higher order function. We will start by giving a brief introduction to lambda calculus. Just kidding. Let’s instead start by solving one very simple problem procedurally. Given an array of integers, we want to calculate and output an array of their squares.

let numbers = [1, 2, 3, 4, 5]
func calculateSquares(numbers: [Int]) -> [Int] {
var squares = [Int]()
for number in numbers {
squares += [number * number]
}
return squares
}
println(calculateSquares(numbers)) // [1, 4, 9, 16, 25]

There are few problems with this code. The biggest two are that it works only with integers and that it can only calculate squares. It’s not very reusable. If we want to do some other operation on the input numbers, we have to write a new function, similar to this one, but with different code inside the for loop. Each time we need to do something new, we need to iterate trough the array over and over again. But that’s not our job. That should be done for us. Furthermore, we don’t even care whether the array is actually iterated through. Recursion could be used instead. What we really want is to do something with those numbers. Or more generally, we want to do something with a list of any elements. So we need a function that can be told what to do with the input list. How that work is actually done, is not something we should worry about. The details of the work should be hidden under the hood. They can change at any time, e.g. replacing iteration with recursion, without us knowing and caring about that. Let’s first write a function that can do anything with an array of integers and we will later generalise it so that it can work with an array of any type. What we really want to do inside the for loop is to take the current number, do something with it and append the result to the array which we will return at the end. The body of our new function could look something like this:

var results = [Int]()
for
number in numbers {
results += [operation(number)]
}
return results

The ‘operation’ is a function that takes an integer and returns an integer. But how can we provide that function to the body of another function? Easy in Swift, just like we provide arguments of any other type. Remember, functions are first-class citizens. Here is the complete function:

func doSomethingWithNumbers(
numbers: [Int],
operation: (Int) -> Int) -> [Int] {
var results = [Int]()
for number in numbers {
results += [operation(number)]
}
return results
}

There we are, we’ve just written our first higher order function. But how do we use it? Easily and naturally, by defining an operation function and passing it to ‘doSomethingWithNumbers’. We can still calculate squares:

func square(a: Int) -> Int {
return a * a
}
println(doSomethingWithNumbers(numbers, square)) 
// [1, 4, 9, 16, 25]

But we are not limited to calculating squares any more. We can now do anything with the input list, e.g. doubling each element.

func double(a: Int) -> Int {
return 2 * a
}
println(doSomethingWithNumbers(numbers, double)) // [2, 4, 6, 8, 10]

Nice, but can we make our function to take an array of any elements (not just integers), do something with each element and output an array of whichever type, not necessarily the same as the input array’s type? Yes, we can, by using generics.

func doSomethingWithElements<T, U>(
elements: [T],
operation: (T) -> (U)) -> [U] {
var results = [U]()
for element in elements {
results += [operation(element)]
}
return results
}

We can still calculate squares and do the integer doubling with our new generic function. But now we can do much more. We can calculate square roots, for example.

import Foundation
func squareRoot(a: Int) -> Double {
return sqrt(Double(a))
}
println(doSomethingWithElements(numbers, squareRoot)) 
// [1.0, 1.4142135623731, 1.73205080756888, 2.0, 2.23606797749979]

Or let’s move away from numbers. We can take an array of strings and capitalise each element.

import Foundation
let languages = ["swift", "java", "haskell"]
func capitalize(string: String) -> String {
return string.capitalizedString
}
println(doSomethingWithElements(languages, capitalize)) 
// [Swift, Java, Haskell]

We can do basically anything with any array. But let’s think about the name of our function. ‘doSomethingWithElements’ does express very well the fact that we are taking some elements and then doing something with them, processing them somehow. But what are we returning? Nothing in the function’s name points to the fact that we are returning another array with each element corresponding to exactly one element from the input array. Well, we don’t have to think too much about a better name. What the function does can be simply called mapping. So let’s use the name ‘map’ for it (prefix with ‘_im_’, to avoid name conflicts with the existing ‘map’ function).

func _im_map<T, U>(
elements: [T],
mappingFunction: (T) -> (U)) -> [U] {
var results = [U]()
for element in elements {
results += [mappingFunction(element)]
}
return results
}

We’ve just defined a less generic version of the standard library’s ‘map’ function. We could change it slightly, so that it works with sequences or collections, but let’s keep it like this, for simplicity. Finally, we can extend the ‘Array’ struct so that we can call the function directly on its instances.

extension Array {
func im_map<U>(mappingFunction: (Array.Element) -> (U)) -> [U] {
return _im_map(self, mappingFunction)
}
}

Notice that in this case we only need one generic type, because the other is already provided by the ‘Array’. Let’s examine different ways for using this and other higher order functions. Till now we have been passing predefined functions by their names. But it is often the case that we don’t have any predefined function. Of course, we can always define it and pass it, like we did. But we can also pass an inline closure instead. Let’s rewrite our capitalising example in order to do that.

import Foundation
let languages = ["swift", "java", "haskell"]
let capitalizedLanguages = languages.im_map({
(language: String) -> String in
return language.capitalizedString
})
println(capitalizedLanguages) // [Swift, Java, Haskell]

We can further simplify this in few ways. First, we don’t need ‘return’, since Swift implicitly returns from one-line closures.

let capitalizedLanguages = languages.im_map({
(language: String) -> String in
language.capitalizedString
})

We also don’t need to write argument and return types explicitly, because Swift can infer them from the context.

let capitalizedLanguages = languages.im_map({
language in
language.capitalizedString
})

Whenever a closure is the last parameter of a function (and that should always be the case, unless we have more than one closure argument), slightly simpler trailing closure syntax can be used.

let capitalizedLanguages = languages.im_map() {
language in
language.capitalizedString
}

And because our closure is the only argument in this case, we don’t need the parentheses.

let capitalizedLanguages = languages.im_map {
language in
language.capitalizedString
}

Finally, we don’t even need the argument name. Arguments of inline closure can be accessed using $0, $1 , etc.

let capitalizedLanguages = languages.im_map { 
$0.capitalizedString
}

This syntax could certainly be abused. Just imagine, for example, a completion handler of ‘NSURLSessionDataTask’. What would $0 be in that case? ‘NSURLResponse’, ‘NSData’ or ‘NSError’ object? In that case it’s much more readable to use explicit names:

data, response, error in

But in cases like ‘map’, ‘reduce’, ‘filter’ and similar higher order functions, whose inline closures have one or two arguments, the ‘$0, $1…’ notation can be clean and clear (we always know what those arguments are, there is no confusion).

The other two functions, ‘filter’ and ‘reduce’ are very similar to ‘map’, just slightly more complicated.

func _im_reduce<T, U>(
elements: [T],
initial: U,
combine: (U, T) -> U) -> U {
var result = initial
for element in elements {
result = combine(result, element)
}
return result
}
func _im_filter<T>(elements: [T], predicate: (T) -> Bool) -> [T] {
var filteredArray = [T]()
for element in elements {
if predicate(element) {
filteredArray += [element]
}
}
return filteredArray
}

Hopefully, we are now able to understand the introductory peace of code. Let’s write it here again:

let result = reduce(1...100, 0) { 
($1 * $1) % 4 == 0 ? $0 + $1 : $0
}

Still looks like Greek (or Chinese if you are Greek)? We can rewrite it in a more understandable form.

let result = reduce(1...100, 0) {
(result: Int, currentElement: Int) -> Int in
if (currentElement * currentElement) % 4 == 0 {
return result + currentElement
} else {
return result
}
}

By using the shorthand names of closure arguments ($0 and $1) and the ternary conditional operator (condition ? some value : another value) we were able to reduce the above code to one line. I personally like the shorter syntax in cases like this one, but would probably never use it for completion blocks or whenever the closure’s body has more than one or two lines.