Chapter 11. Higher kinded types and beyond

This chapter covers

• Applying map() to various other types
• Encapsulating error propagation
• Understanding monads and their applications
• Finding resources for further study

Throughout the book, we’ve looked at various versions of a very common algorithm, map(), and in chapter 10 we saw how iterators provide an abstraction that allows us to reuse it across various data structures. In this chapter, we’ll see how we can extend this algorithm beyond iterators and provide an even more general version. This powerful algorithm allows us to mix and match generic types and functions, and can help by providing a uniform way to handle errors.

After we go over a few examples, we’ll provide a definition for this broadly applicable family of functions, known as functors. We’ll also explain what higher kinded types are and how they help us define such generic functions. We’ll look at the limitations we run into with languages that lack support for higher kinded types.

Next, we’ll look at monads. The term shows up in multiple places, and although it might sound intimidating, the concept is straightforward. We’ll explain what a monad is and go over multiple applications, from better error propagation to asynchronous code and sequence flattening.

We will wrap up with a section that discusses some of the topics we learned about in this book and a couple of other kinds of types we did not cover: dependent types and linear types. We won’t go into details here; rather, we’ll provide a quick summary and list some resources in case you want to learn more. We recommend several books to learn more about each of these topics, as well as programming languages that provide support for some of these features.

11.1. An even more general map

In chapter 10, we updated our map() implementation from chapter 5, which worked only on arrays, to a generic implementation that worked on iterators, shown in listing 11.1. We talked about how iterators abstract data structure traversal, so our new version of map() can apply a function to elements in any data structure (figure 11.1).

Figure 11.1. map() takes an iterator over a sequence, in this case a list of circles, and a function that transforms a circle. map() applies the function to each element in the sequence and produces a new sequence with the transformed elements.

Listing 11.1. Generic map()

function* map<T, U>(iter: Iterable<T>, func: (item: T) => U):
    IterableIterator<U> {
    for (const value of iter) {
        yield func(value);
    }
}

This implementation works on iterators, but we should be able to apply a function of the form (item: T) => U to other types too. Let’s take, as an example, the Optional<T> type we defined in chapter 3, shown in the next listing.

Listing 11.2. Optional type

class Optional<T> {
    private value: T | undefined;
    private assigned: boolean;

    constructor(value?: T) {
        if (value) {
            this.value = value;
            this.assigned = true;
        } else {
            this.value = undefined;
            this.assigned = false;
        }
    }

    hasValue(): boolean {
        return this.assigned;
    }

    getValue(): T {
        if (!this.assigned) throw Error();

        return <T>this.value;
    }
}

It feels natural to be able to map a function (value: T) => U over an Optional<T>. If the optional contains a value of type T, mapping the function over it should return an Optional<U> containing the result of applying the function. On the other hand, if the optional doesn’t contain a value, mapping would result in an empty Optional<U> (figure 11.2).

Figure 11.2. Mapping a function over an optional value. If the optional is empty, map() returns an empty optional; otherwise, it applies the function to the value and returns an optional containing the result.

Let’s sketch out an implementation. We’ll put this function in a namespace. Because TypeScript doesn’t support function overloading, to have multiple functions with the same name, we need to put them in different namespaces so the compiler can determine the function we are calling.

Listing 11.3. Optional map()

namespace Optional {
    export function map<T, U>(                                         1
        optional: Optional<T>, func: (value: T) => U): Optional<U> {
        if (optional.hasValue()) {
            return new Optional<U>(func(optional.getValue()));         2
        } else {
            return new Optional<U>();                                  3
        }
    }
}

• 1 export simply makes the function visible outside the namespace.
• 2 If the optional has a value, we extract it, pass it to func(), and use its result to initialize an Optional<U>.
• 3 If the optional is empty, we create a new empty Optional<U>.

We can do something very similar with the TypeScript sum type T or undefined. Remember, Optional<T> is a DIY version of such a type that works even in languages that don’t support sum types natively, but TypeScript does. Let’s see how we can map over a “native” optional type T | undefined.

Mapping a function (value: T) => U over T | undefined should apply the function and return its result if we have a value of type T, or return undefined if we start with undefined.

Listing 11.4. Sum type map()

namespace SumType {
    export function map<T, U>(
        value: T | undefined, func: (value: T) => U): U | undefined {
        if (value == undefined) {
            return undefined;
        } else {
            return func(value);
        }
    }
}

These types can’t be iterated over, but it still makes sense for a map() function to exist for them. Let’s define another simple generic type, Box<T>, shown in the following listing. This type simply wraps a value of type T.

Listing 11.5. Box type

class Box<T> {
    value: T;        1

    constructor(value: T) {
        this.value = value;
    }
}

• 1 Box<T> simply wraps a value of type T.

Can we map a function (value: T) => U over this type? We can. As you might have guessed, map() for Box<T> would return a Box<U>: it will take the value T out of Box<T>, apply the function to it, and put the result back into a Box<U>, as shown in figure 11.3 and listing 11.6.

Figure 11.3. Mapping a function over a value in a Box. map() unpacks the value from the Box, applies the function, and then places the value back into a Box.

Listing 11.6. Box map()

