There are a few higher-order functions for collections that can be rather difficult to fully understand. While there are several good resources out there to learn the basics, it can still be confusing and seem a bit like magic. And when things seem like magic they tend to not get used effectively or maybe not at all.

In this post, I’m going to try explaining map, compactMap, flatMap, reduce and filter by walking through their inputs, outputs and deriving an implementation for each. For simplicity, we will focus on arrays but this can be expanded to most data structures. The goal is only learning the ideas, not to implement the best possible solution.

There are a few benefits to understanding and using these methods.

  • Understand functional programming
  • Brevity, more concise, less code
  • More readable code (once you understand it)
  • Write more declarative code
  • Helps to eliminate side effects
  • Complex functionality by composing simple pieces

Setup


I’m going to write this code out in a playground file. You can follow along in your own playground or download my finished playground at the end of the post.

When I’m writing and testing multiple functions and ideas in a playground it’s usually nice to wrap it in a simple function. This will help keep variables localized and make it easier to group the output.

func test(_ label: String, test: () -> Void) {
    print("--- \(label) ---")
    test()
    print("")
}

Here we are defining our own higher-order function!

The test function takes a string label, which is used to group test, and a function, which are the tests themselves. The first line prints the label surrounded by some decoration to make it stand out on the debug console. The next line calls the test function that was passed in, the expectation is that this method will print more output. Finally, we print an empty line to give us some spacing for the output.

This is such a simple function that is really useful in playgrounds.

We’re going to be extending Array without own version of these higher-order functions. We can do that because the standard library does not define them directly in Array itself.

extension Array {
    typealias A = Element

}

The Array type is generic, meaning it can hold different types of elements. The generic name for the type of element held in the array is “Element”. Here we are defining an alias for Element called A which will make our signatures easier to understand.

For example, compare these two lines:

func aToB<B>(a: A) -> B
func elementToT<T>(element: Element) -> T

Next, we need to define some data that we can test with. Since we are focusing on Arrays, let’s set up a few basic arrays with different value types.

let integers = [1, 2, 3]
let alphabet = ["a", "b", "c"]
let integerArrays = [[1, 2], [3, 4, 5]]

struct Person { let name: String; let friends: [String] }
let people = [
    Person(name: "Jane", friends: ["Jon", "April"]),
    Person(name: "Sam", friends: ["Mark", "Tony"])
]

Here we have defined an integer array, a string array, an array of integer arrays, and an object (Person) array.

That should be enough to get us started. Now on to the main event!

 

Functions


Map, compactMap, flatMap, reduce and filter are all higher-order functions. A higher-order function is simply a function which takes a function its input or as part of its input.

In mathematics, a function defines a relationship between the set of inputs (domain) and the output (codomain) such that every input is related to exactly one output. The set of all input-output pairs is a graph.

This relationship between inputs and outputs is also sometimes called a mapping which is usually shortened to map.

 

Map


Map transforms values.

When you call the map function on an array, the input (domain) is the elements of the array. The function is what you supply, the argument passed to the map function. And the output is a new array where each of the input values has been mapped to a value in the codomain.

In other words, the output of map is an array containing the results of passing each value through the provided function.

Let’s look at some examples.

test("map") {
    let half = integers.map { Double($0) / 2 }
    print(half)
    
    let uppercase = alphabet.map { $0.uppercased() }
    print(uppercase)

    let counts = integerArrays.map { $0.count }
    print(counts)
    
    let names = people.map { $0.name }
    print(names)
}

Output:

--- map ---
[0.5, 1.0, 1.5]
["A", "B", "C"]
[2, 3]
["Jane", "Sam"]

First, we use map over integers, converting them to Doubles then dividing by two, resulting in an array of Doubles which are half the value of the original Ints.

Next, we map over the strings calling uppercased. The result is an array of uppercase strings.

Then we get the count for each array in the integerArrays.

Finally, we can get the names of all the people by mapping over our people and just return the name.

Simple, yet powerful.

 

Implementing Map

Now, let’s suppose you want to write a map function. Where would you start?

Let’s start with the signature, defining the input and output types. As we can see from the examples above, the input is a function and the output is an array.

