Functional-Light JavaScript, v2 Transducing

Transcript from the "Transducing" Lesson

[00:00:00]
>> Kyle: Now I'm gonna take you through, this is our scenario. Here we have a similar kind of fluent method chain, but now we have three separate operators that are adjacent to each other that don't have a compatible shape. And if I wanted to reduce those all or combine those, compose those three functions all into one operator that could work across the list, it's not gonna work as it stands.

[00:00:28] And the solution to that is to transduce. Now, I'm just gonna pause for a moment and explain almost at a meta level, what we're about to do, just so you don't get too lost. Because to be quite honest, transducing is a highly advanced topic within functional programming. Or at least, it's a highly advanced topic within functional like.

[00:00:50] I teach this, and have written about it, and I have been doing it for a while, and I still find it to be a bit confusing, a bit hard to get my brain wrapped around. So don't feel bad that what I'm about to take you through, is gonna be quite brain twisting.

[00:01:05] But what I'm gonna take you through, instead of just showing you how to transduce. Because the punchline here is that there's a transduce utility built into your favourite functional programming library, and you just need to pass the right stuff in and it will do the work for you.

[00:01:21]
>> Kyle: But I don't think that's good enough for me to just tell you, transducing's all you want to just call this utility. In this spirit of what we've been doing in this class, I want you to see how it works under the covers. So I'm gonna take you through a derivation.

[00:01:33] Transforming this code, step by step, into something that can be transduced. And those steps are going to be quite complex to understand. And they're gonna hurt your brain a little bit, cuz they hurt my brain and I've been doing this a lot. But you don't ever have to go through that set of steps again.

[00:01:52] It's just I need to take you through it once, so you can appreciate what transducing does for you. So even though this seems complex, transducing as an end user utility is actually very, very simple to use. You just have to understand, recognize where you need it, drop in that tool and use it.

[00:02:12] It's a very powerful power drill if you will. To do this set of derivations. To reshape these things into something that we'll compose, I'm going to several different junctures here. Pull a rabbit out of thin air if you will, I don't know if any of you remember, if you recall a similar situation of mine.

[00:02:41] I remember back in grade school, high school taking like an algebra class, and I remember that the teacher will be showing some crazy complex equation like x squared plus 3 is equal to 2x to the 4th plus 9 or whatever. And we get this thing down to some specific thing where the two sides of the equation, we couldn't figure out how to keep going any further in terms of reducing and solving it.

[00:03:11] And it would look like we were at an impasse. We'd say I don't know what to do, I don't know how to get x squared and x cubed to somehow work with each other. And the teacher would wait for a moment, and then a glimmer in her eye, and she'd say something like, ''what if I multiply both sides by 2x to the eighth'', or whatever she said.

[00:03:32] What if I multiply both sides by this some random thing? And she did it and all of a sudden, it just magically worked itself out. And I'd be like what? Where did this two x to the eighth plus nine then come from? That's completely out of thin air.

[00:03:50] How did you know that that was the thing that you should multiply it by? That used to drive me insane. And I go up to the teacher after class every single time and be like, how'd you know to do that? And the honest and truthful but unsatisfying answer was, well I've just done it before.

[00:04:10] I've done it enough that I just knew that was the right thing to do. What I'm about to take you through is a set of derivations, where I'm gonna pull some junk out thin air, like two x squared plus nine or whatever it is, and you're gonna be like, how did you do that?

[00:04:28] And my answer to you is I didn't. I read somebody else that did it, and I'm trying to practice enough that I can get my brain to that point, where I could have figured out. There is no way on earth that what I'm about to show you, is something that I would've independently come up with.

[00:04:43] The set of steps, the jumps that you make, I would never have figured it out. But I read some really great stuff from others, and learned what they did, and broke it down, and figured it out. And I'm using that as my journey, if you will, to try to learn to develop that same instinct.

[00:04:57] And so all I can say is that's what you're gonna have to do, if you wanna think like this higher level functional programmer does. You have to just practice that kinda stuff. So with that metapoint made, let's try to transform this step by step into something that we can traduce, that we can compose those incompatible utilities.

[00:05:20] The first thing that we could observe here, is that map filter and reduce themselves are incompatible. Much less the operators we're passing to them. They are incompatible. It would be really good, if we could somehow get this from a map filter reduce to just three reduces. And to do that, we can observe that because reduces are Swiss Army knife, we can implement a map operation with reduce.

[00:05:48] And we can implement a filter operation with reduce. As a matter of fact, we already did a filter operation with reduce in the previous exercise. So, the first step here is to reorganize map and filter as reductions. So now we'll end up, the goal will be to end up with three reduces instead of a map filter reduce.

