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

Subscribers get exclusive access to new and all previous subscriber-only episodes, video downloads, and 30% discount for team members. Become a Subscriber

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 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 if it's empty or not. 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.

Recent Episodes

See All

Unlock Full Access

Subscribe to Swift Talk

  • Watch All Episodes

    A new episode every week

  • icon-benefit-download Created with Sketch.

    Download Episodes

    Take Swift Talk with you when you're offline

  • Support Us

    With your help we can keep producing new episodes