Reading 9: Functional Programming

We have already been using function expressions, starting as far back as Testing, since the mocha framework uses them:

describe("Math.max", function() {
  it("covers a < b", function() {
    assert.strictEqual(Math.max(1, 2), 2);
  });
});

This code has two function expressions – the first one is passed as an argument to describe(), and the second (nested inside it) is passed as an argument to it().

TypeScript also has a more compact arrow syntax that avoids the need for a function keyword:

describe("Math.max", () => {
  it("covers a < b", () => {
    assert.strictEqual(Math.max(1, 2), 2);
  });
});

If the body of the function consists of only a single expression (i.e. like a Python lambda expression), then even the curly braces can be omitted:

it("covers a < b", () => assert.strictEqual(Math.max(1, 2), 2) );

But it turns out that there is a technical difference between arrow functions and function expressions that is important when using methods: a function expression may redefine this, but an arrow function uses the definition of this from its surrounding context. So arrow functions should always be used inside an instance method, rather than function expressions. Understanding This, Bind, Call, and Apply in JavaScript has a good explanation of the issues behind the meaning of this in JavaScript.

interface Dog {
    name(): string;
    breed(): Breed;
    loudnessOfBark(): number;
}

dogs: Array<Dog>

dogs.sort(function(dog1: Dog, dog2: Dog) {
    return dog2.loudnessOfBark() - dog1.loudnessOfBark();
});

dogs.sort(function(dog1: Dog, dog2: Dog) {
    return dog1.loudnessOfBark() > dog2.loudnessOfBark() ? dog1 : dog2;
});

dogs.sort((dog1: Dog, dog2: Dog) => {
  return dog1.loudnessOfBark() - dog2.loudnessOfBark();
});

dogs.sort((dog1: Dog, dog2: Dog) => dog1.loudnessOfBark() - dog2.loudnessOfBark());

function quietestFirst(dog1: Dog, dog2: Dog) {
    return dog1.loudnessOfBark() - dog2.loudnessOfBark();
};

dogs.sort(quietestFirst());

It’s important to understand the difference between an iterator and an iterable.

An iterable type represents a sequence of elements that can be iterated over. In TypeScript, the Iterable<E> interface represents an iterable, and requires the type to have an iterator method which returns a fresh Iterator object for the sequence. Python has a similar notion of iterable, where the required method is called __iter__.

An iterator, on the other hand, does not represent an entire sequence of elements. Its state represents a particular point in an iteration over a sequence (so it actually represents the remainder of the sequence that it is iterating over). But an iterator is a mutable object. Each time next() is called, the iterator advances to the next element, and previous elements are no longer accessible through the iterator. Once the iterator reaches the end, it cannot be reset back to the beginning of the sequence.

As a result, when you are working with sequences – storing them in variables, passing them to functions, returning them from functions – you should be using iterable types, not Iterator itself. Often these iterable types are specific types like Array or Set. But if you are writing a function that doesn’t need any of the particular operations of these types — that only needs to iterate using for...of — then consider using the supertype Iterable instead.

// Uses the strings in `sequence` to compute something
function doSomething(sequence: Iterator<string>): string;

doSomething(myStrings);

To better understand how an iterator works, here’s a simple implementation of an iterator for Array<string>. Because our simple iterator can only handle strings, we’ll also simplify next() to return string|undefined – i.e., either the next value from the array, or undefined if we’ve reached the end. (Note that Iterator<E> can’t do this in general, because undefined might very well be one of the elements in the collection, if it’s part of the E type.)

/**
 * A MyIterator is a mutable object that iterates over
 * the elements of a Array<string>, from first to last.
 * This is just an example to show how an iterator works.
 * In practice, you should use the Array's own iterator
 * object, returned by its iterator() method.
 */
class MyIterator {

    private readonly array: Array<string>;
    private index: number;
    // AF(array, index) = the sequence of elements array[index]...array[array.length-1]
    // RI: index is a nonnegative integer

    /**
     * Make an iterator.
     * @param array array to iterate over
     */
    public constructor(array: Array<string>) {
        this.array = array;
        this.index = 0;
    }

    /**
     * Get the next element of the array.
     * Modifies: this iterator to advance it to the element 
     *           following the returned element.
     * @returns the next element in the array, 
     *          or undefined if there are no more elements
     */
    public next(): string|undefined {
        if (this.index >= this.array.length) {
            return undefined;
        } else {
            const value = this.array[this.index];
            ++this.index;
            return value;
        }
    }
}

