Reduce

Map and filter get all the glory, but reduce is the quiet workhorse.

5 April 2017 ∙ Swift Language ∙ written by Greg Heo

Map and filter get a lot of attention, but I say reduce is the important one. Or if you’re interested in efficiency, how about this: you can build map and filter using reduce. If you’re going to learn about just one, pick reduce.

Functional Friends

Map has the useful behavior of performing some operation on every item in the sequence and collecting the results.

let words = ["hello", "there"]
let shoutyWords = words.map { $0.uppercased() }
// ["HELLO", "THERE"]

The input to map is a sequence of size n, and the output will also be of size n.

Next, filter lets you decide which items to keep (and which to discard) from a sequence.

let numbers = 0...10
let evenNumbers = numbers.filter { $0 % 2 == 0 }
// [0, 2, 4, 6, 8, 10]

The output size will be somewhere between 0 and n, depending on how many things get filtered.

What of reduce?

Reducing Reduce

Like the other two operations, reduce takes a sequence as input but its output is more generic: it can be anything you want!

For every turn of the loop, reduce passes the previous output along with the current item. That means you get a some state preserved between iterations and can build up the output however you need it.

For the first time through, you need to provide an initial starter “result” value. That means reduce takes two arguments:

1. The initial result value.
2. A closure that produces the next partial result.

Reduce will pass in the partial result and next value as arguments to the closure.

Using Reduce

The textbook example of reduce is finding the sum of numbers:

let primes = [3, 7, 31, 127]
let sum = primes.reduce(0) { (result, item) in
  return result + item
}

The first time through, reduce will call closure(0, 3) where 0 is the initial value and 3 is the first item. The result is now 0 + 3, or 3.

The next time through the loop, reduce will call closure(3, 7) where 3 is the result from last time and 7 is the next item. And so on.

At the end, we’ll have turned an array [Int] into the final result of type Int.

Building Reduce

Let’s have a look at how reduce is built in the standard library. As usual, the code will be inline below and you can see the code yourself on GitHub in SequenceAlgorithms.swift.

It’s pretty short once you get through the slightly gnarly function signature:

public func reduce<Result>(
  _ initialResult: Result,
  _ nextPartialResult:
    (_ partialResult: Result, Iterator.Element) throws -> Result
) rethrows -> Result {

There are a lot of Result types here — that’s the generic type describing what the final return value will be. This can be different from Iterator.Element, which is the type of the thing in the sequence.

The initialResult parameter is of type Result, and needs to be passed into the function as the first argument.

The second parameter is the closure that runs for each value in the sequence. The closure itself gets passed two arguments:

1. The result returned from the previous iteration.
2. The next item in the sequence.

Finally, the throws and rethrows keywords allow for closures that throw errors; these will be rethrown up the chain to the original caller if needed.

Accumulating Results

The accumulator variable will hold the cumulative result as we iterate through the sequence.

var accumulator = initialResult

We’ll start out with the initial result passed into the function.

Next up is the big iteration step:

for element in self {
  accumulator = try nextPartialResult(accumulator, element)
}

The accumulator gets replaced each time through the loop with the new partial value returned from the closure. Again, the closure here takes the previous result and the next element.

Just one more line to go:

return accumulator

By the end, all that’s left to do is return the last result.

Building Map

How might you build map with reduce? For simplicity, we’ll work with arrays rather than sequences.

Let’s think about map in terms of how reduce works:

• The result type will be an array
• The initial value should be an empty array
• For each turn of the loop, add an item to the array

extension Array {
  func mapUsingReduce<OutElement>(
    _ closure: (_ item: Iterator.Element) -> OutElement)
    -> [OutElement] {
      return self.reduce([]) { (partial, item) in
        return partial + [closure(item)]
      }
  }
}

The generic parameter OutElement is the type of element in the output array. The method takes a closure to perform the transform step of converting an Iterator.Element into an OutElement.

The reduce call is as expected here: start with an empty array, and keep adding to the accumulated array each time through the loop.

Can you think of how to write filter using reduce? How about sort? What other uses can you think of? How efficient is doing map this way vs actual map?

The Closing Brace

This is one of those times where learning how to use a hammer means every problem starts looking like a nail (to wrangle another turn of phrase). Whenever I need some kind of operation on an array, I start thinking of how I might do it with reduce.

That doesn’t mean I actually use reduce though — it isn’t the best solution for every problem! What I like about it is it makes me think through the basics: initial value, an incremental step, and how to slowly build up a return value.

Download Reduce.playground to check out the code and play around with it yourself.

}