Reduce: Combination

[00:00:00]
>> Kyle Simpson: Our third and final list/data structure operation that we're gonna look at, is called reduce. If map does transformation, and filter does inclusion or exclusion, depending upon your perspective, reduce combines values. It's a different sort of an operation, because it's not actually taking one individual value at a time and making some decision on it.

[00:00:23]
The other two, operate independently on individual values. For example, you could imagine implementing map or filter in an entirely parallel sort of scenario. If you had a million values in an array and you had a filter that was parallelizible across background threads. You could spin up a million background threads and do each filter operation entirely independent, because the decision is made only on that value, same thing with map.

[00:00:52]
And in fact in many scenarios, not JavaScript but in many other functional languages, they do actually implement things like map and filter entirely threaded. So that they can happen in parallel is for large data structures, but reduce can't really work that way, because reduce works with multiple values.

[00:01:09]
It makes its decision based upon the current running accumulator, as well as the next value. So it's not really readily parallelizable or independently parallelizable the way something like map or filter would be. So here's how it works, we start with a collection of values and we need to start with some sort of initial value that is appropriate for the list of values.

[00:01:29]
So if we have a list, I mean a collection of it, so if we have for example, an array of numbers, and we're gonna do something arithmetic with those numbers like addition. A good initial value might be zero, if we were gonna do multiplication or even division, a better number might be the number one, are you with me?

[00:01:52]
If we're gonna start with a set of strings and do like some sort of concatenation of all the strings, a good initial value would be an empty string. If we were gonna start with a list of promises and try to chain all those promises together, a good initial value might be an already resolved promise.

[00:02:09]
If we were gonna start with a list of functions and have one function call another and that function call another and so on and so on, aka, composition. We might start with the identify function as a good initial value, you with me? So you have to select an appropriate initial value for your reduction.

[00:02:29]
There are some special cased implementations of reduce which will, if you don't provide an initial value. They will select the first item in the collection as the initial value and start the reduction with the next value. That's a special casing not all implementations do that, that can be convenient, but not all implementations do it.

[00:02:49]
So generally, the problem is you need to select a good initial value, and sometimes that's easy like zero or empty string, and sometimes it's a little bit more awkward. So you have to be careful in selection of your initial value, but anyway, what it does is, whatever the current accumulator is, either the initial value, or if we're deep into the reduction.

[00:03:08]
It takes the current accumulated value, and then it adds in the next value in our collection, those two come in together, and somehow they get combined with a reducer. So they get combined, we take the number three and the number four and we combine them, we reduce them with addition, and that produces seven.

[00:03:29]
So now our new accumulator is seven, or we take two strings and we combine we reduce them with concatenation, and now we have one string. So our reducer function like we have a mapper and a predicate filter function. We have a reducer, which takes two inputs now takes the existing accumulator and the next value in the collection, and that reducer decides how to combine them.

[00:03:52]
,And by the way combination, the idea of reduction it's a very general concept, okay. You might think the only way to reduce two numbers would be to add them together or divide them or multiply them, but you could do a reduction that just picked one of the two.

[00:04:09]
For example you wanted to pick out all the evens you could do a reduction that just only selects evens, right, so combination is whatever you define it to be. Reduction is whatever you define it to be, but it is often times something where the values end up together in some way, like strings or numbers or functions or promises or whatever, okay?

[00:04:28]
So, the way it looks is we start with an initial value and we start adding stuff in, combining all of these down to a single discrete value.
>> Kyle Simpson: Often you would start with say, list of numbers and produce from a reduction, a single number as a result. Or start with a list of strings and have a single string, but it is not always the case.

[00:04:49]
Reduce is actually kind of swiss army knife of functional programming, because you don't even have to produce a single discrete value, you can produce another data structure from a reduce. You could start with a list of numbers and reduce that to an object with properties holding those numbers.

[00:05:05]
Or you could start with a list of numbers and produce a whole different list of numbers. As a matter of fact, counterintuitively, a list of numbers could be reduced to an even longer list of numbers.
>> Kyle Simpson: Okay? So it's a very general operation, in fact, it's so general, and we're gonna come back to this a bit later in this discussion.