Here’s a snapshot diagram showing a typical state for a MyIterator object in action:

Note that we draw the arrow from array with a double line, to indicate that it’s readonly. That means the arrow can’t change once it’s drawn. But the array object it points to is mutable — elements can be changed within it — and declaring array as readonly has no effect on that.

Let’s try using our iterator for a simple job. Suppose we have an array of filenames, like ["a.txt", "b.txt", "c.pdf"]. We want a function removeFilesWithExtension that will delete filenames with a particular extension, like .txt, from the array, leaving the other filenames behind. For this example, the function should remove the elements "a.txt" and "b.txt", leaving behind a one-element array ["c.pdf"].

Following test-first programming, we write a spec, choose and implement test cases to cover some partitions, and finally implement the function, using our MyIterator class:

/**
 * Remove filenames with a given extension.
 * Modifies the filenames array by removing filenames that end with the extension.
 * 
 * @param filenames array of filenames
 * @param extension must start with ".", e.g. ".txt"
 */
function removeFilesWithExtension(filenames: Array<string>, extension: string): void {
    let iter: MyIterator = new MyIterator(filenames);
    for (let filename = iter.next(); filename !== undefined; filename = iter.next()) {
        if (filename.endsWith(extension)) {
            // remove the filename from the array
            filenames.splice(filenames.indexOf(filename), 1);
        }
    }
}

Now we run our test cases, and they work! … almost. This test case fails:

// removeFilesWithExtension(["a.txt", "b.txt", "c.pdf"], ".txt")
//   expected ["c.pdf"], actual ["b.txt","c.pdf"]

We got the wrong answer: removeFilesWithExtension left a matching filename behind in the array! Why? Trace through what happens. It will help to use a snapshot diagram showing the MyIterator object and the Array object and update it while you work through the code.

Note that this isn’t just a bug in our MyIterator. The built-in iterator in Array suffers from the same problem, and so does the for loop that’s syntactic sugar for it. So do lists and for loops in Python. Mutating a list that is currently being iterated over is simply not safe in general.

This is a fundamental issue with mutable types. Multiple references to the same mutable object (aliasing) may mean that multiple places in your program — possibly widely separated — are relying on that object to remain consistent.

To put it in terms of specifications, contracts can’t be enforced in just one place anymore, e.g. between the client of a class and the implementer of a class. Contracts involving mutable objects now depend on the good behavior of everyone who has a reference to the mutable object.

As a symptom of this non-local contract phenomenon, consider iterators. Try to find where it documents the crucial requirement on the client that we’ve just discovered — that you shouldn’t mutate an array while you’re iterating over it. Who takes responsibility for it? The iterator specification? Array? Can you find it?

The need to reason about global properties like this makes it much harder to understand, and be confident in the correctness of, programs with mutable data structures. We still often do it — for performance and convenience — but we pay a big price in bug safety for doing so.

For these reasons, functional programming largely avoids mutation. The map/filter/reduce pattern discussed below produces new sequences of elements, rather than mutating existing ones, and the first-class functions that are passed to map/filter/reduce are generally pure functions, which return an output rather than mutating any of their inputs.

Map applies a unary function to each element in the sequence and returns a new sequence containing the results, in the same order:

map : Array<‍E> × (E → F) → Array<‍F>

For example:

const array: Array<number> = [1, 4, 9, 16];
const result = array.map(Math.sqrt);

This code starts with an array containing the numbers 1, 4, 9, 16 and applies the square root function to each element to produce the values 1.0, 2.0, 3.0, 4.0.

In the call array.map(Math.sqrt):

• map has type Array<‍number> × (number → number) → Array<‍number>
• the input array has type Array<‍number>
• the mapping function Math.sqrt has type number → number
• the return value has type Array<‍number>

We can write the same expression more compactly as:

[1, 4, 9, 16].map(Math.sqrt);

which is the syntax that future examples will use.

Another example of a map:

["A", "b", "C"].map(s => s.toLocaleLowerCase())

which produces an array containing "a", "b", "c". (Notice that when we call a function like Math.sqrt, we can refer to it directly. Calling a method like toLocaleLowerCase requires a lambda expression to wrap the method call syntax.)

