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.