[00:05:23]
It is so general that both map and filter can be implemented with a reduce.
>> Kyle Simpson: Think about this for a moment, if reduce, the way a reduce works, if at each operation I have an accumulator and I have a value, if my accumulator is a new list. Starts out empty, and I decide to put stuff into it, if I call the mapper function, and I take the value and I put it in, the end result is a new list that's been mapped.

[00:05:52]
Or if I did an if statement with a predicate and only put stuff in if the predicate reduced, the result of that reduction is a filter. So it's the swiss army, now it can produce any of the other operations, basically any of the other operations can be expressed in terms of reduction.

[00:06:07]
Tremendously powerful, but just don't get intimidated by it, you'll often just do basic reductions, like a list of numbers down to a number or something like that, okay. So how would we implement or reduce? Let's say that I had a list of lists, so I have a two dimensional array here, these are basically, it's like a list of tuples.

[00:06:27]
Remember we talked about two tuples before a two element array? Well, I'm gonna interpret my tuples as the first element representing a property name, and the second element representing a value. And I'm gonna reduce my list of tuples into an object, so here's my reduce, and you'll notice that my implementation of reduce is generic.

[00:06:49]
It doesn't know anything about what I'm gonna reduce over, it just knows that I'm reducing over an array and producing some new value. So we start with an initial value and we call the reducer with the current accumulator the RET variable and that's the current accumulator. And the next element, and whatever that returns becomes the next accumulated value.

[00:07:10]
And we just keep doing that over and over until we're done, we can pass that a list of tuples, and if our add to record reducer up at the top. Takes in a record, that's our object our running object that we're gonna build up, and it takes in a tuple.

[00:07:28]
I'm doing a destructuring there, this is partly just to be saving space on the slides, but I'm showing that my element is a tuple and I don't really care about the tuple. I care about the key and the value in the tuple, so I've got a desctructuring there that says, give me the key and give me the value, and I just make a new copy of the object.

[00:07:47]
That's what ...record does, and then I add in the next key, that bracket key is the computed property name from key and then I set the value. Why do you suppose I didn't just add the property to the object, why did I make a copy of the object every time?

[00:08:06]
>> Student: Because you don't wanna mutate the-
>> Kyle Simpson: I don't want to mutate, right? If I just added the key to the object, we'd end up with the same result, but now we would have had basically an impure reducer, creating a side effect at each iteration on some single shared object.

[00:08:24]
And that may or may not create bugs, in our particular case, it may be would have been safe. But it's a terrible idea to ever, ever, ever assume that it's okay for you to just mutate a value that somebody else passed to you that you don't control. Remember, we talked in immutability earlier in the course, anytime we receive a value assume that you're not allowed to mutate it, you've gotta make a copy of it if you wanna extend it.

[00:08:48]
So that's why we write to reduce our online 2 to make a copy of the object.
>> Kyle Simpson: Reduce of course is implemented on JavaScript arrays. Same thing, we start with an array, we call reduce with our reducer, and then we give it an initial value in this case the empty object.

[00:09:09]
>> Kyle Simpson: I wanna call something out about our reducer, because I wanna call back to something we talked about earlier in the course, which was the shape of things. Remember we talked about the shape of functions, look at the shape of our reducer and compare it to the say the shape of a mapper.

[00:09:27]
The shape of our reducer is that it takes in two values and produces one output, whereas the mapper function takes in one value and produces one output. So a map function is unary a predicate is unary, but a reducer is binary. And a little bit later in our discussion, the shape of these things, the relative shapes of them is gonna matter a whole lot.

[00:09:55]
When we're talking about trying to put things together if they don't have a compatible shape, they don't fit the Lego pieces don't fit, okay. So remember at the very beginning of this course I said, functional programmers love unary functions. The math, the way it works out, unary functions are just so easy, the Lego's just work together, we can compose them, we can do all kinds of stuff.

[00:10:16]
But when we have non unary functions, the next best thing is a binary function that looks like this, which is a reduce, okay. So essentially, any function that takes two inputs and somehow produces one output from those two inputs, can be thought of as a reducer, it fits that shape as a reducer.

[00:10:37]
And that's something I want you to keep in the back of your head for later on in our discussion.