Parser and Getting Complicated with Types

Quick context: Validator<T> is a function that returns a Result<T>:

type Validator<T> = (value: any) => Result<T>;

When sharing some of this with a coworker to help figure out some type questions they quickly pointed out that this is in fact a Parser (thanks Dennis). These are things an informally trained developer (me) probably should have been able to identify at this point in their career.

Mapping the understanding of what a Parser is to what I had named it caused confusion. So all things Validator<T> have become Parser<T>. Naming: one of the two hard things.

Combining more than Two Parsers

In the Parser<T> library the function oneOf accepts two Parser<T> types and returns the union of them:

function oneOf<A,B>(a: Parser<A>, Parser<B>): Parser<(A|B)> {
  return value => mapFailure(a(value), () => b(value));
}

A more complex Parser<T> is now created out of simpler ones.

const isStringOrNumber = oneOf(isString, isNumber);

TypeScript can infer that isStringOrNumber has the type of Parser<string|number>.

This works great when combining two parsers, but when more than two are combined with oneOf it requires nested calls:

const isThing = oneOf(isNull, oneOf(isPerson, isAnimal));

Assuming isPerson is Parser<Person> and isAnimal is Parser<Animal>, const isThing is inferred by TypeScript to be:

type Parser<null | Person | Animal>

Each additional Parser<T> requires another call of oneOf. Writing a oneOf that takes one or more Parser<T> types is straight forward:

function oneOf(parser, ... parsers) {
  return value => parsers(
     (result, next) => mapFailure(result, () => next(result)),
     parser(value)
  )
}

However, writing the correct type signature for this function was beyond my grasp.

My first attempt I knew couldn’t work:

