List Operations Solution: addn

[00:00:00]
>> Kyle Simpson: All right, let's get to the tough stuff. Let's look at item number five in the readme, which says, define an addn utility. Addn is supposed to receive a list of functions, which I'll call fns, it receives a list of functions. And it needs to add all of the values that are represented by all of those functions together and return us a final result.

[00:00:28]
So before I even write it, it should look this. We should be able to call addn and we should be able to say something like constant of three and constant of seven and five and nine. And that's four different functions and let's throw one more in there. Let's throw a constant of 11 and if I'm doing my math correctly that should end up giving us 35.

[00:00:57]
Okay? So that's the thing that we want to produce. We wanna be able to pass in any number of functions that are wrapped around values and have it add all of those together. Remember, in the setup to this exercise, I pointed out that if you take the eager approach, which is the call add two with two of these functions, and then immediately you get a number.

[00:01:19]
Well now you have a number but you still have a bunch of functions. And a number and a function are not something that can work together. They are not of the same sort. But if we were to take the approach of deferring that addition by wrapping everything in functions, well, then everything stays at the function level and they all work together better.

[00:01:38]
I'm gonna implement addn three different times. The first time I'm gonna implement it, I'm gonna do it with an iterative approach. Then we'll try the recursive, and then we'll try the list operator approach. All right, so, what is my strategy gonna be? Well, let me consider sort of a base condition.

[00:01:55]
You remember when we talked about recursion earlier in the course, we talked about base conditions. And even though this isn't a recursive solution, we still basically want to ask, how do I know when my iteration needs to finish? Well, if my fns dot length is greater than two, I'll just do a placeholder here.

[00:02:17]
If fns dot length is greater than two then I know I need to do more work. But if addn is passed only two functions, and we're just gonna assume for our purposes that we don't pass in any fewer than two. But if it's been passed two functions, then we're already sort of done with the work.

[00:02:38]
So all we really need to do is call the add to utility with fns of zero and fns of one. That's our base condition, right? We only need to do extra work if there are more functions in the list. So I'm gonna turn this from being an if statement into being a while statement.

[00:02:59]
I'm gonna iterate until I get my fns array down to a length of two. And I'm going to be modifying this fns array so immediately you should have a red flag that pops up. We definitely want to make a copy of the fns array rather than, I'm sorry, I forgot that we need to be gathering.

[00:03:22]
If we're passing them separately, we need to be gathering into an array. So we definitely wanna make a copy of an array. Although in this particular case, the fns array, since it was gathered for us, it's not referenced to anywhere else. So it's probably okay for us to modify.

[00:03:35]
But generally, you wanna make a copy of something and not modify something unless it's something that you actually own. Okay, so let's modify our array. Each time we iterate through, we want to reduce the array length by one. The way we're gonna do that is to take the first two elements in the array, which are gonna be functions, and we're gonna make a new function that wraps around both of those functions.

[00:04:03]
So I'm gonna basically try to pull off the first two elements of the array. Remember, every time I iterate, I'm gonna have a new array that I'm looking at. I'm gonna pull off the first two elements of the array and I'm gonna use an array D structure to do that.

[00:04:14]
I'm gonna say let and then we'll have fn0 and fn1 will be the first two elements in that array and then I'll gather everything else up into a rest argument and I will destructure the fns array. So I'm simply saying, give me a variable that points to the first one, a variable that points to the second one, and then gather everything else up into a secondary array called rest.

[00:04:40]
Now that I have fns of zero and fns of one, those two functions can be wrapped in a function and that function can be inserted back into the fns list. So what I'm gonna do is redefine fns to point at a function here, which we'll define in just a moment, and everything that's in the rest array.

[00:05:05]
So we'll spread out whatever's left in the rest array.
>> Kyle Simpson: What is this function going to do? Well, we're trying to defer the add2 work, rather than doing the add2 work now, we want to defer the add2 work. So this function just simply needs to say return add2 with fns of zero and fns of one.

[00:05:34]
>> Kyle Simpson: Conceptualize what's happening here. We're going to be taking two functions that have numbers in them and replacing those two with a single function that will eventually add them and has not added them yet but will eventually add them together, okay? And that function is now alongside of a bunch of other single functions that have numbers in them.

[00:05:54]
Every time we loop we take two functions and make them into one and then we take two more functions and make them into one, so the very first function in this array just gets as a bigger and bigger and bigger and bigger function wrapped around function, wrapped around function until at the very end, when functions of length is equal to two.

[00:06:14]
We have a giant function in the first position and a singular value function in the last position. And we pass both of those into the add utility. That big function, which will be in the position of fns of zero, it collapses itself, it computes all of its partial additions by calling add2 and adding that to add2 and adding that to add2 and it gives us back the number.

[00:06:40]
And that gets added to whatever is in fns of one. So let's test this. If my math was correct, this one should have produced for us the value 35. So let's test and see how it works.
>> Kyle Simpson: [LAUGH], of course, I get back this add, I need to call add2, right?

[00:07:07]
Because that's the utility we're using. And there we have the 35.
>> Kyle Simpson: Let me make sure I fix that before I forget. I used the wrong function. I wanna call add2, not add. Okay, any questions about the iterative approach that I took? Do you see why I was talking about the hint in the setup for our exercise that if you defer the work it makes things a lot easier?