namespace Box {
    export function map<T, U>(
        box: Box<T>, func: (value: T) => U): Box<U> {
        return new Box<U>(func(box.value));             1
    }
}

• 1 map() over Box<T> extracts the values, calls func() on it, and puts the result into a Box<U>.

We can map functions over many generic types. Why is this capability useful? It’s useful because map(), like iterators, provides another way to decouple types that store data from functions that operate on that data.

11.1.1. Processing results or propagating errors

As a concrete example, let’s take a couple of functions that process a numerical value. We’ll implement a simple square(), a function that takes a number as an argument and returns its square. We’ll also implement stringify(), a function that takes a number as an argument and returns its string representation, as shown in the next listing.

Listing 11.7. square() and stringify()

function square(value: number): number {
    return value ** 2;
}

function stringify(value: number): string {
    return value.toString();
}

Now let’s say that we have a readNumber() function, which reads a numeric value from a file, as shown in listing 11.8. Because we are dealing with input, we might run into some problems. What if the file doesn’t exist or can’t be opened, for example? In that case, read-Number() will return undefined. We won’t look at the implementation of this function; the important thing for our example is its return type.

Listing 11.8. readNumber() return type

function readNumber(): number | undefined {
    /* Implementation omitted */
}

If we want to read a number and process it by applying square() to it first and then stringify(), we need to ensure that we actually have a numerical value as opposed to undefined. A possible implementation is to convert from number | undefined to number, using if statements wherever needed, as the next listing shows.

Listing 11.9. Processing a number

function process(): string | undefined {
    let value: number | undefined = readNumber();

    if (value == undefined) return undefined;      1

    return stringify(square(value));               2
}

• 1 We need to check whether value is undefined. In that case, we immediately return undefined.
• 2 We process the value and return the result.

We have two functions that operate on numbers, but because our input can also be undefined, we need to handle that case explicitly. This is not particularly bad, but in general, the less branching our code has, the less complex it is. It is easier to understand and to maintain, and there are fewer opportunities for bugs. Another way to look at this is that process() itself simply propagates undefined; it doesn’t do anything useful with it. It would be better if we could keep process() responsible for processing and let someone else handle error cases. How can we do this? With the map() we implemented for sum types, as shown in the following listing.

Listing 11.10. Processing with map()

namespace SumType {
    export function map<T, U>(                                         1
        value: T | undefined, func: (value: T) => U): U | undefined {
        if (value == undefined) {
            return undefined;

        } else {
            return func(value);
        }
    }
}

function process(): string | undefined {
    let value: number | undefined = readNumber();

    let squaredValue: number | undefined =
        SumType.map(value, square);                                    2

    return SumType.map(squaredValue, stringify);                       3
}

• 1 This is the map() for sum types we implemented in listing 11.4.
• 2 Instead of explicitly checking for undefined, we call map() to apply square() on the value. If it is undefined, map() will give us back undefined.
• 3 Just as with square(), we map() our stringify() function on the squaredValue. If it is undefined, map() will return undefined.

Now our process() implementation has no branching. The responsibility for unpacking number | undefined into a number and checking for undefined is handled by map(). map() is generic and can be used across many other types (such as string | undefined) and in many other processing functions.

In our case, because square() is guaranteed to return a number, we can create a small lambda that chains square() and stringify(), and pass that to map() in the next listing.

Listing 11.11. Processing with lambda

function process(): string | undefined {
    let value: number | undefined = readNumber();

    return SumType.map(value,
        (value: number) => stringify(square(value)));       1
}

• 1 Lambda that passes the result of square() to stringify()

This implementation is a functional implementation of process(), in that the error propagation is delegated to map(). We’ll talk more about error handling in section 11.2, which discusses monads. For now, let’s look at another application of map().

11.1.2. Mix-and-match function application

Without the map() family of functions, if we have a square() function that squares a number, we would have to implement some additional logic to get a number from a number | undefined sum type. Similarly, we would have to implement some additional logic to get a value from a Box<number> and package it back in a Box-<number>, as the following listing shows.

Listing 11.12. Unpacking values for square()

function squareSumType(value: number | undefined)       1
    : number | undefined {
    if (value == undefined) return undefined;

    return square(value);
}

function squareBox(box: Box<number>): Box<number> {     2
    return new Box(square(box.value));
}

• 1 This function wraps the undefined check.
• 2 This function unpacks the value from Box and then puts the result into another Box.

So far, this isn’t too bad. But what if we want something similar with stringify()? Again, we’ll end up writing two functions that look a lot like the previous ones, as shown in the following code.

Listing 11.13. Unpacking values for stringify()

function stringifySumType(value: number | undefined)
    : string | undefined {
    if (value == undefined) return undefined;

    return stringify(value);
}

function stringifyBox(box: Box<number>): Box<string> {
    return new Box(stringify(box.value))
}

This starts to look like duplicate code, which is never good. If we have map() functions available for number | undefined and Box, they provide the abstraction to remove the duplicate code. We can pass either square() or stringify() to either SumType.map() or to Box.map() in the next listing; no additional code is needed.

Listing 11.14. Using map()

let x: number | undefined = 1;
let y: Box<number> = new Box(42);

