Higher Order Functions: Map, Filter, Reduce and more

Introducing Closures

One of the great features of Swift is a clean new syntax for first class functions / closures that replaced the quite confusing block syntax. So hopefully we won’t need something like fuckingblocksyntax for Swift.

Closures are self-contained blocks of functionality that can be passed around and used in your code.

In this article we’ll focus on closures that are anonymously defined (i.e. defined inline without a name) also called unnamed closures. We can pass these as parameters to other functions/methods or return them as result values. Closures are an extremely powerful language feature and can make programming faster, easier and less error prone.

Blocks/Closures (different names for the same concept) are extensively used throughout Cocoa and Cocoa Touch and are at the heart of amazing iOS frameworks

Let’s look at some examples of closures and why they’re a useful concept :

Let’s say we want two functions one that computes the average of the squares of 2 numbers and one that computes the average of the cubes of 2 numbers. A naive solution would look like this:

func square(a:Float) -> Float {
    return a * a
}

func cube(a:Float) -> Float {
    return a * a * a
}

func averageSumOfSquares(a:Float,b:Float) -> Float {
    return (square(a) + square(b)) / 2.0
}

func averageSumOfCubes(a:Float,b:Float) -> Float {
    return (cube(a) + cube(b)) / 2.0
}

Notice that the only difference between averageSumOfSquares and averageSumOfCubes are the calls to the square or cube function respectively. It would be nice if we could define a general method that takes as parameters 2 numbers and a function to apply to them and compute their average instead of repeating ourselves, and we can by using a closure as a parameter.

func averageOfFunction(a:Float,b:Float,f:(Float -> Float)) -> Float {
    return (f(a) + f(b)) / 2
}

averageOfFunction(3, 4, square)
averageOfFunction(3, 4, cube)

Note that we use an explicit name for the closures we send here. We can also define closures inline withouth giving them an explcit name using a closure expression.

There are multiple ways of defining a closure expression in Swift. Here they are sorted from most verbose to least verbose:

averageOfFunction(3, 4, {(x: Float) -> Float in return x * x})