function oneOf<T>(parser: Parser<T>, ...parsers: Parser<T>[]): Parser<T> {

In use, TypeScript’s inference was not happy:

const example = oneOf(isString, isNumber, isBoolean);

Types of property 'value' are incompatible.
          Type 'number' is not assignable to type 'string'.

The T was being captured as string because the first argument to oneOf is a Parser<string>. However isNumber is a Parser<number>, so the two T did not match and tsc was not happy. Removing the first parser: Parser<T> didn’t help.

If TypeScript is told what the union is, then everything is ok:

const example = oneOf<string|number|boolean>(isString, isNumber, isBoolean);

But the best API experience is one in which the correct type is inferred.

After varying attempts of picking out similar cases in TypeScript’s Advanced Types I gave up and posed the question in the company’s #typescript Slack channel.

The magical internet people debated about Parser<T> and Result<T> so I tried to simplify things to the “base case” and got rid of Result<T>:

type Machine<T> = () => T

Is it possible to create a function signature such that a list of Machine<*>s of differing <T>s via variadic type arguments could infer the union Machine<T1|T2|T3|...>:

function oneOf(... machines: Array<Machine<?>>>): Machine<(UNION of ?)> {

The magical internet people came up with a solution (thank you, Tal).

type MachineType<T> = T extends Machine<infer U> ? U : never;

function<M extends Machine<any>[]>(...machines: M): Machine<MachineType<M[number]>> {

After mapping it into the Parser domain, It worked!

type ParserType<T> = T extends Parser<infer U> ? U : never;

function<P extends Parser<any>[]>oneOf(...machines: P): Parser<ParserType<P[number]>> {

const example = oneOf(isNumber, isString, isBoolean);

Running tsc passed, and the inferred type of const example is:

const example: (value: any) => Result<string | number | boolean>

Now to understand why it works.

Conditional Types: ParserType<T>

The first thing to understand is ParserType<T>, which uses a Conditional Type:

type ParserType<T> = T extends Parser<infer U> ? U : never;

This is essentially a function within the type analysis stage of TypeScript (somewhat analogous to Flow’s $Call utility type). My first understanding of this reads as:

Given a type T, if it extends Parser<infer U> return U, otherwise never.

Using ParserType with any Parser<T> will give the type of T. So given any function that is a Parser<T>, the type of <T> can be inferred.

Within the extends clause of a conditional type, it is now possible to have infer declarations that introduce a type variable to be inferred. Such inferred type variables may be referenced in the true branch of the conditional type. It is possible to have multiple infer locations for the same type variable.

Type inference in conditional types

Take an example parsePerson parser which is defined using objectOf:

const parsePerson = objectOf({
  name: isString,
  email: isString,
  metInPerson: isBoolean
});

type Person = ParserType<typeof parsePerson>;

// This is ok!
const valid: Person = {
  name: 'Nausicaa',
  email: 'nausica@valleyofthewind.website',
  metInPerson: false,
};

// This fails!
const invalid: Person = {}; // Type Error

type Person is inferred to be:

type Person = {
    name: string;
    email: string;
    metInPerson: boolean;
}

const invalid: Person fails because:

Type '{}' is missing the following properties from type '{ name: string; email: string; metInPerson: boolean; }': name, email, metInPerson

So now the return value of oneOf is almost understood:

: Parser<ParserType<P[number]>>

This says:

Returns a Parser<T> whose T is the ParserType of P[number].

Well what is P[number]?

Mapped Types

In TypeScript, Mapped Types allow one to take the key and value types of one type, and transform them into another.

If you’ve used Partial<T> or ReadOnly<T>, you have used a Mapped Type. The example implementations of those are given as:

type Readonly<T> = {
    readonly [P in keyof T]: T[P];
}
type Partial<T> = {
    [P in keyof T]?: T[P];
}

Given a type with an index, the type that is used for the index’s value can be accessed using its key type:

type MyIndexedType = {[key: number]: (number|boolean|string)};
type ValueType = MyIndexedType[number];

In this example ValueType will have the type (number|boolean|string).

In the return signature of oneOf there is a P[number].

: Parser<ParserType<P[number]>>

Assuming P is an indexed type with keys and values whose key type is a number, this gives the type of the value stored in P.

So what is P?

function<P extends Parser<any>[]>oneOf(

P is an array of Parser<any>[]. Well it extends Parser<any>[].

This is where the magic happens.

TypeScript captures the T of each Parser<any> and stores it in P. Because an Array is an indexed type whose key is number, the type of P can also be expressed like this:

type P = {[number]: (Parser<number>|Parser<string>|Parser<boolean>)};

There it is! The union is the value type at P[number].

Putting the Pieces Together

ParserType is a Conditional Type that given a Parser<T>, returns T.

What happens when ParserType is given a union of Parser<T> types.

type T = ParserType<(Parser<string> | Parser<number>)>

TypeScript infers the union for T:

type T = string | number

Given a Mapped Type P that extends Parser<T>[], the union of Parser<T> types is available at P[number].

It follows then that passing the P[number] into ParserType will provide the union of T types in Parser<T>. That is exactly what the return type in oneOf does.

Reading the new signature for oneOf is now less cryptic:

function oneOf<P extends Parser<any>[]>(
  ...parsers: P
): Parser<ParserType<P[number]>> {

Now to wrap up the implementation.

Using oneOf doesn’t work unless there is at least one Parser<T>. The signature can be updated to require one:

function oneOf<T, P extends Parser<any>[]>(
  parser: Parser<T>,
  ...parsers: P
): Parser<T|ParserType<P[number]>> {
    // no additional parsers, return the single parser to be used as is
    if (parsers.length === 0) {
        return parser;
    }

    return value => mapFailure(
        parsers.reduce(
            // with each reduction, only, try to parse when the previous was a Failure
            (result, next) => mapFailure(result, () => next(value)),
            // seed the result with the first parser
            parser(value)
        ),
        // if all parsers fail, indicate that there were multiple parsers attempted
        () => failure(value, `'${value}' did not match any of ${parsers.length+1} validators`)
    );
}

Using oneOf

Using oneOf now looks like this:

const parseStatus = oneOf(
    isExactly('pending'),
    isExactly('shipped'),
    isExactly('delivered'),
);

This expresses a Parser<T> that will fail if the string is not 'pending', 'shipped', or 'delivered'.

With the new signature of oneOf, TypeScript now infers parseStatus to have the type:

const parseStatus: Parser<'pending'|'shipped'|'delivered'>;

Combined with mapSuccess, the Success<T> will guarantee that the value is one of those three exact strings.

mapSuccess(parseStatus('other'), status => {
  switch(status) {
    case 'something': return 'not valid';
  }
});

This fails type checking:

Type '"something"' is not comparable to type '"shipped" | "pending" | "delivered"'.

This works with the most complex of Parser<T>s:

const json: Parser<any> = value = {
    try {
        return success(JSON.parse(value));
    } catch(error) {
        return failure(value, error.description);
    }
}

const employeesParser = mapParser(json, objectOf({
    employees: arrayOf(objectOf({
        role: oneOf(
             isExactly('Vice President'),
             isExactly('Manager'),
             isExactly('Individual Contributor')
        ),
        // This one is for you Dennis
        // assuming ISO8601 Date strings and a modern browser
        hireDate: mapParser(isString, (value) => success(new Date(value)))
    }))
})));

mapSuccess(employeesParser("{...JSON HERE...}"), (valid) => {
    valid.employees.forEach(employee => {
        const employmentDurationInMS = (
            Date.now() - employee.hireDate.getTime()
        );

        switch(employee.role) {
            case "Not A Real Role": {
            }
        }
    });
});

The case "Not A Real Role": doesn’t exist for employee.role:

Type '"Not A Real Role"' is not comparable to type '"Manager" | "Individual Contributor" | "Vice President"'

Lovely!

Here’s the inferred type of employeesParser’s use of oneOf:

function oneOf<"Vice President", [Parser<"Manager">, Parser<"Individual Contributor">]>(parser: Parser<"Vice President">, parsers_0: Parser< "Manager">, parsers_1: Parser<"Individual Contributor">): Parser<...>

We can see where:

1. The Parser<"Manager"> and Parser<"Individual Contributor"> types are captured in P.
2. The parsers_0 and parsers_1 are spread as arguments to oneOf with the correct parser types.