Reduce(into: _) wins! (Swift 4.0)

For a little while now I have been casually poking around and learning Swift in the context of iOS development. One of the things that excited me about learning Swift was hearing it embraced many concepts from the world of functional programming. And, of course, no language could promise functional concepts and not implement some version of foldl, which hass been implemented as reduce(_:_:) on many of the typeclasses in Swift.

Recently with the release of Swift 4 comes a slightly different version of reduce known as reduce(into, _). This new named first argument has one very important difference: it is an inout argument.

For those who don't know, and inout argument in Swift is an argument which is mutatable within the body of the function.

Now, I know some people will see this new method and scream "Wait! But mutable variables break referential transparency!". You're not wrong. But sometimes practicality wins out. Let's take a look at a toy problem I solved recently and how reduce(into:_) makes all the difference.

The Problem

Divisors of 42 are : 1, 2, 3, 6, 7, 14, 21, 42. These divisors squared are: 1, 4, 9, 36, 49, 196, 441, 1764. The sum of the squared divisors is 2500 which is 50 * 50, a square!

Given two integers m, n (1 <= m <= n) we want to find all integers between m and n whose sum of squared divisors is itself a square. 42 is such a number.

The result will be an array of tuples, each tuple having two elements, first the number whose squared divisors is a square and then the sum of the squared divisors.

You can try the problem here.

The First Solution (Functional, slow)

func getDivisorsOf(_ n: Int) -> [Int] {
    return [Int](1...n).reduce([]) { n % $1 != 0 ? $0 : $0 + [$1] }
}

func getSumOfSquaresOf(_ ints: [Int]) -> Int {
    return ints.reduce(0) { $0 + ($1 * $1) }
}

func isSquare(_ n: Int) -> Bool {
    return sqrt(Double(n)).truncatingRemainder(dividingBy: 1.0) == 0
}

func listSquared(_ m: Int, _ n: Int) -> [(Int, Int)] {
    return [Int](m...n).reduce([]) {
        let sumOfSquares = getSumOfSquaresOf( getDivisorsOf($1) )
        return isSquare(sumOfSquares) ? $0 + [($1, sumOfSquares)] : $0
    }
}

Take a look at the closure used in getDivisorsOf. When the current item from the array, $1, is a divisor of n I have to create a new array, put the current item into it and then concatenate that to the accumulated array, $0. That operation generates two totally unnecessary array's which are immediately discarded for the final concatenated result. Unfortunately this is expensive. So much so that this solution failed to solve the problem in the time limit!

The Second Solution (Imperitive)

func getDivisorsOf(_ n: Int) -> [Int] {
    var divisors: [Int] = []
    for i in 1...n {
        if (n % i == 0) {
            divisors.append(i)
        }
    }

    return divisors
}

func getSumOfSquaresOf(_ ints: [Int]) -> Int {
    return ints.reduce(Int(0)) { $0 + ($1 * $1) }
}

func isSquare(_ n: Int) -> Bool {
    return sqrt(Double(n)).truncatingRemainder(dividingBy: 1.0) == 0
}

func listSquared(_ m: Int, _ n: Int) -> [(Int, Int)] {
    var results: [(Int, Int)] = []
    for i in m...n {
        let sumOfSqures = getSumOfSquaresOf( getDivisorsOf(i) )

        if isSquare(sumOfSqures) {
            results.append( (i, sumOfSqures) )
        }
    }

    return results
}

This solution simply replaces the reduce calls with straight for up loops. Using the append method, which mutates the original array, means that no throw away array's are generated on each step of the loop. This solution, when run in my terminal, solves the problem in about 1/3 the time as the first solution.

The Third Solution (Hybrid)

Now, intro reduce(into:_)

func getDivisorsOf(_ n: Int) -> [Int] {
    return [Int](1...n).reduce(into: []) { if n % $1 == 0 { $0.append($1) } }
}

func getSumOfSquaresOf(_ ints: [Int]) -> Int {
    return ints.reduce(0) { $0 + ($1 * $1) }
}

func isSquare(_ n: Int) -> Bool {
    return sqrt(Double(n)).truncatingRemainder(dividingBy: 1.0) == 0
}

func listSquared(_ m: Int, _ n: Int) -> [(Int, Int)] {
    return [Int](m...n).reduce(into: []) {
        let sumOfSqures = getSumOfSquaresOf( getDivisorsOf($1) )
        if isSquare(sumOfSqures) { $0.append( ($1, sumOfSqures) )}
    }
}

Isn't it beautiful?! Those verbose for loops, so prone to typo's, are gone in exchange for concise reduce closures and there is no need to create any throw away array's! 😃

I would even argue that the reduce closures are easier to read without the ternaries required in the first solution.

Ready for the best part? Using reduce(into:_) is much closer to the same execution time as the imperative solution.

Speed Test

To remove any confounding effects that might exist from the other operations involved in this solution we can look at these two simple functions:

func iterateImperitive(_ arr: [Int]) {
    var result: [Int] = []
    for n in arr {
        result.append(n * 2)
    }
}

and

func iterateFunc(_ arr: [Int]) {
    arr.reduce(into: []) { $0.append($1 * 2) }
}

When testing these on functions with an array of values from 1 - 1,000,000 I get these two execution times:

Imperative: 0.220044016838074
Functional: 0.244272947311401

Some quick division tells us that the functional approach takes 1.1101094718297049 as long to complete, or, about 11% , more time. This is a good deal more reasonable than the 3x, or 200% more time required to run the original solution. To me this means that, unless I know that I'm doing some kind of exponential array manipulation, I probably don't have to worry about the time difference. That being said, it is important to remember that you made this decision. When you start getting reports that your app is running poorly on older devices, it is things like this that become low hanging fruit for optimization.