(x: Float) -> Float is the type of the closure (a function that receives a float parameter and returns a float value return x * xis the implementation and follows after the in keyword Quite a headache to write all this code, let’s make it shorter

First of all we can omit type declaration because this can be inferred from the averageOfFunction declaration (The compiler already knows that averageOfFunction expects a function that receives a float and returns a float) averageOfFunction(3, 4, {x in return x * x})

We can also omit the return statement averageOfFunction(3, 4, {x in x * x})

And last of all we can omit specifying the parameter names altogether and use the default parameter name $0 (If the function accepted more than one parameter the we would use $K for the (K-1)nth paramter $0,$1,$2…)

averageOfFunction(3, 4, {$0 * $0})

We’ll use the last method of specifying closures for the rest of this tutorial but I encourage you to use explicit names in your project when clarity demands it.

The programming technique of passing closures to a function instead of duplicating it’s source can be used to greatly increase the expressivity of code and avoid errors associated with boilerplate code and copy pasting.

Sequence Operations

Swift’s standard Array Library includes support for 3 higher order sequence functions: map, filter and reduce. Objective C’s NSArray class laked support for these methods but the Open Source Community stepped in to address these shortcomings

Map

The map method solves the problem of transforming the elements of an array using a function.

[ x1, x2, ... , xn].map(f) -> [f(x1), f(x2), ... , f(xn)]

Let’s say we have an array of Ints representing some sums of money and we want to create a new array of strings that contains the money value followed by the “€” character

i.e. [10,20,45,32] -> ["10€","20€","45€","32€"]

The ugly way of doing this is by creating a new empty array, iterating our original array transforming each element and adding it to the new array

var stringsArray : [String] = [] //Note that we have to specify the type of the array or else we'll get an type error

for money in moneyArray {
    stringsArray += "\(money)$"
}

The operation of transforming individual elements of an array and creating a new array from them is so common that we have a method for doing it: map.

In Swift map is declared as a method on the Array class with signature func map<U>(transform: (T) -> U) -> U[] That just means that it receives a function named transform that maps the array element type T to a new type U and returns an array of Us

In our example T would be Int and U would be String so we have to give map a function that maps from Ints to Strings

Using map is just: stringsArray = moneyArray.map({"\($0)€"})

where {"\($0)€"} is our supplied closure that returns the amount of money as a string followed by €

Or by naming our parameter stringsArray = moneyArray.map({money in "\(money)€"})

If the above code doesn’t make sense you might not familiar with string interpolation check out the documentation. Here’s a quick snippet:

String interpolation is a way to construct a new String value from a mix of constants, variables, literals, and expressions by including their values inside a string literal. Each item that you insert into the string literal is wrapped in a pair of parentheses, prefixed by a backslash:

Swift String Apple Reference

Filter

The filter method solves the problem of selecting the elements of an array that pass a certain condition

Using our previous money example let’s write some code that creates a new array that only contains the amounts exceeding 30€

Our code should produce [45,32]

Again let’s first look at the naive method

var filteredArray : [Int] = [] 

for money in moneyArray {
    if (money > 30) {
      filteredArray += [money]
    }
}

We can see that the only interesting part of that code is money > 30, the rest is boilerplate, the filter method lets us concisely define the same logic.

In Swift filter is declared as a method on the Array class with signature func filter(includeElement: (T) -> Bool) -> T[] i.e. receives a function includeElement that returns true or false for elements of the array and returns only the elements that return true when includeElement is called on them

To filter our array we just have to use

filteredArray = moneyArray.filter({$0 > 30}) where {$0 > 30} is our supplied filter closure

Again note that we omit parameters using the default $0 parameter name and the return type is implicitly assumed to be Bool

Reduce

The reduce method solves the problem of combining the elements of an array to a single value

Using the money example let’s write some code that computes the sum of the elements in the array

Our code should produce 107 (10 + 20 + 45 + 32)

Let’s first have a look at the naive method

var sum = 0
for money in moneyArray {
    sum = sum + money
}

Let’s also look at a method that multiplies the numbers together, for context:

var product = 1
for money in moneyArray {
    product = product * money
}

We can see that the only difference between computing the product and the sum is the starting value we’re using(0 for sum and 1 for product) and the operation that we’re applying to the partial result (+ for sum, * for product)

Reduce is a method that let’s us quickly define this kind of operations by specifying an initial value and a method of combining elements.

In Swift reduce is declared as a method on the Array class with signature func reduce(initial: U, combine: (U, T) -> U) -> U i.e. receives an initial element of type U and a function that specifies how to combine an element of type U with an element of type T to a single element of type U. The whole array is reduced to a single element of type U

In our example both U and T are of type Int, the initial element is 0 and the combine function is adding two Ints

To compute the sum of our array we can use:

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

We can take advantage of the fact that operators are methods in Swift and make using reduce even more convenient

sum = moneyArray.reduce(0,+)

Reduce is probably the most difficult to understand of the 3 higher order array functions. One thing to note is that the arguments of the combine method might have different types with $0 being the of the resulting value type and $1 being of the type of the elements in the array.

One last note about higher order array functions is that they can be faster for large arrays than their naive equivalent because they can be paralellized(i.e. run on multiple cores), you just need one brilliant programer to implement highly optimized versions of map, reduce and filter and your whole codebase that uses them gets faster.

I hope I’ve convinced you that using map, filter, reduce in your code can increase it’s quality. But I urge you to use these methods when appropriate, don’t just try to apply them to any problem. When you have a new hammer everything starts to look like a nail.

Here are some problems to get your hands dirty with closures:

1. Write a function applyTwice(f:(Float -> Float),x:Float) -> Float that takes a function f and a float x and aplies f to x twice i.e. f(f(x))
2. Write a function applyKTimes(f:(Float -> Float),x:Float,k:Int) -> Float that takes a function f and a float x and aplies f to x k times
3. Using applyKTimes write a function that raises x to the kth power
4. Given an array of Users which have properties name:String and age:Int write a map function that returns an array of strings consisting of the user’s names
5. Given an array of of dictionaries containing keys for “name” and “age” write a map function that returns an array of users created from it
6. Given an array of numbers write a filter method that only selects odd integers
7. Given an array of strings write a filter function that selects only strings that can be converted to Ints
8. Given an array of UIViews write a filter function that selects only those views that are a subclass of UILabel
9. Write a reduce function that takes an array of strings and returns a single string consisting of the given strings separated by newlines
10. Write a reduce function that finds the largest element in an array of Ints
11. You could implement a mean function using the reduce operation {$0 + $1 / Float(array.count)}. Why is this a bad idea?
12. There’s a problem you encounter when trying to implement a parallel version of reduce. What property should the operation have to make this easier ?
13. Implement Church Numerals in Swift (This is a difficult and open ended exercise)

Stay tuned and happy hacking

Full Code

If you found this useful please take a moment to share this with your friends.