More precisely, the input is a function which transforms its input (a value in the array) to another value. Note that the transformed value may be a different type than that of the input value. i.e. 𝑓: A → B. The output, therefore, is an array containing elements of the codomain B.

Now, before looking at the code below, try to write the function signature on your own.

func map<B>(_ transform: (A) -> B) -> [B]

Congratulations! You just crossed the biggest hurdle.

Now let’s give some thought about the implementation of map. How do we actually get from [A] to [B] and how do we use transform? We just create a new array of B and fill it with the transformed values. Try to write the code for that.

Here’s the complete map function:

func map<B>(_ transform: (A) -> B) -> [B] {
    var result = [B]()
    forEach { element in
        result.append(transform(element))
    }
    return result
}

Pretty neat, right?

 

Compact Map


CompactMap maps values, discarding values that can’t be mapped.

Note: Until Swift 4.1 this functionality was an overload of flatMap.

Compact Map is similar to Map except that its function allows for inputs that do not relate to any value in the codomain. The function optionally returns some value or none.

The inputs that result in none are discarded and have no corresponding value in the output. Because of this, the output of compactMap can contain fewer elements than the input.

You use compactMap the same way you would use map but in cases where the function may not be able to convert a value.

Note: you can use the same function with map but the output elements will be Optional which is usually undesirable.

Let’s look at some examples.

test("compactMap") {
    let numbers = ["1", "a", "2"].compactMap { Float($0) }
    print(numbers)
    
    let plus1 = integers.compactMap { $0 + 1 }
    print(plus1)
}

Output:

--- compactMap ---
[1.0, 2.0]
[2, 3, 4]

In the first example, we try to convert strings to Floats. Since “a” doesn’t convert to a Float it has no corresponding value in the resulting array. Only “1” and “2” can map.

The second example is just meant to show the similarity with map. The output is the same in the case that the input function doesn’t return nil values.

 

Implementing compactMap

Having already done map, compactMap should be pretty easy. Again, I encourage you to try implementing this on your own.

The function signature is almost identical to map, except, of course, that the transform function returns an optional value. Be careful that the output array is not optional.

In the body, we just check the output of the transform and only append to the output when there’s a value.

Here’s the full compactMap implementation:

func compactMap<B>(_ transform: (A) -> B?) -> [B] {
    var result = [B]()
    forEach { element in
        if let transformedValue = transform(element) {
            result.append(transformedValue)
        }
    }
    return result
}

Got the hang of it?

 

Joined


We’re going to take a slight detour before getting to flatMap because I think understanding joined will make flatMap a little easier to digest. Joined is not a higher-order function.

Joined is defined for arrays containing arrays. Technically, not directly defined for Array but for our purpose you can think of it this way. However, because it’s not defined for an array, the result is not an array but can easily be cast back to an array.

Essentially, what it does is concatenate the elements of the array of arrays. In other words, it creates a new array appending the contents of each array contained in the array of arrays. Another way to think about this is in terms of dimensions. An array of arrays is sometimes called a two-dimensional array. A two-dimensional array can be flattened to a one-dimensional array using the joined function.

Note: Empty arrays contain no values and therefore contribute no values to the result.

 

 

Flat Map


FlatMap maps values to arrays then flatten them.

The flatMap function is probably the one that most people have some confusion around. Part of that confusion is probably due to the fact that prior to Swift 4.1 flatMap was overloaded to do what compactMap does now.

I think it’s easiest to think about flatMap in two parts. The first is a map which maps elements to arrays. The second is taking that result and flattening with the joined function.

The function that you pass into flatMap has a domain which is equal to the elements in the array, i.e. the input is the same as with map. However, the output will be an array of elements.

Let’s look at some examples.

test("flatMap") {
    let friends = people.flatMap { $0.friends }
    print(friends)
    
    let flat = integerArrays.flatMap { $0 }
    print(flat)

    let repeated = integers.flatMap { Array(repeating: $0, count: $0) }
    print(repeated)
}

Output:

--- flatMap ---
["Jon", "April", "Mark", "Tony"]
[1, 2, 3, 4, 5]
[1, 2, 2, 3, 3, 3]