[00:06:11] To do that, I'm gonna create a utility called mapWithReduce and filterWithReduce. So mapWithReduce on line 1, takes a list in a mapping function, and it calls the reduce on that list. And it started out, if you see there on line 5, it starts it out with an empty array.

[00:06:33] And it pushes the mapped value into that new array and then returns the list. So it just goes through the list, calling mapping function with each value and pushes it into the list. Why am I using push here instead of concat? Cuz again, anytime you start mutating something that you don't technically control, you should at least take a step back and ask.

[00:06:57] Well the reason is, because right there on line 5, I actually do control the empty array. Since it's contained within my function, I know it's predictable. I know it's trustable. And it's much more performance for me to mutate the list, than to create a new one every time.

[00:07:15] So that's an acceptable performance cheat if you will. But it's only because that's within the context of something I control. Everybody follow that? So map with reduce is pretty straight forward. FilterWithReduce is the same concept except on line 10, we only push in to the list if it passes the predicate function check.

[00:07:38] Same logic that you would think of, it passes the predicate push it in the list, if not just ignore it.
>> Kyle: Now, looking down at the bottom, we have three separate calls, all three of them are reductions. We have mapWithReduces a reduction, we have filterWithReduces a reduction. And then we call list.reduce on that end resulting list.

[00:08:03] We end up with the same value, 48. So we're still doing three different loops through the list. But at least they're three reductions now instead of three entirely different kinds of operations.
>> Kyle: The next step is that I'd like to describe this, instead of these standalone utilities. It'd be easier for me to illustrate and move forward if I could describe each one of those reductions as a reducer that I could pass to the built-in array method.

[00:08:34] So in other words, the reducer on line 2 and the reducer on line 9, I need to extract those reducers out and just produce those to be used. So I'm gonna make a map reducer and a filter reducer. On line 1, you see I'm just creating that same reducer and then on line 9, I'm creating that same reducer.

[00:08:57] So I am not doing the reduce, I am creating the reducer to be used on lines 18 and lines 19 respectively. But don't miss that there is one level of function wrapping in direction, this is a machine making machine here. Map reducer takes the mapping function to close over on line 1.

[00:09:21] And it returns the reducer, close the remapping function. Which is why on line 18, we have to pass in add one and on line 19, we have to pass in is on. And that produces those reducers. You want to pay very close attention to the shape of the things that we are creating.

[00:09:42] Look at the shape of the reducer. By shape I mean, what kind of inputs does it take? What kind of output does it produce? The shape of that reducer is that it takes two inputs and produces a single output. It's not actually that relevant how it puts them together or if it ignores them.

[00:10:01] It's the shape of two to one that we wanna think about. And generally speaking, the reducer is fundamentally doing this combination activity. It's taking two values, combining them into one. [COUGH] Now, the next step that we're gonna take is, again, a little out of thin air, like, why would you do that?

[00:10:27] But if you squint, and look at the function mapReducer and the function filterReducer, there is some commonality between those two. Specifically, they both push a value into the list and return the list. One of them uses a mapping function to do it. One of them has a predicate check but they both push a value into a list and return a list.

[00:10:56] What I'm gonna do is essentially factor out that commonality into a separate utility, then I'm gonna call listCombination. So listCombination takes a list and a value, pushes the value into the list and returns the list. That's what we see on lines 1 through 4. That's the commonality. And now you'll notice that I'm using listCombination on lines 8 and lines 14 respectively to do that part of the work.

[00:11:24] So on line 8 and line 14, we don't see it actually doing any dot push or anything like that. We just delegate to that list combination utility to let it do that commonality. We still call the mapping function on line 8 and we still have the predicate check on line 14.

[00:11:42] Look at the shape of listCombination and compare it to the shape of one of those reducers.
>> Kyle: They're fundamentally the same shape, aren't they? That's not an accident. That's on purpose. And that turns out that's gonna be the linchpin that helps a lot of this work.
>> Kyle: Now this next step is to take that listCombination and say instead of hard coding the listCombination, why don't we parametrize the listCombination that function itself.

[00:12:22] Because there are other kinds of combination that we potentially might wanted to do in the future. listCombination is a very specific thing which takes a value and pushes it in the list and returns it. But there are other things we could do like throw away the value or double the value or who knows what, right?

[00:12:44] So let's parametrize the combination function that we use. By parametrize I mean, in addition to passing in mappingFn on line 6, we also want to pass in what combination function to use. And, I'm going to go one step further and say, I really want to do those two arguments separately.