console.log(SumType.map(x, stringify));
console.log(Box.map(y, stringify));

console.log(SumType.map(x, square));
console.log(Box.map(y, square));

Now let’s define this family of map() functions.

11.1.3. Functors and higher kinded types

What we talked about in the preceding section are functors.

Functors

A functor is a generalization of functions that perform mapping operations. For any generic type like Box<T>, a map() operation that takes a Box<T> and a function from T to U and produces a Box<U> is a functor (figure 11.4).

Figure 11.4. We have a generic type H that contains 0, 1, or more values of some type T and a function from T to U. In this case, T is an empty circle, and U is a full circle. The map() functor unpacks the T or Ts from the H<T> instance, applies the function, and then places the result back into an H<U>.

Functors are extremely powerful concepts, but most mainstream languages do not have a good way to express them because the general definition of a functor relies on higher kinded types.

Higher kinded types

A generic type is a type that has a type parameter, such as a generic type T, or a type like Box<T> that has a type parameter T. A higher kinded type, just like a higher-order function, represents a type parameter with another type parameter. T<U> or Box<T<U>>, for example, have a type parameter T that in turn has a type parameter U.

Because we don’t have a good way to express higher kinded types in TypeScript, C#, or Java, we can’t define a construct by using the type system to express a functor. Languages such as Haskell and Idris, which have more powerful type systems, make these definitions possible. In our case, though, because we can’t enforce this capability through the type system, we can think of it as more of a pattern.

We can say that a functor is any type H with a type parameter T (H<T>) for which we have a function map() that takes an argument of type H<T> and a function from T to U, and returns a value of type H<U>.

Alternatively, if we want to be more object-oriented, we can make map() a member function and say that H<T> is a functor if it has a method map() that takes a function from T to U and returns a value of type H<U>. To see exactly where the type system is lacking, we can try to sketch out an interface for it. Let’s call this interface Functor and have it declare map() in the next listing.

Listing 11.15. Sketch of Functor interface

interface Functor<T> {
    map<U>(func: (value: T) => U): Functor<U>;
}

We can update Box<T> to implement this interface in the following listing.

Listing 11.16. Box implementing the interface

class Box<T> implements Functor<T> {
    value: T;

    constructor(value: T) {
        this.value = value;
    }

    map<U>(func: (value: T) => U): Box<U> {
        return new Box(func(this.value));
    }
}

This code compiles; the only problem is that it isn’t specific enough. Calling map() on Box<T> returns an instance of type Box<U>. But if we work with Functor interfaces, we see that the map() declaration specifies that it returns a Functor<U>, not a Box<U>. This isn’t specific enough. We need a way to specify, when we declare the interface, exactly what the return type of map() will be (in this case, Box<U>).

We would like to be able to say, “This interface will be implemented by a type H with a type argument T.” The following code shows how this declaration would look like if TypeScript supported higher kinded types. It obviously doesn’t compile.

Listing 11.17. Functor interface

interface Functor<H<T>> {
    map<U>(func: (value: T) => U): H<U>;
}

class Box<T> implements Functor<Box<T>> {
    value: T;

    constructor(value: T) {
        this.value = value;
    }

    map<U>(func: (value: T) => U): Box<U> {
        return new Box(func(this.value));
    }
}

Lacking this, let’s just think of our map() implementations as a pattern for applying functions to generic types or values in some box.

11.1.4. Functors for functions

Note that we also have functors over functions. Given a function with any number of arguments that returns a value of type T, we can map a function that takes a T and produces a U over it, ending up with a function that takes the same inputs as the original function and returns a value of type U. map() in this case is simply function composition as shown in figure 11.5.

Figure 11.5. Mapping a function over another function composes the two functions. The result is a function that takes the same arguments as the original function and returns a value of the second function’s return type. The two functions need to be compatible; the second function must expect an argument of the same type as the one returned by the original function.

As an example, let’s take a function that takes two arguments of type T and produces a value of type T, and implement its corresponding map() in the next listing. This returns a function that takes two arguments of type T and returns a value of type U.

Listing 11.18. Function map()

namespace Function {
    export function map<T, U>(
        f: (arg1: T, arg2: T) => T, func: (value: T) => U)     1
        : (arg1: T, arg2: T) => U {                            2
        return (arg1: T, arg2: T) => func(f(arg1, arg2));      3
    }
}

• 1 map() takes a function (T, T) => T, and a function T => U to map over it.
• 2 map() returns a function (T, T) => U.
• 3 The implementation simply returns a lambda that composes func() and f() by calling func() on the result of f().

Let’s map stringify() over an add() function that takes two numbers and returns their sum. The result is a function that takes two numbers and returns a string—the stringified result of adding the two numbers, as shown in the following listing.

Listing 11.19. Applying map() over a function

function add(x: number, y: number): number {                    1
    return x + y;
}

function stringify(value: number): string {                     2
    return value.toString();
}


const result: string = Function.map(add, stringify)(40, 2);     3

• 1 add() simply sums its arguments.
• 2 stringify() has the same implementation as before.
• 3 We map the stringify() function over add(). Then we call the returned functions with the arguments 40 and 2. The result is the string “42”.

After functors, we’ll cover one final construct: the monad.

