Swift Talk # 150

## The Origins of Reduce

with special guest Wouter Swierstra

### This episode is freely available thanks to the support of our subscribers

Wouter joins us to explore the origins of the reduce function.

00:06 Today we are joined by Wouter Swierstra, Assistant Professor at Utrecht University and co-author of Functional Swift. One of the areas he works in is functional programming, and he's excited to see that some ideas from this field, in which people have been working for a really long time, are coming to a mainstream language like Swift.

00:44 Together we'll dive down the rabbit hole of functional programming during a few episodes. More specifically, we'll be looking at `reduce`. To remind ourselves what `reduce` does, we'll first write out some examples.

## Examples of reduce

01:14 We create an array that holds the numbers from one to ten, and we call `reduce` on it to find the largest number in the array. The function takes two arguments: an initial result value, and a function that combines a single array element with the result. We pass in the smallest possible `Int` as the initial value, and we use `max` for the combining function:

``````let numbers = Array(1...10)
numbers.reduce(Int.min, max) // 10
``````

01:53 We can also use `reduce` to calculate the sum of all elements by passing in zero and the `+` operator:

``````numbers.reduce(0, +) // 55
``````

02:23 Let's take a closer look at the function signature of `reduce` on `Array`:

``````func reduce<Result>(_ initialResult: Result, _ nextPartialResult: (Result, Self.Element) throws -> Result) rethrows -> Result
``````

02:42 The function is generic over its `Result` type. In the above two examples, the result type and the type of the array's elements are both `Int`, but these types don't have to match up. For example, we can also use `reduce` to find out if an array contains an element. The result of this `reduce` call is a `Bool`:

``````extension Sequence where Element: Equatable {
func contains1(_ el: Element) -> Bool {
return reduce(false) { result, x in
return x == el || result
}
}
}

numbers.contains1(3) // true
numbers.contains1(13) // false
``````

03:33 We call `reduce` with an initial result of `false`, because this has to be the result if the array is empty. In the combining function, we check if the passed-in element is equal to the element we're looking for or if the result thus far is `true`.

05:36 This version of `contains` is not the most performant because it does more work than it needs to. Nevertheless, it's an interesting exercise to find an implementation that uses `reduce`.

## List

05:55 But where does `reduce` come from? We can explore its origins by defining a singly linked list and finding a `reduce` operation on it.

In Swift, we define a linked list as an enum with a case for an empty list and a case for a non-empty list. The non-empty case is traditionally called `cons`, and its associated values are a single list element and a tail. The tail is another list, which makes the case recursive, so we have to mark it as indirect:

``````enum List<Element> {
case empty
indirect case cons(Element, List)
}
``````

07:26 We can create a list of integers, like so:

``````let list: List<Int> = .cons(1, .cons(2, .const(3, .empty)))
``````

08:08 Then we define a function called `fold`, which looks a lot like `reduce`, but it's slightly different:

``````extension List {
func fold<Result>(_ emptyCase: Result, _ consCase: (Element, Result) -> Result) -> Result {

}
}
``````

09:15 It's no accident that the two arguments of `fold` match up with the two cases of `List`. Within the function's implementation, we use each of these arguments with its corresponding case:

``````extension List {
func fold<Result>(_ emptyCase: Result, _ consCase: (Element, Result) -> Result) -> Result {
switch self {
case .empty:
return emptyCase
case let .cons(x, xs):
return consCase(x, xs.fold(emptyCase, consCase))
}
}
}
``````

11:07 Now we can `fold` the list to calculate the sum of its elements:

``````list.fold(0, +) // 6
``````

11:45 We can also use `fold` to find the length of the list:

``````list.fold(0, { _, result in result + 1 }) // 3
``````

12:20 There's correspondence between the arguments of `fold` and the declaration of `List`.

We can think of the enum cases of `List` as the two ways to construct a list: one to construct an empty list, and one to construct a non-empty list.

And `fold` takes two arguments: one for the `.empty` case, and one for the `.cons` case — exactly the information we need in order to compute a result from each of the cases.

13:18 If we think of the `emptyCase` parameter not as a value of type `Result`, but rather as a function, `() -> Result`, then the correspondence with the `.empty` constructor becomes even clearer.

## fold vs. reduce

13:44 The `fold` function is nearly identical to `reduce`, but there's a small distinction. The difference between the two can be demonstrated by calling both functions and comparing the results.

14:12 First we call `fold`, passing in the constructors of the two cases of `List` as the arguments:

``````dump(list.fold(List.empty, List.cons))