In the first example, we flatMap over people returning their friends, resulting in a flattened list of all friends. This is similar to the map example that extracted the names of people into a list. The difference is friends is an array. If we had called map instead of flatMap the result would be an array or arrays containing strings [[String]]. In most cases, we don’t want that extra overhead of having to deal with arrays in arrays and so it’s convenient to flatten it, losing the information about which index or Person the friend came from.

Pulling out arrays of data from objects and then flattening them is probably the most common usage of flatMap.

The second example looks like it does nothing. It’s just returning it’s input, right? That’s true that the function is just passing data through, but it still going to flatten the result. The result is practically the same as calling joined, except that flatMap actually returns an Array so it may be slightly more convenient to work with.

The final example shows that you don’t have to have an embedded array to use flatMap. As long as the input can produce an array and you want to flatten that result, flatMap is the right choice. Here we create an array from an integer by repeating the value of the integer the same number of times.

 

Implementing flatMap

As I’ve hinted at several times already, the result of flatMap is the same as calling map then joined. The one difference is that the function passed to flatMap must return an array. With that, the implementation is rather simple.

func flatMap<B>(_ transform: (A) -> [B]) -> [B] {
        return Array<B>(map(transform).joined())
}

That’s really all there is to it.

Just for fun, let’s implement flatMap without the use of map or joined. We will need to create an array, iterate over every element calling transform, and appending the contents of the resulting array to our new array.

func flatMap<B>(_ transform: (A) -> [B]) -> [B] {
    var result = [B]()
    forEach { element in
        result.append(contentsOf: transform(element))
    }
    return result
}

That’s nearly identical to map except we append the contents of the transform rather than the result.

We’re now complete with our mapping functions: map, compactMap, and flatMap. Next, let’s take a look at a couple other types of higher-order functions: filter and reduce.

 

Filter


Filter removes unwanted values from an array.

The result of filter is an array containing a subset of elements included in the original array. Elements to be included are determined by the result of the function passed into filter.

The filter method, like map, takes a function as an input. The input to that function (the domain) is the contents of the array that filter is called on. The output (codomain) is a subset of true and false. In other words, the values in the array are mapped to either true or false.

Unlike the map function, however, filter does not return these mapped values. Instead, it uses values mapped to true to include in the output. Values mapped to false are discarded.

Let’s look at some examples.

test("filter") {
    let odds = integers.filter { $0 & 1 == 1 }
    print(odds) // 1 -> 3 -> end
    
    let search = "a"
    let result = alphabet.filter { $0 == search }
    print(result) // a -> end
    
    let contains1 = integerArrays.filter { _ in true }
    print(contains1)
    
    let js = people.filter { _ in false }
    print(js)
}

Output:

--- filter ---
[1, 3]
["a"]
[[1, 2], [3, 4, 5]]
[]

In the first example, we are looking for odd integers. The function returns true for add values resulting in 1 and 3 included in the output and the 2 is discarded.

The next example is set up as a search where the search term is “a” and we are looking for an exact match. Of course “a” is the only match. It’s a bit contrived, but hopefully, you get the idea.

The next two examples ignore in input and simply return true and false respectively. Here you can see that true returns all elements and false will exclude all elements.

 

Implementing filter

Do you think you can come up with the function signature for filter on your own? Again, we know that the input is a function and the output is an array. To be more specific, the input function will take an element and return a boolean which is used to determine if the value is included in the result. The result of filter is an array containing a subset of the original values, so we know it has the same type.

func filter(_ isIncluded: (Element) -> Bool) -> [Element]

Note: since we are not converting A -> B, I’ve gone back to calling the A type Element which is how it’s defined on Array and is much more readable in this context.

For the body, we’re just going to loop over each element in our array and append it to a new array if the function we passed in tells us to include it.

func filter(_ isIncluded: (Element) -> Bool) -> [Element] {
    var result = [Element]()
    forEach { value in
        if isIncluded(value) {
            result.append(value)
        }
    }
    return result
}

 

Reduce


Reduce combines the elements of the array into a single value.

The reduce method stands apart from the rest in both input and output. The input is two parameters, an initial value, and a function. The output is a single value.