11.1.5. Exercise

1

We have an interface IReader<T> that defines a single method, read(): T. Implement a functor that maps a function (value: T) => U over an IReader<T> and returns an IReader<U>.

11.2. Monads

You have probably heard the term monad, as it’s been getting a lot of attention lately. Monads are making their way into mainstream programming, so you should know one when you see it. Building on top of section 11.1, in this section we will explain what a monad is and how it is useful. We’ll start with a few examples and then look at the general definition.

11.2.1. Result or error

In section 11.1, we had a readNumber() function that returned number | undefined. We used functors to sequence processing with square() and stringify(), so that if readNumber() returns undefined, no processing happens, and the undefined is propagated through the pipeline.

This type of sequencing works with functors as long as only the first function—in this case, readNumber()—can return an error. But what happens if any of the functions we want to chain can error out? Let’s say that we want to open a file, read its content as a string, and then deserialize that string into a Cat object, as shown in listing 11.20.

We have an openFile() function that returns an Error or a FileHandle. Errors can occur if the file doesn’t exist, if it is locked by another process, or if the user doesn’t have permission to open it. If the operation succeeds, we get back a handle to the file.

We have a readFile() function that takes a FileHandle and returns either an Error or a string. Errors can occur if the file can’t be read, perhaps due to being too large to fit in memory. If the file can be read, we get back a string.

Finally, deserializeCat() function takes a string and returns an Error or a Cat instance. Errors can occur if the string can’t be deserialized into a Cat object, perhaps due to missing properties.

All these functions follow the “return result or error” pattern from chapter 3, which suggests returning either a valid result or an error from a function, but not both. The return type will be an Either<Error, ...>.

Listing 11.20. Functions returning result or error

declare function openFile(path: string): Either<Error, FileHandle>;      1

declare function readFile(handle: FileHandle): Either<Error, string>;    2

declare function deserializeCat(
    serializedCat: string): Either<Error, Cat>;                          3

• 1 openFile() returns an Error or a FileHandle.
• 2 readFile() returns an Error or a string.
• 3 deserializeCat() returns an Error or a Cat.

We are omitting the implementations, as they are not important. Let’s also quickly review the implementation of Either from chapter 3 in the next listing.

Listing 11.21. Either type

class Either<TLeft, TRight> {
    private readonly value: TLeft | TRight;                       1
    private readonly left: boolean;                               1

    private constructor(value: TLeft | TRight, left: boolean) {   2
        this.value = value;
        this.left = left;
    }

    isLeft(): boolean {
        return this.left;
    }

    getLeft(): TLeft {                                            3
        if (!this.isLeft()) throw new Error();

        return <TLeft>this.value;
    }

    isRight(): boolean {
        return !this.left;
    }
    getRight(): TRight {                                          3
        if (this.isRight()) throw new Error();

        return <TRight>this.value;
    }

    static makeLeft<TLeft, TRight>(value: TLeft) {                4
        return new Either<TLeft, TRight>(value, true);
    }

    static makeRight<TLeft, TRight>(value: TRight) {              4
        return new Either<TLeft, TRight>(value, false);
    }
}

• 1 The type wraps a value of either TLeft or TRight and a flag to keep track of that type is used.
• 2 Private constructor, as we need to make sure that the value and boolean flag are in sync
• 3 Attempting to get a TLeft when we have a TRight, or vice versa, throws an error.
• 4 Factory functions call the constructor and ensure that the boolean flag is consistent with the value.

Now let’s see in the next listing how we could chain these functions together into a readCatFromFile() function that takes a file path as an argument and returns a Cat instance, or an Error if anything went wrong along the way.

Listing 11.22. Processing and explicitly checking for errors

function readCatFromFile(path: string): Either<Error, Cat> {            1
    let handle: Either<Error, FileHandle> = openFile(path);             2

    if (handle.isLeft()) return Either.makeLeft(handle.getLeft());      3

    let content: Either<Error, string> = readFile(handle.getRight());   4

    if (content.isLeft()) return Either.makeLeft(content.getLeft());    5

    return deserializeCat(content.getRight());                          6
}

• 1 readCatFromFile() returns either an Error or a Cat instance.
• 2 First, we attempt to open the file. We get back either an Error or a FileHandle.
• 3 If we have an Error, we return early. We call Either.makeLeft(), as we need to convert from Either<Error, FileHandle> to Either<Error, Cat>. We unpack the Error from Either<Error, FileHandle> and pack it back into an Either<Error, Cat>.
• 4 If we have a FileHandle, we attempt to read the content of the file.
• 5 Similarly, we return early if we encountered an error reading the file.
• 6 Finally, if we have the content, we call deserializeCat(). Because this function has the same return type as readCatFromFile(), we simply return its result.

This function is very similar to the first implementation of process() earlier in this chapter. There, we provided an updated implementation that removed all the branching and error checking from the function and delegated those tasks to map(). Let’s see what a map() for Either<TLeft, TRight> would look like in listing 11.23. We will follow the convention “Right is right; left is error,” which means that TLeft contains an error, so map() will just propagate it. map() will apply a given function only if the Either contains a TRight.

Listing 11.23. Either map()

