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)
```

01:53 We can also use `reduce`

to calculate the sum of all elements by
passing in zero and the `+`

operator:

`numbers.reduce(0, +) `

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) numbers.contains1(13)
```

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, +) `

11:45 We can also use `fold`

to find the length of the list:

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

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))
```

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) }))
```

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) list.reduce(List.empty, List.cons)
```

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) `

## 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.