/*
▿ __lldb_expr_4.List.cons
▿ cons: (2 elements)
- .0: 1
▿ .1: __lldb_expr_4.List.cons
▿ cons: (2 elements)
- .0: 2
▿ .1: __lldb_expr_4.List.cons
▿ cons: (2 elements)
- .0: 3
- .1: __lldb_expr_4.List.empty
*/
``````

14:27 We see that the result is exactly the same as the original list. In other words, calling `fold` with the two case constructors is a complicated way of writing the identity function: nothing changes.

15:09 Then we `reduce` an array, passing in the same constructors of the `List` cases — except we have to swap the order of the arguments of the `cons` case, because `reduce` passes in the accumulating result first and the current element second:

``````dump(Array(1...3).reduce(List.empty, { .cons(\$1, \$0) }))

/*
▿ __lldb_expr_6.List.cons
▿ cons: (2 elements)
- .0: 3
▿ .1: __lldb_expr_6.List.cons
▿ cons: (2 elements)
- .0: 2
▿ .1: __lldb_expr_6.List.cons
▿ cons: (2 elements)
- .0: 1
- .1: __lldb_expr_6.List.empty
*/
``````

16:03 When we inspect the result from this `reduce` call, we see that it's a `List` containing the array elements in reverse order, because `reduce` traverses the array and processes each element into the result as it goes. This is different from what `fold` does, because it goes from left to right through the linked list and only uses the `emptyCase` value when it hits the very end of the list.

16:39 There are plenty of operations, like calculating a sum or a length, for which `reduce` and `fold` give the same result. But through operations in which the order matters, we start to see the difference in the behavior of the two functions.

## List.reduce

17:03 We've implemented `fold`, and we've used Swift's `Array.reduce`, but it would also be interesting to look at the implementation of `List.reduce`. We write the function in an extension, and we give it the same arguments as `fold`:

``````extension List {
func reduce<Result>(_ emptyCase: Result, _ consCase: (Element, Result) -> Result) -> Result {
// ...
}
}
``````

17:59 To implement the function, we assign the `emptyCase` parameter to an initial result, and then we switch over the list to see whether or not it's empty. If it's empty, we can return the result right away. If the list is non-empty, we add the `x` element to the result we've seen so far using the `consCase` function, and we recursively call `reduce` on the tail, passing on the accumulated result:

``````extension List {
func reduce<Result>(_ emptyCase: Result, _ consCase: (Element, Result) -> Result) -> Result {
let result = emptyCase
switch self {
case .empty:
return result
case let .cons(x, xs):
return xs.reduce(consCase(x, result), consCase)
}
}
}
``````

## Tail Recursion

20:15 Here we can see that `reduce` is tail-recursive: it either returns a result or it makes a recursive call immediately. `fold` is not tail-recursive because it calls the `consCase` function, and the recursion is more or less hidden and used to construct the second argument of that function.

20:50 This difference is what leads to the different results, which we can see even more clearly now by comparing the two methods on `List`:

``````let list: List<Int> = .cons(1, .cons(2, .const(3, .empty)))
list.fold(List.empty, List.cons) // .cons(1, .cons(2, .const(3, .empty)))
list.reduce(List.empty, List.cons) // .cons(3, .cons(2, .const(1, .empty)))
``````

21:28 An operation using tail recursion can very easily be rewritten with a loop:

``````extension List {
func reduce1<Result>(_ emptyCase: Result, _ consCase: (Element, Result) -> Result) -> Result {
var result = emptyCase
var copy = self
while case let .cons(x, xs) = copy {
result = consCase(x, result)
copy = xs
}
return result
}
}
``````

22:59 This version, `reduce1`, produces the same result as `reduce`:

``````list.reduce1(List.empty, List.cons) // .cons(3, .cons(2, .cons(1, .empty)))
``````

## Coming Up

23:18 `reduce` is just one example of a folding operation, and we can actually define these operations on many other structures as well, as we'll see next time.

### Resources

• #### Sample Code

Written in Swift 5

See All
SwiftUI

### Integrating UIKit Components

Episode 161 · Jul 17

SwiftUI

Episode 160 · Jul 12

SwiftUI

### Passing Data Around

Episode 159 · Jul 05

SwiftUI

### The Swift Talk App: First Steps

Episode 158 · Jun 28

SwiftUI

### Asynchronous Networking with SwiftUI

Episode 157 · Jun 21

SwiftUI

### A First Look at SwiftUI

Episode 156 · Jun 14

Unlock Full Access

## Subscribe to Swift Talk

• ### Watch All Episodes

A new episode every week