namespace Either {
    export function map<TLeft, TRight, URight>(
        value: Either<TLeft, TRight>,
        func: (value: TRight) => URight): Either<TLeft, URight> {       1
        if (value.isLeft()) return Either.makeLeft(value.getLeft());    2

        return Either.makeRight(func(value.getRight()));                3
    }
}

• 1 func() is only applied if the input Either contains a value of type TRight, so its argument must be of type TRight.
• 2 If the input contains a TLeft, we unpack it from Either<TLeft, TRight> and repack it into Either<TLeft, URight>.
• 3 If the input contains a TRight, we unpack it, apply func() to it, and pack the result it into an Either<TLeft, URight>.

There is a problem with using map(), though: the types of the functions it expects as arguments are incompatible with the functions we are using. With map(), after we call openFile() and get back an Either<Error, FileHandle>, we would need a function (value: FileHandle) => string to read its content. That function can’t itself return an Error, like square() or stringify(). But in our case, readFile() can fail, so it doesn’t return string; it returns Either<Error, string>. If we attempt to use it in our readCatFromFile(), we get a compilation error, as the next listing shows.

Listing 11.24. Incompatible types

function readCatFromFile(path: string): Either<Error, Cat> {
    let handle: Either<Error, FileHandle> = openFile(path);

    let content: Either<Error, string> = Either.map(handle, readFile);     1

    /* ... */
}

• 1 This fails to compile due to a type mismatch.

The error message we get is

Type   'Either<Error,   Either<Error,   string>>'   is   not
assignable to type 'Either<Error, string>'.

Our functor falls short here. Functors can propagate an initial error through the processing pipeline, but if every step in the pipeline can fail, functors no longer work. In figure 11.6, the black square represents an Error, and the white and black circles represent two types, such as FileHandle and string.

Figure 11.6. We can’t use a functor in this case because the functor is defined to map a function from a white circle to a black circle. Unfortunately, our function returns a type already wrapped in an Either (an Either<black square, black circle>). We need an alternative to map() that can deal with this type of function.

map() from Either<Error, FileHandle> would need a function from File-Handle to string to produce an Either<Error, string>. Our readFile() function, on the other hand, is from FileHandle to Either<Error, string>.

This problem is easy to fix. We need a function similar to map() that goes from T to Either<Error, U>, as shown in the next listing. The standard name for such a function is bind().

Listing 11.25. Either bind()

namespace Either {
    export function bind<TLeft, TRight, URight>(
        value: Either<TLeft, TRight>,
        func: (value: TRight) => Either<TLeft, URight>       1
        ): Either<TLeft, URight> {
        if (value.isLeft()) return Either.makeLeft(value.getLeft());

        return func(value.getRight());                       2
    }
}

• 1 func() has a different type from the func() in map().
• 2 We can simply return the result of func(), as it has the same type as the result of bind().

As we can see, the implementation is even simpler than the one for map(): after we unpack the value, we simply return the result of applying func() to it. Let’s use bind() to implement our readCatFromFile() function in the next listing and get the desired branchless error propagation behavior.

Listing 11.26. Branchless readCatFromFile()

function readCatFromFile(path: string): Either<Error, Cat> {
    let handle: Either<Error, FileHandle> = openFile(path)

    let content: Either<Error, string> =
        Either.bind(handle, readFile);               1

    return Either.bind(content, deserializeCat);     2
}

• 1 Unlike map(), this code works. Applying readFile() to handle gives us back an Either<Error, string>.
• 2 deserializeCat() has the same return type as readCatFromFile(), so we simply return the result of bind().

This version seamlessly chains together openFile(), readFile(), and deserialize-Cat() so that if any of the functions fails, the error gets propagated as the result of readCatFromFile(). Again, branching is encapsulated in the bind() implementation, so our processing function is linear.

11.2.2. Difference between map() and bind()

Before moving on to define monads, let’s take another simplified example and contrast map() and bind(). We’ll again use Box<T>, a generic type that simply wraps a value of type T. Although this type is not particularly useful, it is the simplest generic type we can have. We want to focus on how map() and bind() work with values of types T and U in some generic context, such as Box<T>, Box<U> (or T[], U[]; or Optional<T>, Optional<U>; or Either<Error, T>, Either<Error, U>, and so on).

For a Box<T>, a functor (map()) takes a Box<T> and a function from T to U and returns a Box<U>. The problem is that we have scenarios in which our functions are directly from T to Box<U>. This is what bind() is for. bind() takes a Box<T> and a function from T to Box<U> and returns the result of applying the function to the T inside Box<T> (figure 11.7).

Figure 11.7. Contrasting map() and bind(). map() applies a function T => U over a Box<T> and returns a Box<U>. bind() applies a function T => Box><U> over a Box<T> and returns a Box<U>.

If we have a function stringify() that takes a number and returns its string representation, we can map() it on a Box<number> and get back a Box<string>, as shown in the following listing.

Listing 11.27. map() on Box

namespace Box {
    export function map<T, U>(                               1
        box: Box<T>, func: (value: T) => U): Box<U> {
        return new Box<U>(func(box.value));
    }
}

function stringify(value: number): string {                  2
    return value.toString();
}

