Deriving Transduction: Extracting Reduce

[00:00:00]
>> Kyle Simpson: Let's dive into deriving transduction, okay? Again, strap on your seatbelts, because I know that this is gonna get a little complex. To help ease the pain of what we're about to talk about. I wanna give you an anecdote from my days in algebra back in like eighth or ninth grade, and some of you may relate to this particular story.

[00:00:24]
This used to drive me absolutely nuts in my math classes because for example, the teacher would be up at the front of the room and she'd be teaching us how to take some algebra equations. On one side it's got like x squared minus three and the square root of that, and then on the other side some other kind of thing.

[00:00:47]
And what we're trying to do is like solve for x, okay? And so we're like down each side. We're doing different thing, s and at some point you get to a point where it's not at all obvious how you can keep reducing either side of it. It's like, well, this one has a square root, and this is cubed, and I don't know what mathematically I can do with both of those things.

[00:01:09]
And then the teacher, she'll say, well, what do we do next? And everybody's like,
>> Kyle Simpson: Well, I don't know. And then, she gets this glimmer in her eye. This is like 30 years ago and I still feel like this is today. She gets this glimmer in her eye and she says, what if we multiply both sides by 2x squared to the fourth, or whatever?

[00:01:33]
And you're like what? It's completely out of thin air, you just pulled something entirely completely unrelated to this. But sure enough when you multiply both sides by this weird thing, everything just fixes itself. I don't know if anybody can relate to this, but I see some nods, some of you seem to have had similar experiences.

[00:01:52]
This used to absolutely drive me insane. Because I go up after class, I was that annoying student I wanted to understand. And I'd go up after class and I pestered the teacher, I'd say, how did you know about 2x squared to the fourth, or whatever? Like how did you know?

[00:02:07]
And the most annoying response was, well, I've just done it before, right? I knew it because I've done it before. I had an intuition that maybe it would work and it did. Because the obvious point is, well, if you had that intuition how am I supposed to develop that intuition?

[00:02:24]
And the frustrating response is, you just got to do it a bunch, right? You just gotta do it and screw up a bunch, and then eventually you get to the point where you've seen something like that before and it occurs to you to try this, out of the box thing and it works.

[00:02:40]
I share that anecdote with you, because that's exactly what I'm about to do slide after slide, after slide. I'm about to pull stuff completely out of thin air that would completely never occurred to any of you. It would never have occurred to me in a million years to try these things.

[00:02:56]
But somehow the mathematicians tried it and tried it, and tried it. And it just makes it work. I can't explain the math to you, but I can tell you, I can explain from a programming perspective sort of what's going on, okay? So when you feel like, why would you try that?

[00:03:11]
That's exactly what I feel like. Why did they try it? I don't know. Other than that it works, okay? So let's start again from the beginning. We have this map filter and reduce. And we observed that clearly maps filters don't compose with each other and they definitely don't compose with reducers.

[00:03:29]
As a matter of fact, two reducers don't compose together. Two high order reducers to transistors do but two reducers can't even compose together. So these are clearly not of the right shape and we've gotta change some shapes around to make this stuff work. So how are we gonna do that?

[00:03:46]
Well, number one, we want to observe that mapping and filtering can fundamentally be modeled as a reduction operation. And I mentioned this earlier in the course, but now I'm gonna show you how we do it, okay? So what we're first gonna do is take the map and the filter parts, and do them with reductions.

[00:04:05]
Lets look at the top. I'm going to use my little cursor here to help you, cuz there's a lot of code on this slide. So I'm gonna to help you know what to focus on. mapWithReduce, this utility here, mapWithReduce is taking in an array and a mapping function, okay?

[00:04:20]
And it's going to call array.reduce on it. So all of a sudden you see we're doing a mapping operation, but we're doing it with a reducer, okay? So what does that reduce are going to do? Well, first to draw your attention to here. We're gonna start with an empty array is the initial value for this reduction.

[00:04:37]
The general strategy for using reduced to do a map or a filter is, you make a new list and then you stick stuff into it. So our initial value starts out as an empty list and our reducer says I'm going to push into that new list that accumulator list every time, the result of calling mapping function on V.

[00:04:59]
And then return that list. So in other words our reduction is not actually getting the new value every time, it's just getting a growing and growing array list. Everybody follow me there? The same technique is gonna be true when we do the filter. We are going to call arr.reduce, line nine.