[00:07:36]
By making that into a function that we'll do the add2 later, we keep everything at the function level and functions and functions and functions, they all just keep working together.
>> Kyle Simpson: All right, let's try a recursive approach to this problem.
>> Kyle Simpson: I'm still gonna be taking in a functions.

[00:08:05]
This time I'm gonna actually pass in an array. That's probably a better way rather than passing them in individually. We probably should be passing them in as actual arrays. So let's do that. Let's just change to passing in a real array rather than passing n individual values. And what I know about this functions array is that it has elements, again, we know we're always going to pass at least two, we don't need to worry about the zero or the one case here.

[00:08:35]
So I could just destructure the argument to the function. So instead of having an fns, I'm just going to do a destructuring pattern here that takes fns of zero, fns of one and everything else. And I'm gonna literally use the exact same strategy as I used in the iterative approach, which is to say, if rest length is greater than zero basically.

[00:09:01]
So if rest dot length is greater than zero, then what we're gonna need to do is call recursively and pass along a new function with fn zero and fn one in it, along with everything else in rest. So we're gonna call addn recursively and the array that we're gonna pass in is an array that includes that function that we just did.

[00:09:26]
The same function here, which I'll just copy and paste. So I don't have to re-type it.
>> Kyle Simpson: And then everything else. So each time we recurse, we're reducing our list length by one. Exactly as we were doing iteratively. Until we get to the base condition. Which I could've rewritten and I'm gonna actually rewrite just for clarity.

[00:09:55]
I could say if rest dot length equals two, then I can return add2 with fn zero, I'm sorry, equals zero, fn zero and fn one. In other words if there's no other functions fn zero and fn one are our only two then just do that. Otherwise, do the recursive return.

[00:10:18]
>> Kyle Simpson: This recursive return makes a new array, which has one fewer element in it. And we keep making that array smaller and smaller and smaller and smaller until we get an array of size two. Which leaves rest with array length of zero, and then we're done. Let's try that implementation of addn and make sure that it still works.

[00:10:56]
>> Kyle Simpson: Uh-oh, I made a mistake. Let's see, where did I make a mistake here?
>> Kyle Simpson: I didn't put the arrays in here. That's right. Forgot, okay, we need to put in the array and that should work. There we go. Okay? So our addn recursive is doing the same work and basically the same strategy as our iterative approach.

[00:11:23]
By the way, do you notice anything about our recursive solution here? Do you notice anything about how our function calls are in proper tail call position? And these function calls are in proper tail call position, we're creating a big, big, big nested hairy mess of functions, but every single one of them, the whole tree of functions are all in tail call position.

[00:11:51]
Which means, if we were to run this in a tail call enabled environment, we would take the benefit of tail call optimization, of proper tail calls. Okay. Let's go back and let's try it one final time. This time we're gonna do it with a list operator. You can probably guess which one.

[00:12:19]
>> Kyle Simpson: We want to move through the list and we want to combine two values into one. And then combine two more values into one and combine two more values into one. What does that sound like to you? What list operation does that sound like? What do we do every time we have a function of a shape that takes two values and it ends up producing-

[00:12:44]
>> Speaker 2: Reduce.
>> Kyle Simpson: That's a reduce, right? So our fundamental strategy here is very similar to the previous one. [LAUGH] Which is, we're going to do a reduce on the fns array. Reduce requires two inputs, right? It requires a reducer and an initial value.
>> Kyle Simpson: So we're gonna write a reducer.

[00:13:08]
>> Kyle Simpson: And then we're gonna need an initial value. So what should that initial value be here? We could pass the identity function in as the initial value. Whatever gets passed into it just gets passed right back out. But there's a trick, as we mentioned earlier, that the JavaScript array reduce, the one that's built into JavaScript arrays, it is a shortcut that if you don't provide an initial value, it uses the first value in the list as the initial value, and it starts the reduction at the second position.

[00:13:41]
So that turns out to be really convenient for us because that's what we want here. We just want functions to start composing themselves, combining themselves together. All right, so what are we gonna call the two parameters to our reducer? Canonically they're usually referred to as acc for accumulator and then v for value.

[00:13:59]
But I always like to give them more descriptive names, so what's a good descriptive name for this thing that we keep building up? At the end, as we go along our reduce? Well, our strategy has been to take two functions and make them into a bigger function. So I'm going to call this a composed function.

[00:14:19]
And I'm going to call each value that comes in the fn. We could have maybe been even cheeky about it and called this big fn. [LAUGH] Because it's a bigger and bigger and bigger function, right? Bigger and deeper and deeper function. We'll leave it at that just because that's fun and it's towards the end of this unit of discussion.

[00:14:38]
Okay, so, our strategy then is, we get these two things and we need to compose them together. We need to reduce them rather. So how do we reduce them? We make a new value, which is a function, and that function calls add2 with our two functions. It's exactly the same function as we did, and it's basically the same strategy here.

[00:15:04]
Now what is the end result of our full reduce? After we've run through the entire list and made functions and functions and functions into this bigger and bigger function. What is the end result of that whole thing?
>> Kyle Simpson: A big function and we don't want a big function, do we?

[00:15:23]
We actually want the computed value. So what do we need to do? Do a final execution of that function. To give us the value. Let's try this final implementation of addn and see how it works.
>> Kyle Simpson: We should still get 35, and there we go, there's 35.