const s: Box<string> = Box.map(new Box(42), stringify);      3

• 1 map() implementation for Box from earlier in this chapter.
• 2 stringify() implementation from earlier in this chapter takes a number and returns a string.
• 3 We can map stringify() on a Box<number> and get back a Box<string>.

If instead of stringify(), which goes from number to string, we have a boxify() function that goes from number directly to Box<string>, map() won’t work. We’ll need bind() instead, as shown in the next listing..

Listing 11.28. bind() on Box

namespace Box {
    export function bind<T, U>(
        box: Box<T>, func: (value: T) => Box<U>): Box<U> {    1
        return func(box.value);
    }
}

function boxify(value: number): Box<string> {                 2
    return new Box(value.toString());
}

const b: Box<string> = Box.bind(new Box(42), boxify);         3

• 1 bind() unpacks the value from Box and calls func() on it.
• 2 boxify() differs from stringify() in that it returns a Box<string> instead of a string.
• 3 We can bind boxify() on a Box<number> and get back a Box<string>.

The result of both map() and bind() is still a Box<string>. We still go from Box<T> to Box<U>; the difference is how we get there. In the map() case, we need a function from T to U. In the bind() case, we need a function from T to Box<U>.

11.2.3. The monad pattern

A monad consists of bind() and one more, simpler function. This other function takes a type T and wraps it into the generic type, such as Box<T>, T[], Optional<T>, or Either<Error, T>. This function is usually called return() or unit().

A monad allows structuring programs generically while encapsulating away boilerplate code needed by the program logic. With monads, a sequence of function calls can be expressed as a pipeline that abstracts away data management, control flow, or side effects.

Let’s look at a few examples of monads. We can start with our simple Box<T> type and add unit() to it in the next listing to complete the monad.

Listing 11.29. Box monad

namespace Box {
    export function unit<T>(value: T): Box<T> {               1
        return new Box(value);
    }

    export function bind<T, U>(
        box: Box<T>, func: (value: T) => Box<U>): Box<U> {    2
        return func(box.value);
    }
}

• 1 unit() simply calls Box’s constructor to wrap the given value into an instance of Box<T>.
• 2 bind() unpacks the value from Box and calls func() on it.

The implementation is very straightforward. Let’s look at the Optional<T> monad functions in the following listing.

Listing 11.30. Optional monad

namespace Optional {
    export function unit<T>(value: T): Optional<T> {        1
        return new Optional(value);
    }

    export function bind<T, U>(
        optional: Optional<T>,
        func: (value: T) => Optional<U>): Optional<U> {
        if (!optional.hasValue()) return new Optional();    2

        return func(optional.getValue());                   3
    }
}

• 1 unit() takes a value of type T and wraps it into an Optional<T>.
• 2 If the optional is empty, bind() returns an empty optional of type Optional<U>.
• 3 If the optional contains a value, bind() returns the result of calling func() on it.

Very much as with functors, if a programming language can’t express higher kinded types, we don’t have a good way to specify a Monad interface. Instead, let’s think of monads as a pattern.

Monad Pattern

A monad is a generic type H<T> for which we have a function like unit() that takes a value of type T and returns a value of type H<T>, and a function like bind() that takes a value of type H<T> and a function from T to H<U>, and returns a value of type H<U>.

Bear in mind that because most languages use this pattern, without a way to specify an interface for the compiler to check, in many instances the two functions, unit() and bind(), may show up under different names. You may hear the term monadic, as in monadic error handling, which means that error handling follows the monad pattern.

Next, we’ll look at another example. You may be surprised to see that this example showed up much earlier in this book, in chapter 6; we just didn’t have a name for it yet.

11.2.4. The continuation monad

In chapter 6, we looked at ways to simplify asynchronous code. We ended up looking at promises. A promise represents the result of a computation that will happen sometime in the future. Promise<T> is the promise of a value of type T. We can schedule execution of asynchronous code by chaining promises, using the then() function.

Let’s say we have a function that determines our location on the map. Because this function will work with the GPS, it may take longer to finish, so we make it asynchronous. It will return a promise of type Promise<Location>. Next, we have a function that, given a location, will contact a ride-sharing service to get us a Car, as the next listing shows.

Listing 11.31. Chaining promises

declare function getLocation(): Promise<Location>;
declare function hailRideshare(location: Location): Promise<Car>;

let car: Promise<Car> = getLocation().then(hailRideshare);         1

• 1 When getLocation() returns, hailRideshare() will be invoked with its result.

This should look very familiar to you at this point. then() is just how Promise<T> spells bind()!

As we saw in chapter 6, we can also create an instantly resolved promise by using Promise.resolve(). This takes a value and returns a resolved promise containing that value, which is the Promise<T> equivalent of unit().

It turns out that chaining promises, an API available in virtually all mainstream programming languages, is monadic. It follows the same pattern that we saw in this section, but in a different domain. While dealing with error propagation, our monad encapsulated checking whether we have a value that we can continue operating on or have an error that we should propagate. With promises, the monad encapsulates the intricacies of scheduling and resuming execution. The pattern is the same, though.

11.2.5. The list monad

