Comp 110 filter and the Predicate interface

filter and the Predicate Interface

This page is going to talk about how we can make use of the generic filter function implemented below. Check out the pages on the filter-map-reduce pipeline and generic functions for a review of those concepts!

let filter = <T> (list: List<T>, test: Predicate<T>): List<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);

Let's talk through what this function is doing.

filter takes in two parameters:

     1. A List of some generic type. 

     2. A test function whose type is Predicate.

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 is belongs to. For a crash course on functional interfaces and function types, click here.

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!


1. Filtering with strings.

let bestLetter = (word: string): boolean => {
    return (word.substr(0,1) === "K");
let main = async () => {
    let original: List<string> = listify("Kaki", "Morgan", "Kris", "Madison", "Kiet");
    let filtered: List<string> = filter(original, bestLetter);

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.

let even = (x: number): boolean => {
    return (x % 2 === 0);
let main = async () => {
    let original: List<number> = listify(1, 2, 3, 5, 10);
    let filtered: List<number> = filter(original, even);

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: Cat = new Cat();
    cat1.hasClaws = false;
    cat1.numLivesLeft = cat1.numLivesLeft - 3;
    let cat2: Cat = new Cat();
    cat2.numLivesLeft = cat2.numLivesLeft - 1;
    let cat3: Cat = new Cat();
    cat3.furColor = "rainbow";
    cat3.hasClaws = false;
    let original: List<Cat> = listify(cat1, cat2, cat3);
    let filtered: List<Cat> = filter(original, declawed);
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.