Map is useful even if you don’t care about the return value of the function. When you have a sequence of mutable objects, for example, you may want to map a mutator operation over them. Because mutator operations typically return void, however, you can use forEach instead of map. forEach applies the function to each element of the sequence, but does not collect their return values into a new sequence:

itemsToRemove.forEach(item => mySet.delete(item));

(A lambda is needed here, too. The expression mySet.delete by itself would refer to the delete function without binding mySet to this, which will not work.)

The map and forEach operations capture a common pattern for operating over sequences: doing the same thing to each element of the sequence.

["1", "2", "3"].map((s: string) => s.length);

[1, 2, 3].map((s: string) => s.length);

Our next important sequence operation is filter, which tests each element of an Array<E> with a unary function from E to boolean.

Elements that satisfy the predicate are kept; those that don’t are removed. A new sequence is returned; filter doesn’t modify its input sequence.

filter : Array<‍E> × (E → boolean) → Array<‍E>

Examples:

[1, 2, 3, 4]
   .filter(x => x%2 === 1);
// returns [1, 3]

["x", "y", "2", "3", "a"]
   .filter(s => "abcdefghijklmnopqrstuvwxyz".includes(s)));
// returns ["x", "y", "a"]

const isNonempty = (s: string) => s.length > 0;
["abc", "", "d"]
   .filter(isNonempty);
// returns ["abc", "d"]

const s1 = "Abel";
const s2 = "Baker";
const s3 = "Charlie";

[s1, s2, s3]
    .filter(s => s.startsWith("A"));

const s1 = "Abel";
const s2 = "Baker";
const s3 = "Charlie";

[s1, s2, s3]
    .filter(s => s.startsWith("Z"));

const isDigit = (s: string) => s.length === 1 && "0123456789".includes(s);
["a", "1", "b", "2"]
    .filter(isDigit);

const isDigit = (s: string) => s.length === 1 && "0123456789".includes(s);
["a", "1", "b", "2"]
    .filter( ! isDigit);

Our final operator, reduce, combines the elements of the sequence together, using a binary function. In addition to the function and the array, it also takes an initial value that initializes the reduction, and that ends up being the return value if the array is empty:

reduce : Array<‍E> × (E × E → E) × E → E

arr.reduce(f, init) combines the elements of the array together. Here is one way that it might compute the result:

result₀ = init
result₁ = f(result₀, arr[0])
result₂ = f(result₁, arr[1])
...
result_n = f(result_n-1, arr[n-1])

result_n is the final result for an n-element sequence.

Adding numbers is probably the most straightforward example:

[1,2,3].reduce( (x,y) => x+y,  0)

…which computes as shown below:

reduce( [1, 2, 3], + , 0 ) = ((0 + 1) + 2) + 3 = 6

There are three design choices in the reduce operation. First is whether to require an initial value. In TypeScript, the initial value can be omitted, in which case reduce uses the first element of the sequence as the initial value of the reduction. But if the sequence is empty, then reduce has no value to return, and reduce throws a TypeError. It’s important to keep this in mind when using reducers like max, which have no well-defined initial value:

[5, 8, 3, 1].reduce((x,y) => Math.max(x,y))
// computes max(max(max(5,8),3),1) and returns 8

[].reduce((x,y) => Math.max(x,y))
// throws TypeError!

The second design choice is the return type of the reduce operation. It doesn’t necessarily have to match the element type of the original sequence. For example, we can use reduce to concatenate an array of numbers (type E) into a string (type F). This changes the reduce operation in two ways:

• the initial value now has type F
• the binary function is now an accumulator, of type F × E → F, that takes the current result (of type F) and a new element from the sequence (of type E), and produces an accumulated result of type F.

So a more general form of the reduce operation now looks like this:

reduce : Array<‍E> × (F × E → F) × F → F

In the special case where F is the same type as E, this type signature is the same as above.

Here’s a simple example that concatenates a sequence of numbers into a string:

[1,2,3].reduce( (s: string, n: number) => s + n, "" );
// returns "123"

We’ve included parameter type declarations in the lambda expression above in order to clarify the difference between the two parameters of the accumulator function. If F is the same type as E, it’s ok to omit these type declarations in the lambda expression.

