Comp 110 Filter-Map-Reduce Pipeline

Filter-Map-Reduce Pipeline

The filter-map-reduce pipeline is a pattern for analyzing and processing data that you will see again and again in this class. The data we will be working with will be stored in Lists or arrays that we apply functions and algorithms to in order to collect some sort of meaningful information. Note that filtering, mapping and reducing can all be done independently of each other, they just happen to work nicely together, too.

Let's take it step by step!

Filtering

Filtering is often the first step in our data processing pipeline. A function that filters takes a collection of data objects and returns a subset of those data objects based on some criteria outlined within the function. 

For example, you could write a function that given a list of birthdays, returns to you a list of birthdays with odd-numbered dates. When you filter a data set, the type of the data you pass in as a parameter must match the type of data you get back. This is helpful because we can use multiple filters one after another on the same data. Let's take a look at some code examples.

This first function filters a List of numbers and returns back the subset of that List that is negative. For a review of building Lists recursively, click here.

let filterByNegative = (list: List<number>): List<number> => {
    if (list === null) {
        return null;
    } else if (first(list) < 0) {
        return cons(first(list), filterByNegative(rest(list)));
    } else {
        return filterByNegative(rest(list));
    }
};
let main = aync () => {
    let numbers: List<number> = cons(-3, cons(3, cons(0, cons(-1, null))));
    print(filterByNegative(numbers));
};

The resulting output would be -3 --> -1 --> null. Since this is a filtering function, the type of the List parameter matches the type of List being returned. 

Filter functions can take in more than one parameter to help with the filtering. Here is a function that filters a List of people based on their horoscope sign.

let filterBySign = (people: List<Person>, sign: string): List<Person> => {
    if (people === null) {
        return null;
    } else if (first(people).zodiacSign ==== sign) {
        return cons(first(people), filterBySign(rest(people), sign));
    } else {
        return filterBySign(rest(people), sign);
    }
};
class Person {
    age: number = 18;
    name: string = "Jeffrey";
    zodiacSign: string = "Aquarius";
};
let main = aync () => {
    let p1: Person = new Person();
    p1.zodiacSign = "Gemini";
    let p2: Person = new Person();
    let p3: Person = new Person(); 
    let people: List<Person> = cons(p1, cons(p2, cons(p3, null)));
    print(filterBySign(people, "Aquarius"));
};

The resulting output will be a List of Person objects:

agenamezodiacSign
18JeffreyAquarius
18JeffreyAquarius
null

Our p1 Person object was not included because we changed it's zodiacSign property to be different than the default value of "Aquarius". If we had filtered by a different criteria, for example using the "Gemini" string, only p1 would appear in our new List. Be sure to check out our pages on Object Oriented Programming if any of this is fuzzy to you!

Mapping

Mapping functions take a data set of one form, and convert it into data of another form. We will often use mapping to construct a List of a completely different type than the one passed in as a parameter. This is often useful when dealing with objects in order to just work with a certain property. 

let mapToSign = (people: List<Person>): List<string> => {
    if (people === null) {
        return null;
    } else {
        return cons(first(people).zodiacSign, mapToSign(rest(people)));
    } 
};
class Person {
    age: number = 18;
    name: string = "Jeffrey";
    zodiacSign: string = "Aquarius";
};
let main = aync () => {
    let p1: Person = new Person();
    p1.zodiacSign = "Gemini";
    let p2: Person = new Person();
    let p3: Person = new Person();     
    let people: List<Person> = cons(p1, cons(p2, cons(p3, null)));
    print(mapToSign(people));
};

The resulting output will be Gemini --> Aquarius --> Aquarius --> null. Notice that the return type of this function is a List of strings! This is because the zodiacSign property of the Person class is a string. We are converting our List of Person objects into a List of strings.

In many mapping functions this means that the type of List or array return will be different than the one passed in, but it doesn't always have to be. For example, a function that takes in a List of words and returns back a List consisting only of the first letters of those words is still a mapping function! It is transforming our data set so that we can hone in on certain properties or characteristics of our data elements.

let firstLetter = (words: List<string>): List<string> => {
    if (words === null) {
        return null;
    } else {
        let letter: string = first(words).substr(0, 1);
        return cons(letter, firstLetter(rest(words)));
    }
};
let main = aync () => {
    let list: List<string> = cons("Apple", cons("Banana", cons("Carrot", null)));
    print(firstLetter(list));
};

The resulting output will be A --> B --> C --> null.

Reducing

Reducing takes a data set and simplifies it in some way. This often means taking in a data set and reducing it to a single value, but a reducer function can also result in a collection of values. You can think of filtering as a special kind of reducing. However, the types of the data taken in by a reduce function and the type of data returned by the function must match.

Here is an example of a reducer function that takes a List of strings and simplifies them all into a single string.

let concatenator = (words: List<string>): string => {
    if (words === null) {
        return "";
    } else {
        return first(words) + concatenator(rest(words));
    }
};
let main = aync () => {
    let list: List<string> = cons("Apple", cons("Banana", cons("Carrot", null)));
    print(concatenator(list));
};

The resulting output is "AppleBananaCarrot".