In previous sections, we talked about functions as building blocks and explained that we can compose our applications with functions. If functions can be building blocks in our programs, then they should be cacheable! But how do we cache them? The answer is memoization.

Memoization is the process of storing the result of functions, given their input, in order to improve the performance of our programs. We can memoize pure functions as pure functions do not rely on external data and do not change anything outside themselves. Pure functions provide the same result for a given input every time. Therefore, we can save or cache the results (in other words, memoize the results) given their inputs and use them in the future without going through the calculation process.

To be able to understand the concept, let's look at the following example in which we will manually memoize the power2 function:

var memo = Dictionary<Int, Int>() 

func memoizedPower2(n: Int) -> Int { 
    if let memoizedResult = memo[n] { 
        return memoizedResult 
    } 
    var y = 1 
    for _ in 0...n-1 { 
        y *= 2 
    } 
    memo[n] = y 
    return y 
} 
print(memoizedPower2(n: 2)) 
print(memoizedPower2(n: 3)) 
print(memoizedPower2(n: 4)) 
print(memo) // result: [2: 4, 3: 8, 4: 16] 

As we can see from the example, we define a dictionary of the [Int, Int] type. We save the result of the function given its input to this dictionary.

This approach works properly but we need to manually modify and maintain a collection outside of the function to be able to memoize the results of the function. Also, it adds a lot of boilerplate code to each function that we need memoization for.

The advanced Swift session presented at the Worldwide Developers Conference (WWDC) 2014 (https://developer.apple.com/videos/play/wwdc2014-404/) provides a convenient function for memoization that can be used with any pure function.

Watching the video is highly recommended. Let's see if we can automatize this functionality and reuse it using the memoize function from that session:

func memoize<T: Hashable, U>(fn: @escaping ((T) -> U, T) -> U) -> (T) -> U { 
    var memo = Dictionary<T, U>() 
    var result: ((T) -> U)! 
    result = { 
        x in 
        if let q = memo[x] { return q } 
        let r = fn(result, x) 
        memo[x] = r 
        return r 
    } 
    return result 
} 

The function looks complex but don't worry, we will go through it in detail.

First of all, it is a generic function. Do not worry about generics, we will cover generics in detail in Chapter 5, Generics and Associated Type Protocols. Secondly, Hashable is used because we need to store T as a key in a dictionary.

If we look at the signature of the function, we see that the memoize function takes a function (fn) with two parameters and a return type. So the signature of fn, which is a function, is as follows:

((T) -> U, T) -> U 

The first parameter of fn is a function of the (T) -> U type and the second parameter is of the T type and finally fn returns U.

OK, the memoize function received fn, which is described in the preceding code snippet.

At the end, the memoize function returns a function of the (T) -> U type; in other words, the memoized version of the function that takes a T type and returns U type.

Now let's look at the body of the memoize function. First, we need to have a dictionary to cache the results. Second, we need to define the result type, which is a closure. In the closure body, we check whether we already have the key in our dictionary. If we do, we return it, otherwise, we call the function and save the result in our memo dictionary.

Now we can use this function to memoize the results of different function calls and improve the performance of our programs.

The following example presents the memoized version of the factorial function:

let factorial = memoize { 
    factorial, x in 
    x == 0 ? 1 : x * factorial(x - 1) 
} 

print(factorial(5)) 

The memoize function expects a closure as input; therefore, we can use the trailing closure syntax. In the preceding example, we provided the factorial function and x parameters as input to the closure and the line after the in keyword is the body of the closure. In the previous example, we used memoize for a recursive function and it works properly. Let's look at another example:

let powerOf2 = memoize { 
    pow2, x in 
    x == 0 ? 1 : 2 * pow2(x - 1) 
} 

print(powerOf2(5)) 

In this example, we use the memoize function to have a memoized version of the powerOf2 function.

Writing the memoize function once, we will be able to use it for any pure functions to cache the data and improve the performance of our programs.