Another commonly used monad is the list monad. Let’s look at an implementation over sequences: a divisors() function that takes a number n and returns an array containing all of its divisors except 1 and n itself, as shown in listing 11.32.

This straightforward implementation starts from 2 and goes up to half of n, and adds all numbers it finds that divide n without a remainder. There are more efficient ways to find all divisors of a number, but we’ll stick to a simple algorithm in this case.

Listing 11.32. Divisors

function divisors(n: number): number[] {
    let result: number[] = [];

    for (let i = 2; i <= n / 2; i++) {
        if (n % i == 0) {
            result.push(i);
        }
    }

    return result;
}

Now let’s say we want to take an array of numbers and return an array containing all their divisors. We don’t need to worry about dupes. One way to do this is to provide a function that takes an array of input numbers, applies divisors() to each of them, and joins the results of all the calls to divisors() into a final result, as shown in the following code.

Listing 11.33. All divisors

function allDivisors(ns: number[]): number[] {
    let result: number[] = [];

    for (const n of ns) {
        result = result.concat(divisors(n));
    }

    return result;
}

It turns out that this pattern is common. Let’s say that we have another function, anagrams(), that generates all permutations of a string and returns an array of strings. If we want to get the set of all anagrams of an array of strings, we would end up implementing a very similar function, as the next listing shows.

Listing 11.34. All anagrams

declare function anagram(input: string): string[];      1

function allAnagrams(inputs: string[]): string[] {      2
    let result: string[] = [];

    for (const input of inputs) {
        result = result.concat(anagram(input));
    }

    return result;
}

• 1 anagram() implementation omitted
• 2 allAnagrams() is very similar to allDivisors().

Now let’s see whether we can replace allDivisors() and allAnagrams() with a generic function in the next listing. This function would take an array of Ts and a function from T to an array of Us, and return an array of Us.

Listing 11.35. List bind()

function bind<T, U>(inputs: T[], func: (value: T) => U[]): U[] {    1
    let result: U[] = [];

    for (const input of inputs) {
        result = result.concat(func(input));                        2
    }

    return result;
}

function allDivisors(ns: number[]): number[] {                      3
    return bind(ns, divisors);
}

function allAnagrams(inputs: string[]): string[] {                  4
    return bind(inputs, anagram);
}

• 1 bind() takes an array of Ts, a function that returns an array of Us given a T, and returns an array of Us.
• 2 We apply func() to each input T and concatenate the results.
• 3 allDivisors() can be expressed by binding divisors() to an array of numbers.
• 4 allAnagrams() can be expressed by binding anagram() to an array of strings.

As you’ve probably guessed, this is the bind() implementation for the list monad. In the case of lists, bind() flattens the arrays returned by each call of the given function into a single array. While the error-propagating monad decides whether to propagate an error or apply a function and the continuation monad wraps scheduling, the list monad combines a set of results (a list of lists) into a single flat list. In this case, the box is a sequence of values (figure 11.8).

Figure 11.8. List monad: bind() takes a sequence of Ts (white circles, in this case) and a function T => sequence of Us (black circles, in this case). The result is a flattened list of Us (black circles).

The unit() implementation is trivial. Given a value of type T, it returns a list containing just that value. This monad generalizes to all kinds of lists: arrays, linked lists, and iterator ranges.

11.2.6. Other monads

A couple of other common monads, which are popular in functional programming languages with pure functions (functions that don’t have side effects) and immutable data, are the state monad and the IO monad. We’ll provide only a high-level overview of these monads, but if you decide to learn a functional programming language such as Haskell, you will likely encounter them early in your journey.

The state monad encapsulates a piece of state that it passes along with a value. This monad enables us to write pure functions that, given a current state, produce a value and an updated state. Chaining these together with bind() allows us to propagate and update state through a pipeline without explicitly storing it in a variable, enabling purely functional code to process and update state.

The IO monad encapsulates side effects. It allows us to implement pure functions that can still read user input or write to a file or terminal because the impure behavior is removed from the function and wrapped in the IO monad.

If you are interested in learning more, section 11.3 provides some resources for further study.

11.2.7. Exercise

1

Let’s take the function type Lazy<T> defined as () => T, a function that takes no arguments and returns a value of type T. It’s Lazy because it produces a T, but only when we ask it to. Implement unit(), map(), and bind() for this type.

11.3. Where to next?

We have covered a lot of ground, from primitive types and composition, to function types, subtyping, generics, and a sliver of higher kinded types. Still, we’ve barely scratched the surface of the world of type systems. In this final section, we’ll look at a few topics you may be interested in learning more about and provide some starting points for each one.

11.3.1. Functional programming

Functional programming is a very different paradigm from object-oriented programming. Learning a functional programming language gives you another way to think about code. The more ways you have to approach a problem, the easier it is to break it down and solve it.

More and more features and patterns from functional programming are making their way into nonfunctional languages, which is a testament to their applicability. Lambdas and closures, immutable data structures, and reactive programming all come from the functional world.

The best way to get started is to pick up a functional programming language. I recommend Haskell as a starting language. It has a fairly simple syntax and a very powerful type system, and it stands on a solid theoretical foundation. A good, easy-to-read introductory book on the topic is Learn You a Haskell for Great Good! by Miran Lipovaca, published by No Starch Press.

