Consider this problem: You're getting a list of persons from a JSON endpoint. You'd like to know the average age from all people living in California. The parsed data looks like this:

let persons: [[String: AnyObject]] = [["name": "Carl Saxon", "city": "New York, NY", "age": 44],
 ["name": "Travis Downing", "city": "El Segundo, CA", "age": 34],
 ["name": "Liz Parker", "city": "San Francisco, CA", "age": 32],
 ["name": "John Newden", "city": "New Jersey, NY", "age": 21],
 ["name": "Hector Simons", "city": "San Diego, CA", "age": 37],
 ["name": "Brian Neo", "age": 27]]

Note the last entry, which omits a city for the person in question. Those cases have to be silently ignored.

The expected result in the example would be 3 persons , as we have three persons from California. Let's try to implement this in Swift in terms of flatMap and filter. The flatMap is used instead of map as flatMap automatically ignores empty optionals. So flatMap([0, nil, 1, 2, nil]) results in [0, 1, 2]. This eases the handling of persons without a proper city.

func infoFromState(state state: String, persons: [[String: AnyObject]]) 
     -> Int {
    return persons.flatMap( { $0["city"]?.componentsSeparatedByString(", ").last })
	   .filter({$0 == state})
	   .count
}
infoFromState(state: "CA", persons: persons)
//#+RESULTS:
//: 3

That's simple enough.

However, now consider the following complication: You'd like to know how many of those persons live in California, and you'd like to know their average age. If we try upgrading the above example, we soon realize that his is a slightly harder problem. There are various solutions, but they all seem to not fit well with functional constructs. A loop-based approach feels much simpler.

When we think about why this does fit, we realize it is because the shape of the data changes. map, flatMap, and filter all keep the shape of the data similar. Array goes in, array goes out. The amount and the contents of the array may change, but the array-shape stays. The problem above, however, requires us to change the shape to a struct or tuple with an Integer average and an Integer sum.

These are the kind of problems where you can apply reduce.

Reduce is sort of a generalized version of map, flatMap, or filter. The basic idea is to reduce a sequence into a different shape utilizing an accumulator that can keep incremental state. To do this, we hand the function a combinator closure/function/method which is called once for each item in the sequence. This may sound complicated but becomes really easy with a couple of examples.

It is a method on SequenceType and looks like this (simplified):

func reduce<T>(initial: T, combine: (T, Self.Generator.Element) -> T) -> T

So we have an initial value, and we have a closure which expects us to return the same type as the initial value. The final value of the operation is also of the same type as the initial value.

If we take a very simple reduce operation - adding up a list of integers, the evaluation will look like this:

func combinator(accumulator: Int, current: Int) -> Int {
   return accumulator + current
}
[1, 2, 3].reduce(0, combine: combinator)
// The following steps will be performed
combinator(0, 1) { return 0 + 1 } = 1
combinator(1, 2) { return 1 + 2 } = 3
combinator(3, 3) { return 3 + 3 } = 6
= 6

The combinator function will be called once for each item in the list [1, 2, 3]. The state will be kept in the accumulator variable which is just an Integer.

Let's start re-implementing some of our other, trusted, functional programming friends. In order to keep things simple for now, all these functions will operate on Int or Optional<Int>; i.e. we will ignore generics in here. Also, keep in mind that the implementations below exist to explain the behaviour of reduce. The native Swift implementations are usually much faster compared to the reduce versions below¹. Reduce shines in a different set of problems, which will be explained further below.

Let's start with a favorite of mine, the sum of a list of numbers:

[0, 1, 2, 3, 4].reduce(0, combine: +)
// 10

+ is a valid combinator function as it will just add the lhs and the rhs and return the result, which is specifically the requirement reduce has.

Another example is building the product of a list of numbers:

[1, 2, 3, 4].reduce(1, combine: *)
// 24

Or what about reversing a list:

[1, 2, 3, 4, 5].reduce([Int](), combine: { [$1] + $0 })
// 5, 4, 3, 2, 1

Finally, something a tad more complicated. We'd like to partition a list based on a division criteria

typealias Acc = (l: [Int], r: [Int])
func partition(lst: [Int], criteria: (Int) -> Bool) -> Acc {
   return lst.reduce((l: [Int](), r: [Int]()), combine: { (ac: Acc, o: Int) -> Acc in 
      if criteria(o) {
	return (l: ac.l + [o], r: ac.r)
      } else {
	return (r: ac.r + [o], l: ac.l)
      }
   })
}
partition([1, 2, 3, 4, 5, 6, 7, 8, 9], criteria: { $0 % 2 == 0 })
//: ([2, 4, 6, 8], [1, 3, 5, 7, 9])

