filter and the Predicate Interface

Let's talk through what this function is doing.

filter takes in two parameters:

1. A Node of some generic type.

2. A test function whose type is Predicate.

let filter = <T> (list: Node<T>, test: Predicate<T>): Node<T> => {
    if (list === null) {
        return null;    
    } else if (test(first(list))) {
        return cons(first(list), filter(rest(list), test));    
    } else {
        return filter(rest(list), test);    
    }
};

Note that since filter is a function that accepts another function as a parameter, filter is considered a higher-order function. The type of a function is the functional interface that it belongs to.

In the case of filter, the "test" parameter must be a function that belongs to the Predicate interface, defined as follows:

interface Predicate<T> {
    (item: T): boolean;
}

In other words, the function passed to filter must return a boolean when given a parameter of any type.

This is pretty mind blowing stuff! Don't be discouraged if it's not 100% clicking yet. Let's try to break down what is happening behind the scenes when this higher-order filter function is.

As a general rule of thumb, when you are filtering a data set, you are trying to obtain a subset of that data that meets a certain criteria. For example, if you start out with a list of all the words in the dictionary, you could break this list down into however many different sublists you wanted to. You could filter by part of speech, word length, first letter or number of vowels. However, no matter how you filter this list, your result will be a list of words - the same type you started with!

The logic behind filtering a list of data does not depend on the type of data - the algorithm will be the same. That is why we can make it generic! The only piece of logic that is changing is the criteria we want each item in our new filtered list to meet. This is where our Predicate function comes in!

Our test function is called with each element of our list. If the result of each individual call to this Predicate function is true, that item is added to the new list we are building. If false is returned, we ignore that item and go on to process the rest of the list.

Now that we have abstracted the logic of the filter algorithm, we can reuse the filter function over and over again. Just make sure you import it at the top of your program:

import { filter } from "./list-utils";
/* This import statement will only work if you have the list-utils.ts file 
in the same folder you are working in! You can find this in your lecture 13
or lecture 14 folders. */

Let's take a look at a few examples!

Examples:

1. Filtering with strings.

// predicate
let bestLetter = (word: string): boolean => {
    return (word.substr(0,1) === "K");
};

let main = async () => {
    let original = listify("Kaki", "Morgan", "Kris", "Madison", "Kiet");
    let filtered = filter(original, bestLetter);
    print(filtered);
};

The resulting output will be Kaki --> Kris --> Kiet --> null. For each element in the original List, the Predicate function bestLetter is called, which tests if the string begins with a "K." A new filtered list is constructed containing only the strings that result in a true being returned by the bestLetter function.

2. Filtering with numbers.

// predicate
let even = (x: number): boolean => {
    return (x % 2 === 0);
};

let main = async () => {
    let original = listify(1, 2, 3, 5, 10);
    let filtered = filter(original, even);
    print(filtered);
};

The resulting output will be 2 --> 10 --> null.

The Predicate function even returns true only if an even number is passed to it, if even returns true, we add the number to our list. We check this using the modulus operator "%". In English the expression x % 2 === 0 can be read as "check if the remainder of x divided by 2 is equal to zero."

3. Filtering with objects.

class Cat {
    hasClaws: boolean = true;
    furColor: string = "black";
    numLivesLeft: number = 9;
}

let main = async () => {
    let cat1 = new Cat();
    cat1.hasClaws = false;
    cat1.numLivesLeft = cat1.numLivesLeft - 3;
    let cat2= new Cat();
    cat2.numLivesLeft = cat2.numLivesLeft - 1;
    let cat3= new Cat();
    cat3.furColor = "rainbow";
    cat3.hasClaws = false;
    let original = listify(cat1, cat2, cat3);
    let filtered = filter(original, declawed);
    print(filtered);
};

// predicate
let declawed = (kitty: Cat): boolean => {
    return !kitty.hasClaws;
};

The resulting output will be a list of only the Cats that have been "declawed"... AKA the declawed function returns true when tested on those particular Cat objects.

hasClaws	furColor	numLivesLeft
false	black	6
false	rainbow	9
null

Filtering with Arrays

What if we want to filter arrays instead of lists?? Lucky for us, arrays all have built-in filter, map & reduce methods. Methods are just functions defined specifically for a certain class. For a review of these and other important concepts, check out the Object-Oriented Programming section!

Every array of any generic type T[] has a filter method! This filter method differs slightly from the filter function we may be more used to working with, but the fundamental ideas behind them are exactly the same.

The filter method takes in a single parameter: a Predicate function. This Predicate function follows the exact same rules and requirements as a Predicate used with the filter function. The filter method gives us back a new array that is a subset of the original, just like the list function does.

Let's take look at the same examples as above, just using arrays instead.

1. Filtering string arrays

let bestLetter = (word: string): boolean => {    
    return (word.substr(0,1) === "K");
};

let main = async () => {    
    let original = ["Kaki", "Morgan", "Kris", "Madison", "Kiet"];    
    let filtered = original.filter(bestLetter);   
    print(filtered);
};

Resulting output is Kaki, Kris, Kiet.

2. Filtering with numbers.

let even = (x: number): boolean => {    
    return (x % 2 === 0);
};

let main = async () => {    
    let original = [1, 2, 3, 5, 10];    
    let filtered = original.filter(even);    
    print(filtered);
};

The resulting output is 2, 10.

3. Filtering with objects.

class Cat {    
    hasClaws: boolean = true;    
    furColor: string = "black";    
    numLivesLeft: number = 9;
}

let main = async () => {    
    let cat1 = new Cat();    
    cat1.hasClaws = false;    
    cat1.numLivesLeft = cat1.numLivesLeft - 3;    
    let cat2 = new Cat();    
    cat2.numLivesLeft = cat2.numLivesLeft - 1;    
    let cat3 = new Cat();    
    cat3.furColor = "rainbow";    
    cat3.hasClaws = false;    
    let original = [cat1, cat2, cat3];    
    let filtered = original.filter(declawed);    
    print(filtered);
};

let declawed = (kitty: Cat): boolean => {    
    return !kitty.hasClaws;
};

The resulting output will be [object Object],[object Object] when we don't have a toString() method defined for the Cat Class. An example one of one you could define might be:

toString = (): string => {
    return this.furColor + " cat with " + this.numLivesLeft 
     + " lives left";
}

The resulting output would be black cat with 6 lives left,rainbow cat with 9 lives left.

Comp 110 filter and the Predicate Interface

filter and the Predicate Interface

Filtering with Arrays