The function passed to reduce also has two parameters. The first parameter represents the current result and the second parameter is a value from the array. The output of this function is the combined value of the current result and the value that was passed in.

Let’s look at some examples.

test("reduce") {
    let sum = integers.reduce(0, +)
    print(sum)
    
    let joined = alphabet.reduce("") { [$0, $1].joined() }
    print(joined)
    
    let count = integerArrays.reduce(0) { $0 + $1.count }
    print(count)
    
    let friends = people.reduce([String]()) { result, value in
        var nextResult = result
        nextResult.append(contentsOf: value.friends)
        return nextResult
    }
    print(friends)
}

Output:

--- reduce ---
6
abc
5
["Jon", "April", "Mark", "Tony"]

The first example combines integer values by adding them together. We start with a value of 0 and add each value one by one resulting in the sum of all the numbers.

The second example the individual strings into one using joined. Note, this is similar but not the same joined method we discussed earlier, this one is overloaded specifically for arrays of strings.

Next, we count all of the elements in our multidimensional array. We start with 0 and for each element, we add the number of elements contained within it.

Finally, we reduce our array of people to an array containing all friends. This example shows that, although we are reducing to a single value, there’s no reason that single value can’t be a collection containing more values. In other words, it’s okay for reduce to result in an array.

Note that the standard library defines a second form, reduce(into:_:), which makes reducing into a collection much easier and more performant. I’ll leave it to the reader to explore this alternative further.

Reduce is actually very powerful. The evidence of that can easily be found by the fact that all of the other higher-order functions we’ve discussed so far can be implemented using reduce.

 

Implementing reduce

Let’s think about what the signature could be for the reduce method. The result is a single value of an unknown type. So, we know it’s going to be generic. The first parameter is some initial value of the type we want to reduce to. The second parameter is the function that combines the elements.

The function that’s passed in needs to combine the current value with the previous to create the next partial result. So that function is going to take an argument that represents all of the previously combined values (or the initial value) and another argument that is the current value to be combined.

Here’s the result:

func reduce<T>(_ initialResult: T, _ nextPartialResult: (T, Element) -> T) -> T

Now the body of the method is actually rather simple. We’re just going to keep track of the result, starting with the initialResult value and combining the next value until we are left with only a single value.

func reduce<T>(_ initialResult: T, _ nextPartialResult: (T, Element) -> T) -> T {
    var result = initialResult
    forEach {
        result = nextPartialResult(result, $0)
    }
    return result
}

That’s it for the higher-order functions. We’ve covered map, compactMap, flatMap, reduce and filter! There is one thing that the built-in methods do which we didn’t account for. If you looked at the built-in methods, you may have noticed that they can throw. For the sake of simplifying we avoided error handling.

 

Error Handling


The actual higher-order functions defined in the standard library allow you to pass in a function that can throw. It doesn’t make any sense for the higher-order function to handle the error thrown by the function passed in so it simply rethrows. To understand how this works, let’s look at map for example.

func map<B>(_ transform: (A) throws -> B) rethrows -> [B] {
    var result = [B]()
    for element in self {
        let newValue = try transform(element)
        result.append(newValue)
    }
    return result
}

Since the transform function passed in can throw, we have to use try where it’s called. We don’t have to wrap it with do {} catch {} since map simply rethrows the error. This is convenient when trying to convert to a type with a throwing constructor. Now you can use it like this:

do {
    let file = try [fileUrls]
        .map { try String(contentsOf: $0) }
} catch {
    // do something with error
}

 

Conclusion


Higher-order functions aren’t scary, they’re actually rather simple. Simple, yet powerful. I’ve seen a lot of confusion around return types or what type was actually being operated on or seemingly cryptic compiler errors. Too many people give up at this point and fall back to older habits. My hope is now that you understand the internals of these functions you’ll better understand how to use them. The methods we covered can also be used as examples to show how you can easily build your own higher-order functions and how you can compose simple functions to build complex systems in a declarative manner.

I’d love to hear your feedback, questions or thoughts; find me on twitter @kenboreham
Thanks for reading! 🔥👍