The most interesting thing we're doing above is using a tuple as the accumulator. As you'll find out, once you start trying to incorporate reduce into your daily work-flow, tuples are a great way of quickly combining related data during a reduce operation.

Apart from the higher flexibility that reduce offers, it has another advantage: Oftentimes, chaining map and filter induces a performance penalty as Swift has to iterate over your collection multiple times in order to generate the required data. Imagine the following code:

[0, 1, 2, 3, 4].map({ $0 + 3}).filter({ $0 % 2 == 0}).reduce(0, combine: +)

Apart from being nonsensical, it is also wasting CPU cycles. The initial sequence will be iterated over 3 times. First to map it, then to filter it, and finally to sum up the contents. Instead, all of this can just as well be implemented as one reduce call, which greatly improves the performance:

[0, 1, 2, 3, 4].reduce(0, combine: { (ac: Int, r: Int) -> Int in 
   if (r + 3) % 2 == 0 {
     return ac + r + 3
   } else {
     return ac
   }
})

Here's a quick benchmark of running both versions and the for-loop version below over an list with 100.000 items:

var ux = 0
for i in Array(0...100000) {
    if (i + 3) % 2 == 0 {
	ux += (i + 3)
    }
}

As you can see, the reduce version' performance is very close to the mutating for loop and more than twice as fast as the chaining operation.

However, in other situations, chained operation can greatly outperform reduce. Consider the following example:

Array(0...100000).map({ $0 + 3}).reverse().prefix(3)
// 0.027 Seconds

Array(0...100000).reduce([], combine: { (var ac: [Int], r: Int) -> [Int] in
    ac.insert(r + 3, atIndex: 0)
    return ac
}).prefix(3)
// 2.927 Seconds

Here, we have a stark performance difference of 0.027s for the chained operation vs. 2.927s for the reduce operation, what's happening here?²

foBrowsing on Reddit points out that reduce's semantics means that the parameters to the closure (if mutated) are copied once for every element in the underlying sequence. In our case, this means that the accumulator parameter ac will be copied for each item in our 0…100000 range. A better, more detailed explanation of this can be found in this Airspeedvelocity blog post.

So, when you're replacing a set of operations with reduce, always keep mind whether reduction is indeed a good use case for the situation in question.

We can now go back to our initial count & average problem and try to solve it with reduce.

  func infoFromState(state state: String, persons: [[String: AnyObject]]) 
      -> (count: Int, age: Float) {

      // The type alias in the function will keep the code cleaner
      typealias Acc = (count: Int, age: Float)

      // reduce into a temporary variable
      let u = persons.reduce((count: 0, age: 0.0)) {
	  (ac: Acc, p) -> Acc in

	  // Retrive the state and the age
	  guard let personState = (p["city"] as? String)?.componentsSeparatedByString(", ").last,
		personAge = p["age"] as? Int

	    // make sure the person is from the correct state
	    where personState == state

	    // if age or state are missing, or personState!=state, leave
	    else { return ac }

	  // Finally, accumulate the acount and the age
	  return (count: ac.count + 1, age: ac.age + Float(personAge))
      }

  // our result is the count and the age divided by count
  return (age: u.age / Float(u.count), count: u.count)
}
print(infoFromState(state: "CA", persons: persons))
// prints: (count: 3, age: 34.3333)

As in earlier examples above, we're once again using a tuple to share state in the accumulator. Apart from that, the code is easy to understand.

We also defined a typealias Acc within the func in order to simplify the type annotations a bit.

This was a short overview of the power behind the reduce method. It is particularly helpful if you end up chaining a lot of functional methods together, or when output shape of your data differs from the input shape. I'll end this post with more reduce examples to give you inspirations for various use cases where reduce can easily be applied:

The following examples display additional reduce use cases. Keep in mind that they're educational in nature. I.e. they exist to stress the usage of reduce, not to be general solutions for your codebase. Most of the examples can be written in a better and faster way (i.e. by using extensions or generics). There are better implementations of these examples in various Swift libraries such as SwiftSequence or Dollar.swift

12/01/2015

• Fixed the rFlatMap type signature
• Added additional explanations for the code examples
• Fixed issue where performance differences were attributed to laziness