[00:13:07] I don't want to pass them in at the same time. Do we know about a utility that we learned earlier in this course that would allow us to pass in arguments one at a time?
>> Speaker 2: Partial.
>> Kyle: Partial has some of the arguments later, What was the other one that could pass in one argument and then another?

[00:13:30]
>> Speaker 2: Curry.
>> Kyle: Curry, so what I'm gonna do is I'm gonna make a map producer, that is the curry of a function that takes both a mapping function and the combination function. So line 6, I have a map producer that expects both of those utilities as parameters but they're not curry yet.

[00:13:51] And that currying is going to allow me to provide those independently. And now on line 8, you'll see that I'm using combined function on line 8 that was passed in through line 6. I'm using combined function on line 14 that was passed in through line 12. Now down at the bottom when I call mapReducer, and I call add1, I am passing in add1 as the mapping function, but only one argument at a time, since it's curried.

[00:14:25] And then when I call it the second time, I pass in listCombination, that's combineFn. Everybody follow that? Same is true for my filters. When I call filterReducer and pass in isOdd, that's my predicate function. And when I call it again, or the resultant function one more time, I pass in listCombination is combineFn.

[00:14:47] So you can still see listCombination being used on lines 8 and lines 14 respectively, but it's been parameterized which combination function to use.
>> Kyle: I know this is in the weeds. I know this is a jumbled mess of it. And even me standing up here and talking about it for the hundredth time.

[00:15:08] It's still deep in the weeds, I got it. Just stick with me. We're about to really start to make some progress here.
>> Kyle: What would happen If I called mapReducer add1 and I didn't call it the second time to provide a combiner, what is the shape of that function?

[00:15:32]
>> Kyle: The shape of that function is that it expects a combiner function, right? And the same is true of filterReducer. filterReducer(isOdd), that gives us a function that expects a combiner function. So we now have, if we think about it we now have two functions that are both expecting a combiner function.

[00:15:54] Now. I asked you just a moment ago to compare the shape of the combiner function with the reducer. And it turns out that the combiner function and the reducer function have exactly the same shape because they are basically one and the same. I'm using combiner function to keep it separate but it is essentially a reducer.

[00:16:15] So here's the trick that's gonna start to make all this unravel for us. Because they both take a combiner aka a reducer, the output of one of them can be the input to the other. The output reducer that comes from the call mapReducer add1 listCombination, that's a reducer.

[00:16:39] That reducer could be the combiner for the next one, because they have the same shape. And if the output of one can become the input of the other, what does that sound like?
>> Speaker 2: Composition.
>> Kyle: Does it sound like a composition? So that is what we are going to do.

[00:16:59] We are going to take that function mapReducer add1 and compose that with the filterReducer isOdd, that function. That is going to make a composed function which is expecting a combiner aka a reducer. When we pass in the combiner, it's gonna make a reducer out of the first one and that reducer is gonna be the combiner for the next one.

[00:17:27]
>> Kyle: So that's what this looks like, on line 19 I've made this thing called a transducer which is the composition of those two functions. Each of which is expecting and a combiner aka a reducer. And then on line 24 that is when I call the transducers and pass in the list combination.

[00:17:52] So follow with me the flow of logic here. When I pass in the list combination to the transducers it's coming into the function on line 19, the one that we created. That filter reducer isOdd; that's the one on the right. It's the one that's sitting there waiting for a combiner to be passed into it.

[00:18:10] So we're passing it in when we call it on line 24 so that combiner comes into the filter reducer. And it produces the reducer that we list out on line 13. That reducer from line 13, when it says combineFn on line 14, it means list combination okay? Now that reducer is the output of that call in the function composition on line 19.

[00:18:40] That reducer gets passed into the waiting function that was produced by mapReducer add1 who is sitting there waiting for a combination function. But we're just going to secretly give it a reducer instead. Not really secretly, but that's our trick. We're going to give it a reducer instead of a combiner.

[00:18:58] So now we're up on line 6 combineFn there, that combineFn is actually the reducer from line 13, you follow me? So let's look at what it does with that combiner function. On line 8 it says I wanna call that combineFn with a list and with the mapping of that value, you see that?

[00:19:25]
>> Kyle: That is gonna delegate to the reducer on line 14 which says I received a list and a now already mapped value. That's line 13, I'm going to call the predicateFn. And the predicateFn is going to check the mapped value and if it passes I'm going to stuff it in and if not I'm just going to skip over it.

[00:19:48] So line 8, while it looks like it's stuffing it into the list, it's only conditionally stuffing it into the list if it passes the predicate check. So the mapping and filtering have now been combined into one step,
>> Kyle: Which is why we now are down to two reduces at the bottom.

