reduce and the Reducer Interface

This page is going to explain how we can make use of the generic reduce function implemented below. Head over to the filter-map-reduce pipeline and generic functions pages for a review of those concepts!

export let reduce = <T, U> (list: Node<T>, f: Reducer<T, U>, memo: U): U => {    
    if (list === null) {        
        return memo;    
    } else {        
        return reduce(rest(list), f, f(memo, first(list)));    
    }
};

Let's break this down!

reduce takes in 3 parameters:

1. A Node of some generic type

2. A function of type Reducer

3. A starting point / "memo" value

Like we saw with filter and map, reduce is also a higher-order function - it takes in a Reducer function as a parameter. A function belonging to the Reducer functional interface is one that takes in some starting point ("memo") and an item. These parameters can be of the same or different types. The function then processes the data element in some way, producing a return value that matches the type of memo.

The value that is returned as a result of calling f, the Reducer function, with the first item in our list then serves as the memo/starting point for the next call of f. This second call of f will be with the second item in the list. This continues until the list runs out of elements and we are left with a single value!

The Reducer interface is defined as follows:

export interface Reducer<T, U> {    
    (memo: U, item: T): U;
}

The most important thing this functional interface tells us is that regardless of the types of "memo" and "item", the return type of the Reducer function needs to match memo. I.e. The final value we get when we are done reducing needs to match the type of our starting point.

Examples

1. Reducing with strings

let getExcited = (memo: string, word: string): string => {    
    return memo + word + "! ";
};

let main = async () => {    
    let original: Node<string> = listify("Let's", "Go", "Heels");    
    let final: string = reduce(original, getExcited, "");    
    print(final);
};

The resulting output will be Let's! Go! Heels!

Let's analyze what is happening behind the scenes.

1. Our Reducer function, getExcited, adds the first word in the List onto memo followed by an exclamation point. Note that memo starts out as the empty string. This first call to getExcited returns "Let's! " which is the new memo value.

2. The second call to getExcited gets passed a memo value of "Let's! " and the word "Go"... the result is "Lets! Go!"

3. The memo parameter in the third and final call to getExcited is the string "Lets! Go!" and returns "Lets! Go! Heels! ".

Each time that our Reducer function is executed, the memo value is different, but all we have to worry about is providing the initial memo value in our call of the reduce function. The rest is taken care of for us!

2. Reducing with numbers

let sumOfSquares = (memo: number, x: number): number => {    
    return memo + (x * x);
};

let main = async () => {    
    let a: Node<number> = listify(1, 2, 3);    
    let b: Node<number> = listify(2, 3, 6, 9);    
    print(reduce(a, sumOfSquares, 0));    
    print(reduce(b, sumOfSquares, 0));
};

The resulting output will be 14 and 130.

3. Reducing with objects

class Store {    
    name: string = "Random Store";    
    cash: number = 1000;
}

let consolidate = (memo: Store, x: Store): Store => {    
    memo.cash  = memo.cash + x.cash;    
    return memo;
};

let main = async () => {    
    let store1: Store = new Store();    
    store1.cash = 3500;    
    let store2: Store = new Store();        
    let store3: Store = new Store();    
    store3.cash = 500;    
    let storeList: Node<Store> = listify(store1, store2, store3);    
    print(reduce(storeList, consolidate, store1);
};

The result that is printed after reducing the List of stores by means of the consolidate Reducer function is:

name	Random Store
cash	8500

What is happening here? Imagine you are the owner of store1 and you just recently bought out store2 and store3. You want to consolidate all three stores into one new store. To do this, we make use of a Reducer function to produce a new Store who's cash property is equal to the total of the individual stores' cash.

Comp 110 reduce and the Reducer Interface

reduce and the Reducer Interface