The third design choice is the order in which the elements are accumulated. TypeScript’s reduce operation combines the sequence starting from the left (the first element):

result₀ = init
result₁ = f(result₀, arr[0])
result₂ = f(result₁, arr[1])
...
result_n = f(result_n-1, arr[n-1])

Another TypeScript operation, reduceRight, goes in the other direction:

result₀ = init
result₁ = f(result₀, arr[n-1])
result₂ = f(result₁, arr[n-2])
...
result_n = f(result_n-1, arr[0])

to produce result_n as the final result.

Here’s a diagram that contrasts the two ways to reduce, from the left or from the right. If the operator is non-commutative (like string concatenation, shown here), then each direction might produce a different answer:

	reduce( [1, 2, 3], + , "" ) = (("" + 1) + 2) + 3 = "123"		reduceRight( [1, 2, 3], + , "" ) = (("" + 3) + 2) + 1 = "321"

[e1, e2, e3].reduce( (x: boolean, y: string) => x && (y === 'true'),
                     true );

[1, 2, 3].reduce((a, b) => a * b, 0)

["oscar", "papa", "tango"]
    .reduce((a,b) => a.length > b.length ? a : b)

const array: Array<number> = [...];

const result = array.reduce((x, y) => Math.min(x, y));

let result;
try {
    result = array.reduce((x, y) => Math.min(x, y));
} catch (e) {
    result = 0;
}

const result = array.reduce((x, y) => Math.min(x, y), Number.POSITIVE_INFINITY);

Python makes filter and map easily accessible with list comprehensions:

doubleOdds = [ x*2 for x in arr if x % 2 == 1 ]

… which is like the TypeScript:

const doubleOdds = arr.filter(x => x % 2 === 1).map(x => x*2)

The result of a list comprehension is a list by virtue of the […] brackets. In Python, comprehensions work over any iterable source, and can also be used to build sets and dictionaries. For example:

arr = [ 4, 7, 5, 6, 7, 4 ]  # given a list
{ x for x in arr if x > 5 } # ... create a set of values greater than 5:
# => a set { 6, 7 }

input = { 'apple': 'red', 'banana': 'yellow' } # given a dictionary
{ value: key for key, value in input.items() } # ... create a dictionary with
                                               #     key-value pairs inverted
# => a dictionary { 'red': 'apple', 'yellow': 'banana' }

We can do the same things in TypeScript:

const arr = [ 4, 7, 5, 6, 7, 4 ];
new Set(arr.filter(x => x > 5));
// => a Set { 6, 7 }

const input = new Map([ ['apple','red'], ['banana','yellow'] ]);
new Map([ ...input.entries() ].map(entry => entry.reverse()));
// => a Map { 'red' => 'apple', 'yellow' => 'banana' }

Breaking down the construction of that inverted map:

• Notice that the Map constructor takes a series of two-element arrays: the first element of each is a key, the second is its value.
• Map.entries returns an iterable that iterates over two-element key-value arrays.
• Because JavaScript/TypeScript doesn’t provide map and filter on iterables, only on arrays, we use the spread operator ... to stuff those key-value arrays into an array.
• Now we can call map on that array, and for each [key,value] entry, we reverse it to [value,key] and create the new map.

Just as idiomatic Python code will avoid for loops in favor of comprehensions for filtering and mapping data structures, idiomatic TypeScript will take advantage of map and filter in concert with tools like Map.entries and array methods like Array.entries, .some, and .every to avoid loops.

Any time you write a loop, reach for those tools first, instead of an index counter.

Let’s look at a typical database query example. Suppose we have a database about digital cameras, in which each object is of type Camera with various properties (brand, pixels, cost, etc.). The whole database is in an array called cameras. Then we can describe queries on this database using map/filter/reduce:

// What's the highest resolution Nikon sells? 
cameras.filter(camera => camera.brand === "Nikon")
       .map(camera => camera.pixels)
       .reduce((x,y) => Math.max(x,y));

Relational databases use the map/filter/reduce paradigm (where it’s called project/select/aggregate). SQL (Structured Query Language) is the de facto standard language for querying relational databases. A typical SQL query looks like this:

select max(pixels) from cameras where brand = "Nikon"

cameras is a sequence (of table rows, where each row has the data for one camera)

where brand = "Nikon" is a filter

pixels is a map (extracting just the pixels field from the row)

max is a reduce