Implement Filter Function Exercise

[00:00:00]
>> Anjana Vakil: Okay, so what we are going to do next is give ourselves the headache [LAUGH] of, instead of using the built-in array methods, how would we do this in functional land? How would we make functions like this that are higher order, that take in functions and then do the thing we want them to do?

[00:00:25]
So, in our next exercise, we are going through each of these functions, filter, math and reduce one by one, and we are going to reimplement them, using functionals style. Okay, so your task here, we're gonna start with filter. In funpro.js, [LAUGH] we have a stub of the filter function and in funpro.test.js, we have some pretty basic test cases that just see if this is doing what we expect it to do.

[00:01:02]
Namely, it's taking an array, and it's filtering some things out, and it's returning us a new array, okay? So now, what we're gonna do is, instead of just using [LAUGH] array.filter predicate function, which would make this a pretty fast course. And also wouldn't help us learn functional programming, we're going to write this higher level function using our most versatile hammer of recursion to do something over and over and over again.

[00:01:36]
Because we don't have iteration, remember, we can't do for let element of array, because I said so, no. But because we want to avoid state, we want to avoid surprises, we want to avoid, I was just tired that day, and I didn't realize that I was incrementing I instead of decrementing, whatever.

[00:01:56]
If we have no state, then we don't have to remember values. So, in addition to recursion, you have a few other tools to help you out here. Which are essentially kind of functional style wrappers around the built-in array methods that we would be using in JavaScript if I weren't imposing artificial constraints on you.

[00:02:15]
So [LAUGH] instead of calling array.length for example, which is a little bit more of a arguably kind of object-oriented API, we're gonna use a functional API of calling the function length on the array. And similarly for concat. And then in order to get things out of the array, these are some functions you might encounter if you look into other functional languages.

[00:02:43]
For example, Lisps, scheme, or closure, head of an array is the first thing. So it's equivalent to in JavaScript API accessing the zero with element of the array, and tail is everything else. So we talk about the head and tail of arrays in functional programming often. And this sort of comes out of so Lisps programming languages are, yeah, languages that are designed to operate on Lisps.

[00:03:17]
And is one of the kind of core references of a functional type of language as a Lisp. However, what we're doing here is we're just kind of masking how JavaScript actually is with these functional APIs. Just so you can get a little more into the habit of the type of utilities you would have if you were using either a purely functional language.

[00:03:36]
Or some kind of toolkit library in JavaScript, let's say, which we'll talk about at the end of the course, I have some links for you. All right, so you can use these in your implementation. And once you have got the implementation going, these tests should pass. So let us take a moment and harness our inner recursive programmer and filter some our A's.

[00:04:08]
>> Anjana Vakil: Let's implement this filter function together. All right, I said it's gonna be a recursive function, so that means it's gonna have two cases at least, a base case and a recursive case. So, why don't we start, as is usually a good plan, with the base case, cuz those are often easier to think about [LAUGH].

[00:04:26]
All right, can anybody share what their base case was in this implementation? When do we know that we're already done?
>> Student: If length of array zero.
>> Anjana Vakil: If there's nothing in the array, great, we've already filtered everything in the array. So we can say, if the length of the array an array is 0, then, what do we wanna return?

[00:04:56]
>> Student: Empty array?
>> Anjana Vakil: It has to be an array because we said by definition, filter is supposed to take in an array and return an array. So in this case, we're just going to return the empty array. Boom, done, fabulous. We could also probably return array, because it's also empty, but what have you.

[00:05:12]
Okay, great, now, we need a recursive case. So, if the array has one thing in it, what do I do?
>> Anjana Vakil: Just like if you were explaining it to me as a person, if I'm trying to filter an array with a given predicate function, and it has one thing in it,

[00:05:35]
>> Student: Test that one thing with the predicate function.
>> Anjana Vakil: Exactly.
>> Student: And then, return it if it passes.
>> Anjana Vakil: Beautiful, so we're gonna call the predicate function on the thing in the array. And then we're going to see what its value is and decide whether or not to put it into the output.

[00:05:50]
Great, so what we can do is just capture the first thing in the array, and we have that head function that's gonna help us do that. So the head of the array is gonna be the first thing in that array. And then what we wanna do is, evaluate what this predicate function actually is for this input of the first item.

[00:06:12]
So, I could call this like filteredFirst, oop. See, no caps needed, [LAUGH] and that is gonna be, anybody help me out with the implementation here?
>> Student: The predicate function?
>> Anjana Vakil: Yep, okay, so I'm gonna call the predicate function on first, we said, but that would be, if I left it here, if I stop here, filteredFirst will be a Boolean, right?

[00:06:39]
>> Student: Because we said, by definition predictive function are supposed to return a Boolean. So that's not what I want, instead, I want either,
>> Anjana Vakil: This item or not this item. Now, there's a few different ways we could write that on JavaScript, but the most declarative way We could do a simple, if else, ternary operator.

[00:07:02]
The ternary if is a nice, declarative way of doing these. So I could say, is the predicate function of first true? And if so, what shall I return?
>> Student: First. First as an array.
>> Anjana Vakil: First in an array, exactly. So I don't wanna just return the object first.

[00:07:21]
I wanna wrap it in an array, cuz that's how this works. And if not, then I will return nothing in the array. Beautiful, okay, now we've solved the two most important cases of array has nothing in it. Array has one thing in it. But that's not enough to make our tests happy, so we need to now draw the rest of the owl.

[00:07:46]
[LAUGH] How will we do that?
>> Student: Call filter,
>> Anjana Vakil: Recursion, call filter, exactly. Okay, so now at some point, I'm gonna call filter and I'm gonna pass in the same predicate function cuz we wanna keep using the same function on all of our elements. But instead of passing in the original array, what should I pass in?

[00:08:07]
>> Student: Everything but the first element.
>> Anjana Vakil: So we already checked the first element, what's left? Everything else, and in functional land, we said we call that often tail. So this tail function is like everything else in the array. So we saw that before where, if we have an array of zero, one, two, three, four, head will be zero, tail will be one, two, three, four.

[00:08:28]
Okay, so this is gonna be our recursive call. What are we, done? [LAUGH] No, obviously, because I'm not returning anything from this function yet, so clearly, we [INAUDIBLE]. But I also I don't wanna just simply return that, cuz that wouldn't have my first element. So how do I smush them together?

[00:08:53]
[LAUGH]?
>> Student: Concat them together.
>> Anjana Vakil: So I could concat multiple arrays together. I have that concat helper in here, concat helper. And so I want to concat this filtered rest of the array. Well, I want that to be at the end. And what I want to be first is what value would I wanna put here?

[00:09:17]
I'm gonna concat these two things, smush them into one array.
>> Student: FilteredFirst.
>> Anjana Vakil: FilteredFirst is already an array with the filteredFirst element or not. And so if it's empty, cool, no big deal. If it's there, great, it gets concatenated to the array. And hopefully, we will see some green, yay.

[00:09:39]
Okay, this is a successful, excellent job, everybody. Implementation of the filter, what we're used to calling a method in JavaScript, which now it's all functions, functions all the way down. We'll talk about that later, it is not the only solution. Did anybody use something else to solve this, particularly maybe the concat part?

[00:10:03]
Trick question cuz I asked you to use those helpers. So thank you for listening to me. But another thing we can do is, for example, use the spread operator into a new array. This is a JavaScript syntax thingy. And again, if you haven't worked with spread operators, I have a course about JavaScript language features that is not today's material.

[00:10:24]
But I'll leave that as an exercise for afterwards, for you to see if you can also without using these built in little helpers here, if there's another way you could finish that last line.