11.3.2. Generic programming

As we saw in previous chapters, generic programming enables extremely powerful abstractions and code reusability. Generic programming became popular with the C++ standard template library and its mix-and-match collection of data structures and algorithms.

Generic programming has its roots in abstract algebra. Alexander Stepanov, who coined the term generic programming and implemented the original template library, wrote two books on the subject: Elements of Programming (coauthored with Paul McJones) and From Mathematics to Generic Programming (coauthored with Daniel E. Rose), both published by Addison-Wesley Professional.

Both books leverage some math, but I hope that fact won’t discourage you. The elegance and beauty of the code are astonishing. The underlying theme is that with the right abstractions, we don’t need to compromise: we can have code that is succinct, performant, easy to read, and elegant.

11.3.3. Higher kinded types and category theory

As we mentioned earlier, constructs such as functors come directly from category theory. Bartosz Milewski’s Category Theory for Programmers (self-published) is a surprisingly easy-to-read introduction to this field.

We talked about functors and monads, but there is a lot more to higher kinded types. It will probably take a while for things to trickle down to more mainstream languages, but if you want to get ahead of the curve, Haskell is a good language with which to grasp these concepts.

Having the ability to specify higher-level abstractions such as monads enables us to write even-more-reusable code.

11.3.4. Dependent types

We didn’t have space to cover dependent types in this book, but if you want to know more ways that a powerful type system makes code safer, this topic is another good one.

Very briefly, we saw how a type can dictate the values that a variable can take. We also looked at generics, in that a type can dictate what another type can be (type parameters). Dependent types flip this situation around: we have values that dictate types. The classic example is encoding the length of a list in the type system. A list of numbers with two elements ends up having a different type from a list of numbers with five elements, for example. Concatenating them gives us another type: a list with seven elements. You can imagine how encoding such information in the type system can guarantee, for example, that we never index out of bounds.

If you want to learn more about dependent types, I recommend Type Driven Development with Idris by Edwin Brady, published by Manning. Idris is a programming language with a syntax very similar to Haskell’s, but it adds support for dependent types.

11.3.5. Linear types

In chapter 1, we briefly mentioned the deep connection between type systems and logic. Linear logic is a different take on classic logic that deals with resources. Unlike classic logic, in which a deduction, if true, is true forever, a linear logic proof consumes deductions.

This has a direct application in programming languages, in which using linear types in a type system encodes resource use tracking. Rust is a programming language that is steadily gaining in popularity; it uses linear types to ensure resource safety. Its borrow checker ensures that there is always a single owner of a resource. If we pass an object to a function, we transfer ownership of the resource, and the compiler no longer allows us to reference the resource until the function hands back the resource. This situation aims to eliminate concurrency issues, as well as the dreaded “use after free” and “double free” of C.

Rust is another good language to learn for its powerful generic support and unique safety features. The Rust Programming Language book is available for free on the Rust website and provides a good introduction to the language (https://doc.rust-lang.org/book).

Summary

• map() generalizes beyond iterators to other generic types.
• Functors encapsulate data unboxing with applications in composition and error propagation.
• With higher kinded types, we can express constructs such as functors by using generics that themselves have type parameters.
• Monads allow us to chain operations that return values in a Box.
• Error monads allow us to chain together operations that return result or failure, encapsulating the error-propagation logic.
• Promises are monads that encapsulate scheduling/asynchronous execution.
• The list monad applies a function that produces a sequence to a sequence of values and returns a flattened sequence.
• In languages that don’t support higher kinded types, we can think of functors and monads as being patterns that we can apply to various problems.
• Haskell is a good language to learn for understanding functional programming and higher kinded types.
• Idris is a good language to learn for understanding dependent types and their applications.
• Rust is a good language to learn for understanding linear types and their applications. I hope that you enjoyed this book, learned something you can use in your work, and gained some new perspectives. Happy, type-safe programming!

11.4. Answers to exercises

An even more general map

1

A possible implementation uses the object-oriented decorator pattern we recapped in chapter 5 to provide another type implementing IReader<U> that wraps an IReader<T> and, when read() is called, maps the given function over the original value:

interface IReader<T> {
    read(): T;
}

namespace IReader {
    class MappedReader<T, U> implements IReader<U> {
        reader: IReader<T>;
        func: (value: T) => U;

        constructor(reader: IReader<T>, func: (value: T) => U) {
            this.reader = reader;
            this.func = func;
        }

        read(): U {
            return this.func(this.reader.read());
        }
    }

    export function map<T, U>(reader: IReader<T>, func: (value: T) => U)
        : IReader<U> {
        return new MappedReader(reader, func);
    }
}

 

Monads

1

A possible implementation follows. Notice the difference between map() and bind().

type Lazy<T> = () => T;

namespace Lazy {
    export function unit<T>(value: T): Lazy<T> {
        return () => value;
    }

    export function map<T, U>(lazy: Lazy<T>, func: (value: T) => U)
        : Lazy<U> {
        return () => func(lazy());
    }

    export function bind<T, U>(lazy: Lazy<T>, func: (value: T) =>
Lazy<U>)
    : Lazy<U> {
        return func(lazy());
    }
}