Advanced Array Operations

Advanced Array Functions

So far we have been doing all of our work on arrays based on elements and their location in an array. But, what if we don't know where an element is?

First

There will be times when you want to get an element from an array, but you don't where it is. Instead, you may know what particular field of that element is, or a property of that element. In this case, we create an anonymous function that will return true if the given element satisfies some criteria and false otherwise. This function will be applied to every element in the list, in order, until an element meets the requirement. Execution then stops and the element is returned. If no element in the list fulfills the criteria, the result will be nil. For this, we use first(where predicate: (Element) throws -> bool) rethrows -> Element?. This is one scary function declaration–let's pick it apart. first takes one argument of type (Element) throws -> bool. This argument takes in our element and has the option to throw an error, and otherwise, must return a boolean. We can ignore the error because this is a pretty niche case. Rethrows just means, that the function takes in a function that can throw an error, and if that is the case, it may just throw the error itself, so again, we can ignore this. first(where: (Element) -> bool) -> element this is a lot easier to tackle. Okay so let's put it to use.

let myList = ["a", "b", "c", "d", "e"]
// myList: [String] = ["a", "b", "c", "d", "e"]

let firstE: String? = myList.first { element in element == "e" }
// firstE: String? = optional("E")

When you use this, of course, you would want to just use a property instead of the entire instance because then what's the point of getting it out the list if you already have it. So maybe we have something more like:

struct Person {
    var name: String
    other properties ...
}
var people: [Person] = ...

let noah = people.first { person in person.name == "Noah" }

There are other cases where it may actually be more helpful to get the location in the list instead of the actual element. This is the exact same process, except instead of using first(_:) we use firstIndex(_:).

If a list stores an equatable type–meaning that it conforms to Equatable we can simplify this slightly–but just slightly. Instead of use firstIndex(where:), we can use firstIndex(of: Element). As the function header suggests, instead of creating a closure to determine criteria, we create an item and use equality for criteria. You can think of this as:

extension Array where Element: Equatable {
    
    func first(of element: Element) -> Element? {
        self.first(where: { $0 == element })
    }
    
}

You'll notice that weird where–this is a slight exposure of Array's implementation. Arrays conform to a protocol with an associated type called Element. This is an advanced technique that you do not need to understand–although if you're interested see Protocols with Associated Types. To understand this block of code, think of Array, again, as a generic with the parametric type named Element. When this type conforms to equatable (when we have access to the == function), we will provide another function that takes in an element and applies it, with ==, to first(where:). Hopefully, the code is a little easier to understand than my explanation.

Last

This is exactly the same as First, but it returns the last element that fulfills the critera–so execution never stops short of the length of the list (i.e. it is always exactly O(n)). For last, just change the function name from first to last. So, firstIndex becomes lastIndex and etc. I'm not going to re-explain everything here, so if you're curious about a function look at the previous section.

RemoveAll

Well there is removeAll(), which quite literally removes everything. But more helpfully, there is removeAll(where shouldBeRemoved: (Element) throws -> Bool) rethrows. Hmmm... This looks awfully familiar. Referring back to our decomposition of first, we can simplify this function by throwing out the error handling: removeAll(where: (Element) -> Bool). So this function takes in another function that takes in an argument and returns a bool. Aka we are taking in a function that will either determine if that element should be removed or not and just applies that to every element in a list.

Going back to our Person data structure:

var people: [Person] = ...
let noNoahs = people.removeAll { person in person.name == "Noah" }

Contains

If we want to see if an array contains an element that fulfills some critera, we use the contains function. This is exactly like first, last, everything we've talked about so far. Here's the header: contains(where predicate: (Element) throws -> Bool) rethrows. Additionally, if Element conforms to Equatable, we can use contains(_: Element) -> Bool. SeefirstIndex(of: Element) for an explanation.

Map

Map is a common function that maps from one list to another. The idea is that you apply a function that transforms an element into an element of another kind. This function is then applied to everything in a list, so the entire list is transformed. Maps type is map(_ transform: (Element) throws -> T) rethrows [T]. We can re-imagine map as:

extension Array {
    
    func map<T>(_ transform: (Element) throws -> T) rethrows -> [T] {
        var nextLst = [T]()
        for i in self {
            try nextLst.append(transform(i))
        }
        return nextLst
    }
    
}

Or a more simple version:

extension Array {
    
    func map<T>(_ transform: (Element) -> T) -> [T] {
        var nextLst = [T]()
        for i in self {
            nextLst.append(transform(i))
        }
        return nextLst
    }
    
}

Filter

Filter does pretty much exactly what you expect it's going to do. It goes through the array, checks criteria, and keeps elements that pass the critera.

Reduce

Reduce will iterate through the list and will return some form of accumulation. OCaml programmers think fold_left and fold_right. Reduce takes in an initial state and a function. Its accumulator starts at the initial state. Then it iterates through the list, applies the function to the accumulator and the next element in the list, and stores the result in the accumulator. It continues until the list is done. Think of reduce as:

extension Array {
    
    func reduce<Result>(_ initialResult: Result, _ nextPartialResult: (Result, Element) throws -> Result) rethrows -> Result {
        var accumulator = initialResult
        for i in self {
            accumulator = try nextPartialResult(accumulator, i)
        }
        return accumulator
    }
// or a simpler version
    func reduce<Result>(_ initialResult: Result, _ nextPartialResult: (Result, Element) -> Result) -> Result {
        var accumulator = initialResult
        for i in self {
            accumulator = try nextPartialResult(accumulator, i)
        }
        return accumulator
    }
    
}

Mixing map, filter, and reduce can feel so cool–while potentially inefficient. Let's try to do it. Say I have a list of words and integers in string form. I want to see the sum of even numbers in the list. Here's one way to do it:

let myList = ["0", "my", "1", "name", "2", "is", "3", "noah", "4"]
let myFilteredList = myList.filter {
    if let result = Int($0), result % 2 == 0 {
        return true
    }
    return false
}
let myIntegerList = myFilteredList.map { Int($0)! }
let myResult = myIntegerList.reduce(0, +)
// 6: Int

A few notes:

1. Int(_: String) is an optional initializer.

2. I can forceunwrap here because I already checked that I could transform the elements into an integer

And here it is as a one-liner

myList.filter({ if let result = Int($0), result % 2 == 0 { return true }; return false }).map({ Int($0)! }).reduce(0, +)

That's quite a long one-liner because of the optional... Let's fix that!

Compact Map

compactMap is exactly like map, except if result is nil, it will automatically be filtered!

let myList = ["0", "my", "1", "name", "2", "is", "3", "noah", "4"]
let myIntegers = myList.compactMap({ Int($0) })
myIntegers: [Integers] = [0, 1, 2, 3, 4]

With this new tool, let's try that one-linear again!

myList.compactMap({ Int($0) }).filter({ $0 % 2 == 0 }).reduce(0, +)
// 6: Int