DEV Community: Susisu

Restricting Function Arguments Using Type-Level Predicates

Susisu — Sat, 03 Apr 2021 11:34:58 +0000

What are type-level predicates?

In the context of programming, a predicate usually refers to a function that returns a boolean (yes/no) value.

For example, these are predicates that are commonly used:

function isPositive(n: number): boolean {
  return n > 0;
}

function hasLength(s: string, l: string): boolean {
  return s.length === l;
}

Both of the functions take one or more arguments and return yes or no.

Type-level predicates do the same thing at the type level. Here we define them as conditional types that take one or more arguments and return true or false type.

type IsPositive<N extends number> = /* snip */ ? true : false;

type HasLength<S extends string, L extends number> = /* snip */ ? true : false;

(The implementations of these predicates are a bit complex, so let's skip for now.)

Restricting function arguments using types

As you already know, function arguments can be restricted using types.

declare function myFunc(n: number): void;

myFunc(42);    // OK
myFunc(0);     // OK
myFunc(-42);   // OK
myFunc("XXX"); // Error: "XXX" is not a number

We can also provide a subset of number. This corresponds to defining a set by enumerating its members { 1, 2, 3 }.

type MyNumber = 1 | 2 | 3;

declare function myFunc(n: MyNumber): void;

myFunc(1); // OK
myFunc(2); // OK
myFunc(3); // OK
myFunc(0); // Error: 0 is not a member of 1 | 2 | 3

But what if we want to constrain n to be a positive number? We cannot provide the set by enumeration, because it has an infinite number of members.

type Positive = 1 | 2 | 3 | ...;

Can we define Positive using the type-level predicate IsPositive<N>, like a set comprehension { n | n is a number, n > 0}?

// Can we define like this?
type Positive = (N | N extends number, IsPositive<N>);

But unfortunately, TypeScript does not provide such feature.

So simply using types to restrict arguments fails if there are an infinite number of (or too many) acceptable values, and we need another way for such case.

Restricting function arguments using type-level predicates

Here is the answer for the problem (playground):

type Positive<N extends number> = IsPositive<N> extends true ? N : never;

declare function myFunc<N extends number>(n: Positive<N>): void;

How does this work? Let's take a look.

When we call the function, for instance myFunc(42), the compiler first tries to infer the type parameter N from the argument 42. In this case, it knows that the conditional type Positive<N> returns N | never = N whatever N is, and successfully infers N = 42.

(Note that N has an upper bound number, so widening (inferring N as N = number) does not occur.)

Next, Positive<N> is computed using the inferred N. Clearly N = 42 is a positive number, so Positive<N> = N = 42.

Finally, the compiler checks whether the argument 42 satisfies the type Positive<N>. As seen above, Positive<N> is 42, and it passes the typecheck.

myFunc(42); // OK

When we call the function with a negative number, like myFunc(-42), the type parameter N is inferred as N = -42, and Positive<N> = never.
The argument -42 is not a member of never, of course, and it is rejected.

myFunc(-42); // Error

The downside of this technique is that the type error is not very helpful. In the above case, the error message is Argument of type 'number' is not assignable to parameter of type 'never'., which does not contain what constraint was not satisfied nor what to do to fix the error. Maybe throw types can be a solution for this?

Appendix

The type-level predicates IsPositive<N> and HasLength<S, L> can be implemented like these:

type IsPositive<N extends number> =
    number extends N ? boolean
  : N extends unknown ? (
      N extends 0 ? false
    : `${N}` extends `-${infer _}`? false
    : true
  )
  : never;

type HasLength<S extends string, L extends number> = Length<S> extends L ? true : false;

type Length<S extends string> =
    string extends S ? number
  : S extends unknown ? _Length<S>
  : never;

type _Length<S extends string, C extends unknown[] = []> =
    S extends "" ? C["length"]
  : S extends `${infer _}${infer R}` ? _Length<R, [...C, unknown]>
  : never;

How to Create Deep Recursive Types

Susisu — Fri, 20 Nov 2020 04:53:46 +0000

TypeScript 4.1, released today, comes with an important change: official support for recursive conditional types. This allows us to define recursive types easily, and I expect using recursive types will become much more common than before.

For example, you can define a type Repeat<T, N> that makes a tuple type of length N filled with T as follows.

type Repeat<T, N extends number> = _Repeat<T, N, []>;
type _Repeat<T, N extends number, A extends T[]> =
  A["length"] extends N
    ? A
    : _Repeat<T, N, [T, ...A]>;

// XS = ["x", "x", "x", "x", "x"]
type XS = Repeat<"x", 5>;

While it's easy to define, the TypeScript compiler has a tight limit on type instantiation depth (almost equal to the number of recursions here). So if N gets lager, Repeat<T, N> cannot be instantiated.

// Wanted: XS = ["x", ..., "x"] and XS["length"] = 100
// Actual: error (Type instantiation is excessively deep or possibly infinite.)
type XS = Repeat<"x", 100>;

As of TypeScript 4.1, the instantiation depth limit is 50. Perhaps this will not be a problem in common situations, but some people might think this is too strict.

When I implemented a type level Brainfuck interpreter, I faced this limitation. Because every execution step requires some instantiation of types, my interpreter couldn't execute even simple programs like "Hello, world!".

Eventually, I found that we can defer the limit, and types that have over 1,000 recursions can be instantiated. In this post, I'll introduce you how to defer the limit and how it works.

Step 1. Put recursive instantiation into an object property

Even before TypeScript 4.1, some sort of recursive type definitions are supported and used. A notable one is that, since TypeScript 3.7, type definitions that recursively referencing themselves are allowed if the references are in object properties or array elements.

Here is the key of Step 1: types in object properties or array elements will not be immediately instantiated, but their instantiations are deferred. Because of this, by putting recusvie type references into object properties, we can avoid the instantiation depth limit.

(Actually I don't know how the TypeScript compiler exactly works. Please tell me if my understanding is wrong.)

So let's change the definition of _Repeat<T, N, A>, the subroutine of Repeat<T, N>.

type _Repeat<T, N extends number, A extends T[]> =
  A["length"] extends N
    ? A
    : { __rec: _Repeat<T, N, [T, ...A]> }; // recurse in an object property

By this change, the tuple type that we want is now wrapped by a deeply nested object type.

// T0 = { __rec: { __rec: { __rec: { __rec: ["x", "x", "x", "x"] } } } }
type T0 = _Repeat<"x", 4, []>;

In exchange for this, we can instantiate it even if N is large.

// No errors
type T = _Repeat<"x", 100, []>;

Next, we want to peel this deeply nested object type to retrieve the tuple type. However, a naïve implementation will require N recursions, which means it will hit the limit there. So we have to use another trick.

Step 2. Peel nested object type in a logarithmic order

The answer is the following.

type _Recurse<T> =
    T extends { __rec: never } ? never
  : T extends { __rec: { __rec: infer U } } ? { __rec: _Recurse<U> }
  : T extends { __rec: infer U } ? U
  : T;

This can halve the number of nests in just one step.

// T0 = { __rec: { __rec: { __rec: { __rec: ["x", "x", "x", "x"] } } } }
type T0 = _Repeat<"x", 4, []>;
// T1 = { __rec: { __rec: ["x", "x", "x", "x"] } }
type T1 = _Recurse<T0>;
// T2 = { __rec: ["x", "x", "x", "x"] }
type T2 = _Recurse<T1>;
// T3 = ["x", "x", "x", "x"]
type T3 = _Recurse<T2>;

The third line of the definition of _Recurse<T> is the key: it squashes two __recs into one __rec, and do the same operation on the child recursively. Because this recursive operation is done in an object property as Step 1, the instantiation depth limit is not applied.

Recurse<T> can be defined to repeat the above operation. Because each step halves the number of nests, it only requires about log_2 N steps to peel all N nests.

type Recurse<T> =
  T extends { __rec: unknown }
    ? Recurse<_Recurse<T>>
    : T;

(Note that the number of steps here is not the same as the instantiation depth that the TypeScript compiler limits. It seems one step costs more than one instantiation depth for some reason.)

Now we are ready! Let's define the improved version of Repeat<T, N>, and check it works for larger N.

type Repeat<T, N extends number> = Recurse<_Repeat<T, N, []>>;

// XS = ["x", ..., "x"] and XS["length"] = 100
type XS = Repeat<"x", 100>;

🎉

You can try the code here.