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.

  40 comments for “Higher Order Functions: Map, Filter, Reduce and more

  1. zav
    June 3, 2014 at 3:02 pm

    Please let me proofread this for you and correct the many grammar mistakes.

    • June 3, 2014 at 3:16 pm

      I fixed some of the issues using a spellchecker. Please feel free to point out my sloppy grammar.

  2. June 5, 2014 at 1:32 pm

    Great article and nice site. Swift looks fascinating and you seem to have a head start on getting to grips with it already. Good job!

  3. Herb Payerl
    June 6, 2014 at 9:38 pm

    Swift’s map and filter functions have origins in Smalltalk’s collect and select collection methods.

    Have a look at the terse guide to squeak to see. These are certainly welcomed language additions as Swift takes a step towards closing the gap between objective C and it’s Smalltalk origins. Closures are also elegantly handled in Smalltalk.

    http://wiki.squeak.org/squeak/5699

    Nice article.

    • June 6, 2014 at 9:59 pm

      I believe map appeared for the first time in one of John McCarthy’s Lisp papers from 1960. (9 years before development on Smalltalk started)

      MapList at the end of the article.

  4. ewangelia
    June 8, 2014 at 11:13 pm

    I like this post, enjoyed this one thanks for posting .

  5. June 10, 2014 at 2:33 am

    We might not *need* an equivalent to fuckingblocksyntax, but we have one: http://fuckingclosuresyntax.com :)

  6. Axman6
    June 10, 2014 at 6:56 am

    I was so disappointed you didn’t give and answer to question 12 in the article. The property that makes parallel reduction almost trivial is that the type being reduced is a monoid which is just something with a function to “join” two things of a specific type, and an identity which when joined with any value of that type returns that value (1+0 = 1, so the operation is + and the identity is 0). The examples you use are (+,0), (*,1), but you can also have (appendArray,[]) (not sure what this would be called in Obj-C/Swift land, but we’d use (++, []) for list concatenate and empty list), there’s also (&&,True) and (||,False), even function composition (written in haskell as ‘.’, with the identity being the id :: a -> a giving (.,id)) with functions who take a single argument and return a value of the same type as the input, plus plenty more.

    There’s so much theory from the land of FP languages that is already being applied to Swift and it’s really exciting. The Swiftz library is an interesting attempt at implementing several ideas from Haskell in a clean way (and finding out which things work nicely, which don’t and which cause the compiler and Xcode to crash; fun stuff!)

    Great post!

    • June 10, 2014 at 11:12 am

      I can’t come up with an concrete example right now but isn’t it enough for the type being reduced to be a Semigroup (a monoid without an identiy element)?
      Reduce doesn’t have to take the type’s identity as argument, just a value of the type.

      The critical obervation is that you can easily parallelize an operation if it’s associative.

    • July 1, 2014 at 2:26 pm

      The key idea of starting with a sequence and applying a bunch of immutable transforms to it lazily is central not only to FP languages, but also to Python—which I think might be more accessible to the typical Swift audience coming out of ObjC. (Also, functional programmers, especially coming out of Haskell, tend to mix this concept freely together with the concept of building higher-order functions—and they are two powerful concepts that synergize nicely, but it can be helpful to learn them each separately.)

      The itertools module in Python’s standard library (as well as a handful of builtins that Swift is missing, like zip), and third-party libraries like more-itertools, show a lot of the things that you can do beyond map and filter. David Beazley has a great presentation called “Generator Tricks for Systems Programmers” (http://www.dabeaz.com/generators-uk/) that shows how to use all of these things.

      Unfortunately, while Python, Ruby, Clojure, Scala, Haskell, etc., all provide really simple ways to create new iterator transformations (comprehensions, generator functions, or both), Swift doesn’t… but maybe in a future version it will.

      In the mean time, I’ve started a project to port Python’s itertools, plus a variety of other useful functions from other libraries and other languages, to swift. The project needs to be restarted because of what I’ve learned along the way, and because of what Apple has improved since the first beta (although some parts of it are still useful as-is; you can see it at http://github.com/abarnert/swift-itertools if interested). I’ve been keeping a blog at http://stupidswiftideas.blogspot.com.

  7. abc
    June 26, 2014 at 9:30 pm

    Do you know why this reduce, with objects, doesn’t work?

    let cartItems:CartItem[] = […]

    cartItems.reduce(0, combine: {$0 + ($1.price * $1.quantity)})

    It says “couldn’t find member ‘price'”, but the fields are 100% there, even suggested by autocompletion.

    • June 26, 2014 at 10:44 pm

      Just a hunch. Is price a Float?
      I think cartItems.reduce(0.0, combine: {$0 + ($1.price * $1.quantity)}) should work.

      • abc
        June 27, 2014 at 11:04 am

        I tried many things and ended copying an incorrect “combination”. My problem seems to be related with casting – price is stored as a String. I wrote a small example:

        class Foo {
        let test:Int = 2
        let test2:String = “2”
        }

        func test() {
        let foos:Foo[] = [Foo(), Foo(), Foo()]
        foos.reduce(0, combine: {$0 + $1.test}) //compiles
        foos.reduce(0, combine: {$0 + ($1.test2 as Int)}) //doesn’t compile
        }

        Maybe a compiler bug? Sure casting is not very efficient in reduce, but it should be possible.

        • June 27, 2014 at 11:11 am

          The problem is that you’re trying to cast a String to an Int.
          The “as” operator is used for downcasting here’s a simple example of using it:
          var x:Any = [1,2,3]
          var y:Int[] = x as Int[]
          You can’t cast a String to an Int because Int is not a subclass of string.

          To convert a string to an Int use the toInt() method on string. For example:
          var string = “123”
          var int = string.toInt()

          • abc
            June 28, 2014 at 7:23 pm

            Ah. My bad!! I knew this, but somehow I’m messing up :D

            Thanks a lot, it works!

  8. Christopher Dyer
    November 13, 2014 at 1:59 pm

    Hi Silviu, please help me understand what you have kindly written. I understood, the examples starting with – averageOfFunction(3, 4, {(x: Float) -> Float in return x * x}) – still call the function – func averageOfFunction(a:Float,b:Float,f:(Float -> Float)) -> Float – described in the preceding box, but no longer need the other square and cubed functions. If this is correct, then does the closure parameter – f:(Float -> Float) – basically become what the closure function returns – x * x – which would allow it to take in the other paramenters – a and b as (x: Float)? If true, then I understand the fuckingthisandthatsyntax issue.

    • Christopher Dyer
      November 14, 2014 at 9:09 am

      I guess the above is wrong. In xcode playground, the lines – averageOfFunction(3, 4, square) AND averageOfFunction(3, 4, {$0 * $0}) – show different results in the results column – 12.5 AND “(3 times)”. Even if these lines of code are not the same, wouldn’t the number of times the closure is called be 4 times in the second call? Now I’m totally lost…

  9. Christopher Dyer
    November 14, 2014 at 9:30 am

    If understood, in your Maps section the operator – “+=” – can’t be used anymore to append elements of an array. I guess it should be:
    for money in moneyArray {
    stringsArray.append(“\(money)$”)
    }

    • Christopher Dyer
      November 14, 2014 at 10:29 am

      Same in the filter box – filteredArray += money – should be – filteredArray.append(money). If you do update the article, these comments can be deleted.

      • Jason Adams
        February 12, 2015 at 9:22 pm

        filteredArray += [money] would work just as well.

  10. November 19, 2014 at 2:37 pm

    Hey, perfect post! Thanks~

  11. Mohammed al Waili
    February 18, 2015 at 10:44 am

    Thank you very much for this article. I was so confused, but not anymore :P

  12. Dave B
    July 16, 2015 at 7:16 am

    Thanks for some great working examples. I had learnt this from the official book but this seems to explain very well.

  13. john
    December 13, 2015 at 12:37 am

    Great tutorial and needs to be reviewed for Swift 2.x. I ran into trouble as soon as I used a function with two parameters.

  14. Prathap Uday Shetty
    July 20, 2016 at 7:13 am

    filter function that selects only strings that can be converted to Ints

  15. December 2, 2016 at 11:25 pm

    My solutions for the problems using Swift 3 can be found here: https://github.com/david6p2/HigherOrderFunctionsPlayground . I didn’t understand question #12

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Subscribe
We send about one email per week with our latest tutorials and updates
Never display this again :)