High Order Functions Principles

In this writing, I will demonstrate the workings of higher-order functions in Swift. Although it might seem challenging at first, after using them, getting accustomed becomes easier. One important aspect to consider when dealing with higher-order functions is “Complexity.”

“Complexity” refers to a term used to evaluate the runtime or resource usage of an algorithm or program. It is often used to understand how the performance of an algorithm or program changes as the size of the dataset or the number of inputs increases. Complexity is measured in two fundamental types:

1. Time Complexity: It assesses the processing time of an algorithm based on the size of the input. It is usually expressed using the Big O notation. For instance, O(n) time complexity indicates that the processing time will increase proportionally as the input size ’n’ increases.
2. Space Complexity: It evaluates how much memory a given algorithm uses based on the input size. Similarly, it’s expressed using the Big O notation. For example, O(n) space complexity indicates that the amount of memory used will increase proportionally as the input size ’n’ increases.

Complexity analysis is employed to compare how different algorithms or approaches perform as the dataset grows and to choose more efficient algorithms. Lower time or space complexity implies better performance and more efficient resource usage.

When calculating complexity, if higher-order functions are nested, their complexities are multiplied; otherwise, they are added.

func sumOfArray(_ array: [Int]) -> Int {
    var sum = 0
    for _ in 0..<array.count {
        for number in array {
            sum += number
        }
    }
    return sum
}

let numbers = [1, 2, 3, 4, 5]
let totalSum = sumOfArray(numbers) //

In the example mentioned above, due to the nested usage of for loops, the complexity is calculated as

O(n) . O(n) = O(n²)

Similarly, for two higher-order functions that are not nested and have a complexity of O(n) each, their combined complexity is

O(n) + O(n) = O(2n)

However, within the Big O notation, constant terms are often negligible, so instead of O(2n), it can be simplified to just O(n).

Below, I will provide the complexities of the discussed higher-order functions:

.filter O(n)

.sort O(n logn)

.map O(n)

.forEach O(n)

for loop O(n)

.filter

The filter function is a higher-order function used to filter elements of a collection based on a specified condition. Typically used with arrays or collections, it selects elements that satisfy a given condition and returns a new collection as a result. The working principle of the filter function is as follows:

1. It checks the specified condition for each element in the original collection.
2. If an element satisfies the condition, it is added to a new collection.
3. After processing all elements, a new collection containing elements that meet the condition is returned.

Here’s an example using the filter function in Swift:

let numbers = [1, -2, 3, -4, 5, -6, 7, -8] 
let positiveNumbers = numbers.filter { $0 > 0 } 
print(positiveNumbers) // Output: [1, 3, 5, 7]

The underlying mechanism of the function involves iterating over the collection and evaluating a specific condition on each element.

To illustrate the same concept using a custom implementation, you can define a customFilter function using an extension on the Array type:

extension Array {
    func customFilter(_ isIncluded: (Element) -> Bool) -> [Element] {
        var result: [Element] = []
        for element in self {
            if isIncluded(element) {
                result.append(element)
            }
        }
        return result
    }
}

let numbers = [1, -2, 3, -4, 5, -6, 7, -8]
let positiveNumbers = numbers.customFilter { $0 > 0 }
print(positiveNumbers) // Output: [1, 3, 5, 7]

The customFilter function demonstrates the core principle behind Swift's standard library filter function and works similarly. However, the original function is more optimized and designed for general usage.

.sort

The sort function is a higher-order function used to rearrange the elements of a collection based on a specified sorting order. For example, you can use the .sort function to sort numbers in ascending or descending order. The basic working principle of the sort function involves the following steps:

1. Iterate over the elements of the collection.
2. Determine a comparable value for each element based on a specific sorting criterion.
3. Sort the elements based on these comparable values. For instance, if sorting numbers in ascending order, their values are used.
4. Return the sorted collection.

Here’s an example of using the .sort function in Swift:

var numbers = [5, 2, 9, 1, 5, 6]
numbers.sort(by: { $0 > $1 })
print(numbers) // Output: [1, 2, 5, 5, 6, 9]

As an analogy, you can think of the basic operation of the .sort function in Swift like this:

extension Array where Element: Comparable {
    mutating func customSort() {
        for i in 0..<self.count {
            for j in i+1..<self.count {
                if self[i] > self[j] {
                    self.swapAt(i, j)
                }
            }
        }
    }
}

var numbers = [5, 2, 9, 1, 5, 6]
numbers.customSort()
print(numbers) // Output: [1, 2, 5, 5, 6, 9]

The customSort function illustrates the core principle behind Swift's standard library .sort function and works similarly. However, the original function is more optimized, designed for general use, and may include different sorting algorithms.

.map

The .map function is a higher-order function used to transform or process the elements of a collection. This function takes each element of the collection, applies a specified transformation or operation, and returns the results as a new collection.

The basic working principle of the .map function involves the following steps:

1. Initiate a loop over the elements of the collection.
2. Apply a specific transformation or operation to each element.
3. Add the values obtained from the transformation or operation as elements of a new collection.
4. Create a new collection with the transformed elements and return it.

Here’s an example of using the .map function in Swift:

let numbers = [1, 2, 3, 4, 5]
let squaredNumbers = numbers.map { $0 * $0 }
print(squaredNumbers) // Output: [1, 4, 9, 16, 25]

As an analogy, you can think of the basic operation of the .map function in Swift like this:

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

let numbers = [1, 2, 3, 4, 5]
let squaredNumbers = numbers.customMap { $0 * $0 }
print(squaredNumbers) // Output: [1, 4, 9, 16, 25]

.forEach

The .forEach function is a higher-order function used to perform an operation on each element of a collection, such as an array, set, or dictionary. This function allows you to apply a specified operation to each element in the collection.

The basic working logic of the .forEach function involves the following steps:

1. It sequentially iterates over each element.
2. Calls the specified closure or function on each element.
3. The closure or function does not return a value, meaning it doesn’t aim to make changes to the elements or create a new collection.

Here’s an example of using the .forEach function in Swift:

let numbers = [1, 2, 3, 4, 5]

numbers.forEach { number in
    print($0)
}
// Output:
// 1
// 2
// 3
// 4
// 5

As an analogy, you can think of the basic operation of the .forEach function in Swift like this:

extension Array {
    func customForEach(_ body: (Element) -> Void) {
        for element in self {
            body(element)
        }
    }
}

let numbers = [1, 2, 3, 4, 5]
numbers.customForEach { print($0) }
// Output:
// 1
// 2
// 3
// 4
// 5

for Loop

As we’ve seen in the high-order functions above, there’s actually a basic for loop underlying all of them. So, how does this basic loop structure come together?

1. Initialization: Before the loop starts, an initial value is set. This value is typically a number or the first element of a collection.
2. Condition Checking: In each iteration, the loop checks a condition. If the condition is true, the loop continues; otherwise, it terminates. Whether the condition is true or not is often determined by whether a counter variable has reached the final value or if the collection has been exhausted.
3. Performing an Action: In each iteration, the loop performs specific actions. These actions are usually contained within the loop’s code block.
4. Counter Update: In each iteration, a counter variable is updated. This update helps determine which stage the loop is in and when it should end. For example, in a for loop, the counter might be incremented, or in a loop that iterates over collection elements, the next element might be accessed.
5. Repetition or Termination: If the condition is still true, the loop returns to the beginning, and steps 2–4 are repeated. If the condition is no longer true, the loop terminates, and control proceeds to the code lines after the loop.

In summary, this basic loop structure outlines how loops work in programming. It provides a foundation for various loop constructs and high-order functions in programming languages.

let numbers = [1, 2, 3, 4, 5]

for number in numbers {
    print(number * 2) // Output: 2, 4, 6, 8, 10
}

We can think of the basic operation of a for loop as follows:

extension Array {
    func customForLoop(_ body: (Element) -> Void) {
        var index = 0
        while index < count {
            let element = self[index]
            body(element)
            index += 1
        }
    }
}

let numbers = [1, 2, 3, 4, 5]
numbers.customForLoop { number in
    print(number * 2) // Output: 2, 4, 6, 8, 10
}