[00:20:08] We have a reduce across the transducer with a combiner function produces us a single composed reducer that does both the mapping and the filtering at the same time. I see lots of glazed over looks in eyes, I totally understand. I can't even tell you how many times I've said this, and explained this, and written about this.

[00:20:32] And taught it, it's still a bit [SOUND] to me too. Like I said earlier, I would've never have thought to do this myself. I'm amazed that real functional programmers came up with this but somebody smart did, okay? So now we have a reducer that we can produce with a list combination.

[00:20:55] But we have one last trick up our sleeve because our ultimate goal was to only process the list once. We're not doing it three times anymore, but now we're doing it twice.
>> Kyle: I want you to think about the shape of the sum function. I don't have it listed here, but just think visually.

[00:21:14] What does the sum function do?
>> Kyle: Some takes two inputs, an x and a y, and what does it do with them?
>> Speaker 3: Uses it.
>> Kyle: It combines them together, right? The sum function being used as a reducer here has exactly the same shape as a combiner.
>> Kyle: So what if, instead of passing in listComination on line 24, what if we just passed in sum?

[00:21:53] Think about how we've generalized what combining means. Now you understand why we needed to generalize the idea of combination. Because now we can say I don't need to go to an intermediary list. If my end result is I want it to be a number that gets added with another number, use this combiner, use the sum combiner.

[00:22:16] And you could potentially come up with any number of other kinds of combinations that you would want as your end result. But here we want the numeric edition. So on lines 24 and 25, the way we're gonna compose those, or put those two together, is we're just gonna get rid of listCombination entirely.

[00:22:34] And we're gonna pass in sum as the list combiner.
>> Kyle: And now we have one single reducer that does a map, and then a filter, and then the summation together all in one step. We only need to pass through the list once. That's how you derive what transducing does, and how it works.

[00:22:59] That's how you know it's not some magical black box, because even though that might have felt intimidating and a bit overwhelming. There isn't a single thing that I just said through that progression of slides that isn't exactly what I've already taught you for this entire course. It is just putting the Lego pieces together, which is really the heart of what I'm trying to teach you is to develop the instinct of how do I put these two Lego pieces together to make something useful?

[00:23:28] There isn't some magic trick there, it really was just do that and then do that and then do that and do that. And they're the right shape now, that's cool. That's really all it is. So that's why I wanted you to see how transducing works, to begin to help build that confidence that you already have developed the foundational things to do advanced stuff like transducing.

[00:23:54] You're already half way up the mountain, if you will. Just by learning things like currying, and function composition, and unary functions, and list operations like reduce, you already have the raw pieces to start putting together a really great system.
>> Kyle: But I don't want you to have to go through all of that crazy mental juggling every time you wanna use transducing.

[00:24:20] What I want you to do really is be able to recognize, I've got some adjacent operations that I wanna fuse together. They don't have the same shape, so that means I need to do transducing. Let me go use the transduced utility. So I wanna show you just how easy using the transduced utility is.

[00:24:38]
>> Kyle: I made one here, but there's one that you comes with every functional programming library. So literally, line 6 and line 8 are all you ever have to do, but here's how the transduced utility works. It takes four inputs It takes a transducer, which is the composed set of combiner functions or composed set of reducers.

[00:24:59] It takes a transducer. It takes a combined function to use, aka another reducer. It takes an initial value and a list to operate on. It's all pretty sensible stuff. How does it work? It calls transducer with the combine function. We know what that looks like. We just saw it on the previous slide, and that makes our reducer.

[00:25:19] Then it does a reduce across the list with that reducer starting with the initial value.
>> Kyle: So if I were to erase lines 1 through 4. Line 6 is really all you need to do to set up your transducer. You have to do the compose and map reducer and filter reducer our utilities that are gonna be provided to you by the functional programming librar.

[00:25:48] So you're gonna have a compose provided to you by the library, you're gonna have a mapReducer provided to you by the library, a filterReducer provided to you by the library, and a transduce utility provided to you by the library. All you need to supply is isOdd, add1, and your sum function.

[00:26:07] That's your business logic stuff. You just have to see this configuration, be able to recognize this configuration of how those Lego pieces go together, and the rest of that magic will happen for you.
>> Kyle: If line 8 said transduce, and I passed in that same transducer and then instead of the sum function, I passed in list combination.

[00:26:35] And instead of the 0 initial value, I passed in an empty array. What do you think I get back out? I get back out the individual constituent values that had been mapped and then filtered. So it's as easy as deciding what kind of combiner do I wanna use, and what is the appropriate initial value?

[00:26:55] And now armed with that trandsducer, I can do any kind of transduction across a list.