[00:05:20]
And we are gonna first call the predicate function and if it returns true, stick it in the list. Otherwise, just don't do anything with that value. It's not like we need to throw it away, we just don't put it in the new list and then we just always keep returning that list every time.

[00:05:37]
So both of those have the same strategy, which is start out with an empty array, go through the original array, and decide what values to stick into the new array. That's how we do map and filter operations with a reduce. Okay, so let's take a deep breath. Did I lose anyone at that point?

[00:05:57]
Did that make sense to you how we can do both maps and filters with a reduce? I wanna call something out. We're gonna come back to this, but I wanna call something out just so that you're trying to develop this instinct as a functional programmer here. What am I doing on line three?

[00:06:17]
>> Speaker 2: Mutating an array
>> Kyle Simpson: I am mutating an array that was passed in. Does that smell like a side effect to anyone? It absolutely is a side effect. So you might think to yourself, maybe the better way of doing this instead of mutating the array would have been to create a brand new array that has the value appended onto it.

[00:06:36]
And that generally would be absolutely how you would want to do a map with a reduce, okay? But I'm specifically cutting a corner here, which is gonna turn out to in the math, it's gonna wash out, it's gonna factor out, it's not gonna matter. But I just want you to get that intuition of looking for side effects and avoiding them.

[00:06:58]
The only reason we're using this here is because the whole point of transduction is a performance optimization. We're deliberately in the math allowing ourselves to cheat just a little bit and in the end, the solution works out, okay? But don't in a general sense, just ignore those sorts of side effects they are important to pay attention to.

[00:07:19]
Okay, so we have map with reduce and we have filter with reduce. What's happening down on the bottom is that we are calling first mapWithReduce. Now we're calling them as standalone utilities instead of chained methods, right? We're passing list with the mapper add1. And then we're passing that new list, that mapped list into filterWithReduce using the isOdd predicate.

[00:07:43]
And that new list is the thing that we then reduce with our sum reducer. And result still ends up at 42. Okay, so we have a mapWithReduce and a filterWithReduce, but it would be easier for us to get those reducers to be shaped together to compose if we extracted the reducer out of these utilities, right?

[00:08:07]
These utilities are standalone, they do the reduction for us. But what if we just have these utilities give us the reducer that we could use. So we're gonna make these utilities instead of do the list thing. We're gonna make these utilities return us a reducer. And then we'll do the reduction ourselves.

[00:08:26]
Follow me? So let's do that. Let's change the mapWithReduce and the filterWithReduce to instead of doing the reductions to just produce the reducer for us, and we'll do the rest. Here's what that looks like. I now have a utility called mapReducer, which only takes a mapping function. It doesn't need to concern itself with the list at this point.

[00:08:47]
It's just gonna take the mapping function. And it's gonna make me a reducer that could reduce any list with that mapping function. That's what happening up on lines two through five, is it's making a reducer that's hard coded into use that mapping function. See a mapping function there on line three?

[00:09:04]
Back up, see a mapping function there on line three? It's hard coded into this reducer via closure, okay? The same thing is happening lines eight through 13, we are going to pass in a predicate function and create a reducer that is hard coded to use that predicate function in it's test of whether it should push something into a list or not.

[00:09:30]
Everybody with me here? So down at the bottom, what we're doing now is we have three separate reduce calls. We create one reducer line 18 by passing in our mapper. We create another reducer line 19 by passing in isOdd. And then, we already have the sum reducer ready to go.

[00:09:52]
So that's how we end up creating the chain of three reductions. We still haven't put the reducers together, but can everybody agree? Now that we've got three reducers, we've made some significant progress because those things definitely are shaped more similarly together, or at least on the track towards being able to compose them together.

[00:10:13]
Are you with me? Any questions about that step of the derivation, extracting out our reducers?
>> Kyle Simpson: Yes?
>> Speaker 3: So reduce is like the adapter, right? Can you say that, I mean.
>> Kyle Simpson: I'm not sure what you mean by that.
>> Speaker 3: That it's the one that's gonna bring the other functions together, right?

[00:10:41]
>> Kyle Simpson: Not exactly. So what's gonna bring, reduce is sort of the interface.
>> Speaker 3: That's, I mean-
>> Kyle Simpson: It's not the adapter, it's the interface. We're saying, the shape of a reducer is the thing that is mathematically capable of being composed together with any other reducer but actually it's higher order reduces that composed together.

[00:11:02]
Yeah.
>> Speaker 3: [INAUDIBLE]
>> Kyle Simpson: Okay, so reduce kind of just this interface that we know through the math we know is gonna work out for us.