Article 2: Fold / Reduce Higher Order Function
Fold / Reduce Higher Order Function
In this article I'm going to be focusing on loops that make use of an accumulation variable, for example:
- Sum of values
- Product of values
- Concatenation (sum of strings)
Scenario 1: Sum of Integer Values
We have an array of integer and need to return their combined sum.
Code:
func sum(values: [Int]) -> Int {
var total = 0
for value in values {
total += value
}
return value
}
print(sum(value: [1, 2, 3, 4, 5, 6, 7, 8, 9]) \\ 45
Ok, quite easy. We create a pure function with values parameter, to accept the array of integers that we need to sum, but what if instead of summing the values, we need to find the
product of the values.
Scenario 2: Product of Integer Values
Code:
func product(values: [Int]) -> Int {
var total = 1
for value in values {
total *= value
}
return value
}
print(product(value: [1, 2, 3, 4, 5, 6, 7, 8, 9]) \\ 362880
Ok, again a fairly easy task... but did you notice how much of the code is similar between the
`sum` and
`product` functions? Essentially we only changed the name, and these two lines:
Code:
var accumulator = 0 ---> var accumulator = 1
accumulator += value ---> accumulator *= value
The rest of the code is essentially duplication.
Ok, but how can we do this in a more "functional way"?
I say "more functional way", because if you look at both of the above functions; they both classify as
`Pure Functions`, i.e. no side effects.
Well..., so let's frame this part a little different: how can functional techniques assist us to reduce the amount of code duplication. So for this section we're going to use one the Higher-order Functions (HOF);
Fold (also is called reduce, accumulate, aggregate).
This takes a function, a collection of items and returns a value that is created by combining the items.
Code:
print([1, 2, 3, 4, 5, 6, 7, 8, 9].reduce(0, +)) // 45 (sum)
print([1, 2, 3, 4, 5, 6, 7, 8, 9].reduce(1, *)) // 362880 (product)
Huh?
I agree it's less code, ... but really WTF is going on, confused?
What's probably confusing the picture a bit is that I've chosen to use some
`Syntactic Sugar`; syntax within a programming language that is designed to make things easier to read or to express.
Before I try to explain what's going on; let me first remove the sugar by expanding those two examples.
Code:
print([1, 2, 3, 4, 5, 6, 7, 8, 9].reduce(0, { total, value in total + value })) // 45
print([1, 2, 3, 4, 5, 6, 7, 8, 9].reduce(1, { total, value in total * value })) // 362880
Ok, so let me help you with understanding of this; we basically have a function called
`reduce` that operates on a list of values (the array) and also takes two additonal parameter values:
- The Initial or starting value; which in this case is 0 for sum, and 1 for product.
- A Closure (or a block of code to process the values); this closure recieves two values: `total` & `value`; to which we then apply an operator, for example: `+` for sum, and `*` for product.
Too further alleviate any confusion, let's have a look at the function definition for
`reduce`
Code:
extension Sequence {
public func reduce<Result>(
_ initialValue: Result,
_ nextValue: (_ partialTotal: Result, Iterator.Element}) throws -> Int) rethrows -> Int {
var total = initialValue
for element in self {
total = try nextValue(total, element)
}
return total
}
}
}
Huh?... there's quite a bit of Swift specific syntax in this code; however let's ignore most of that and focus on the middle part of this function:
Code:
var total = initialValue
for element in self {
total = try nextValue(total, element)
}
return total
Does this seem at all familiar? Go back and look at the two functions (sum & product) that we defined at the beginning of this article. Yes, it's essentially same code.
`self` refers to the sequence of integer values (Array), the only part that looks a little different is this line:
Code:
total = try nextValue(total, element)
More specifically the second part
`nextValue(total, element)`. nextValue if you look at reduce function parameters refers to a closure i.e. a block of code that was passed in as a parameter. This block of code is provided with two values; the current
`total` and the next
`element` or next value in the sequence.
Let's look again at our expanded single line solution for sum:
Code:
print([1, 2, 3, 4, 5, 6, 7, 8, 9].reduce(0, { total, value in total + value })) // 45
The passed in closuure (or block of code) refers to this part:
Code:
{ total, value in total + value }
This basically says, we receive two values `total, value in`, and then proceed to add them together
`total + value`. This is a rudimentary example of a block of code (closure); far more complex logic and/or process can be performed in these closure. The only restrictions is that your block of code at the end, conforms to type of the closure:
Code:
nextValue: (_ partialTotal: Result, Iterator.Element}) throws -> Int
i.e. We are provided two values; `we add our processing code` and finally we're expected to provide a
`Int` return value. Btw the
`throw` keyword is simply telling us that whatever exception we encounter in the closure, will be thrown, similarly
`rethrows` keyword implies that any lower level exceptions will be passed upwards through the call stack, meaning that our originating command would be able trap for these.
Almost there...
Whew, so to summarize reduce is essentially the same accumulation process as our first two functions (sum & product). The benefit is that it helps to remove unnecessary code duplication for common aggregation processes, secondly it has been specifically designed for flexibility by using a closure i.e. a custom block of processing code.
Now if I've haven't completely lost you in the process of this explanation, let me try to explain ...
How exactly does the Sugar Syntax work?
Code:
print([1, 2, 3, 4, 5, 6, 7, 8, 9].reduce(0, +)) // 45 (sum)
As we said the closure receives two values:
`total` and
`value`. The
`+` symbol in the above code refers to the operator
`+`. Ok, so let's have a look at the function signature for the
`+` operator.
Code:
infix func +(lhs: Int, rhs: Int) -> Int { }
It takes two values (Left hand side & right hand side), adds them together and returns an Int. In Swift values passed to a closure are
tuples, and
tuples can be used as a substitute for function parameters, as long as they are provided in the same order. Which in this case it does; so
lhs =
`total` and
rhs =
`value`, because the expected parameters are a perfect match to the provided closure values.
Conclusion
Whew, ok that's enough for this article... You can expect matching `reduce` code examples for Java, C# and PHP (in due course), with one restriction; neither of them have support for sugar syntax as it relates to the
`+` and
`*` operators.
I really hope you're were able to follow along; please feel free to ask for more examples if you need them, even for more clarity on anything that you're struggling with.
Peformance Note:
[table="width: 80%, class: outer_border"]
[tr]
[td]It's also important to appreciate that the underlying code for Higher-order Functions are built by the compiler teams of each language, meaning they would have taken additonal steps to ensure that this code is highly performant.[/td]
[/tr]
[/table]
Bonus
As a bonus I'm a going to also include code on how we can use
`reduce` to solve the first Euler challenge (equivalent examples in Java, C# and PHP will also be made available).
The problem is as follows:
[table="width: 80%, class: outer_border"]
[tr]
[td]> Multiples of 3 and 5: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.[/td]
[/tr]
[/table]
Code:
print((1..<1000).reduce(0, {$0 + ($1 % 3 == 0 || $1 % 5 == 0 ? $1 : 0) }))
FYI the $0 and $1 are substitute
tuple tags that refer respectively to the first and second values that were passed to the closure i.e.
`total` and
`value`
![[)roi(]](/forum/data/avatars/m/8/8711.jpg?1563828683){kind=avatar}
