Home > Net >  Typing based on subsets of unions in TypeScript
Typing based on subsets of unions in TypeScript

Time:01-24

I am working on a TypeScript library (here it is) for algebraic data types (or whatever one wishes to call them), and am struggling with some of the more intricate typing.

The algebraic data types work like this:

// Create ADT instantiator
const value_adt = adt({
    num: (value: number) => value,
    str: (value: string) => value,
    obj: (value: object) => value,
});

// Extract union of variants
type ValueADT = Variants<typeof value_adt>;

// 'ValueADT' will be typed as:
// { [tag]: "num", value: number } |
// { [tag]: "str", value: string } |
// { [tag]: "obj", value: object }

// Create instance of 'value_adt'
const my_value = value_adt.str("hello") as ValueADT;

And I have created a match function (yes, this is very much inspired by Rust) for matching, and extracting associated data from the matched variant, that works like this:

match(my_value, {
    num: value => console.log(`number: ${value}`);
    str: value => console.log(`string: ${value}`);
    obj: value => console.log(`object: ${value}`);
});

The parameter typing for the provided matchers work like a charm. However, I have added the option to omit one or more matchers and replace them with a default case:

match(my_value, {
    num: value => console.log(`number: ${value}`);
    [def]: value => console.log(`not number: ${value}`);
});

I have managed to type the default matcher's parameter as the union of all the variants' value types (ValueADT["value"] in this case), but that only really makes sense if all matchers are omitted and replaced with the default matcher.

I would very much like to be able to type the value parameter of the default matcher based on which other matchers are provided, e.g. it should be string | object in the above example, not number | string | object., so my question is what (if any) advanced TypeScript sorcery is available to achieve something like that?

Here is the link to the matcher source code and types as is.

Note:
I am not sure about this question's title, suggestions are welcome.

Update:
Here is some self-contained code that illustrates the undesired behavior, i.e. that the default matcher's parameter type is a union that contains number, which it logically cannot be:

type Variant<T, U> = { tag: T, value: U };

const adt = { tag: "num", value: 1 } as
    | Variant<"num", number>
    | Variant<"str", string>
    | Variant<"obj", object>;

type MatchAll<T extends Variant<string, any>> = {
    [K in T["tag"]]: T extends Variant<K, infer V>
        ? (value: V) => any
        : never
};

const def = Symbol("[def]ault matcher");

type Matchers<T extends Variant<string, any>> =
    | MatchAll<T>
    | Partial<MatchAll<T>> & {
        [def]: (value: T["value"]) => any;
    };

function match<
    T extends Variant<string, any>,
    U extends Matchers<T>,
>(
    variant: T,
    matchers: U,
) {
    const matcher = matchers[variant.tag as keyof U];

    if (matcher === undefined) {
        throw new Error(`No match for '${variant.tag}'!`);
    }

    matcher(variant.value);
}

match(adt, {
    num: value => console.log(`number: ${value}`),
    [def]: value => console.log(`not number: ${value}`),
});

...and a playground link.

CodePudding user response:

In what follows I am concerned only with the typings, and only from the point of view of the callers of match(); the implementation may need type assertions or the like to prevent compiler errors, since complicated generic call signatures tend to be hard to verify.


My inclination here would be to overload match() so that the fully exhaustive "match all" case is handled separately from the matchers-with-default "partial" case.

For the "partial" case, we want match() to be generic not only in T, the union type of the variant argument, but also in K, the keys of the matchers argument. And we might as well make Matchers generic in both T and K too, so that we can represent the argument type for all the methods as precisely as possible.


So here is a possible definition of Matchers<T, K>:

type Matchers<T extends Variant<string, any>, K extends PropertyKey> = {
    [P in K]: (value: P extends typeof def ?
        Exclude<T, { tag: Exclude<K, typeof def> }>["value"] :
        Extract<T, { tag: P }>["value"]
    ) => any };

The idea is that we map over each element P of K to get callbacks returning any. To find the value parameter type of the callback with key P: if P is the type of def, then value corresponds to all the variants not mentioned in K (which we build using the Exclude<T, U> utility type). Otherwise, we assume P is one of the tags from T, in which case value corresponds to the value for the variant with that tag (which we build using the Extract<T, U> utility type).

Note that if K happens to be the full union of T["tag"], then the [def] callback would have a value argument of type never. This is maybe a little strange, but probably harmless. If it really matters, you could change this type so that the whole property is of type never instead of just the callback argument.


And here are our overloaded call signatures:

declare function match<T extends Variant<string, any>, K extends T["tag"] | typeof def>(
    variant: T, matchers: Matchers<T, K | typeof def>
): void;

declare function match<T extends Variant<string, any>>(
    variant: T, matchers: Matchers<T, T["tag"]>
): void;

The first signature handles the "partial" case with the def property. The inference is a little tricky here; I found that I needed to specify | typeof def both in the constraint for K, and inside the second argument to Matchers. Otherwise the compiler would tend to "give up" on inferring K from the actual keys of the matchers argument.

The second signature handles the "match all" case without the def property, and does not need to be generic in K (since it will always be just the full T["tag"] union).


Let's test it against:

declare const adt:
    | Variant<"num", number>
    | Variant<"str", string>
    | Variant<"dat", Date>;

First, let's try the "match all" case:

match(adt, {
    num: v => v.toFixed(),
    dat: v => v.toISOString(),
    str: v => v.toUpperCase()
});

Looks good. The compiler knows the types of v in each callback. Now let's leave out the str key, and add in the [def] key:

match(adt, {
    num: v => v.toFixed(),
    dat: v => v.toISOString(),
    [def]: v => v.toUpperCase()
});

Also looks good; the compiler knows that v has to be string in the default matcher. Now let's leave out the dat key as well:

match(adt, {
    num: v => v.toFixed(),
    [def]: v => typeof v === "object" ? v.toISOString() :
        v.toUpperCase()
});

Still good; the type of v is now Date | string. And finally let's have only the default matcher:

match(adt, {
    [def]: v => typeof v === "number" ? v.toFixed() :
        typeof v === "object" ? v.toISOString() :
            v.toUpperCase()
})

The type of v is the full number | Date | string union. Okay now let's try including all the tags and the default matcher:

const assertNever = (x: never): never => { throw new Error("Uh oh") };

match(adt, {
    num: v => v.toFixed(),
    dat: v => v.toISOString(),
    str: v => v.toUpperCase(),
    [def]: v => assertNever(v)
});

That is also good, I guess. The default matcher is accepted, and v is of type never (since we never expect the default matcher to be called).

Let's make mistakes and see what it says. If we leave out str and the default matcher, we get an error:

match(adt, {
    num: v => v.toFixed(),
    dat: v => v.toISOString(),
}); // error!
// No overload matches this call.
// Overload 1: Property '[def]' is missing
// Overload 2: Property 'str' is missing

The error describes how we've failed to properly call either of the two call signatures, and that either [def] or str is missing. If we misspell one of the keys:

// oops
match(adt, {
    num: v => v.toFixed(),
    dat: v => v.toISOString(),
    strr: v => v.toUpperCase(), // error, 
    //strr does not exist, Did you mean to write 'str'?
})

The error describes how it doesn't expect to see that misspelled key, and (depending on how close our spelling is) suggests the fix.


So there you go, by adding a second call signature which is generic in the matcher keys, we can get the sort of inference for the default callback argument you're looking for.

Playground link to code

  • Related