Improve composability of tuple schemas

[kanwren]

It would be nice to be able to concatenate two (and by extension, any list of, under concatenation and anEmptyList) tuple schemas. It would also be nice to be able to use an array schema like a varargs, and be able to compose a tuple and array schema to represent a tuple followed by zero or more elements of a certain type.

[kanwren]

26223 says that this is currently impossible

[kanwren]

It is currently possible to append a generic tuple onto a known tuple by taking advantage of function rest parameters:

type Foo = [number, string];

// error
type Bar = [boolean, ...Foo];
// okay
type Baz = Parameters<(x: boolean, ...rest: Foo) => void>;

I doubt this helps, but it's pretty neat.

[kanwren]

I found a way, but it's somewhat dangerous.

Firstly, we can take advantage of the above type to define a Cons operator:

type Cons<A, T extends any[]> = Parameters<(head: A, ...tail: T) => any>;

Next, we need to define a conditional construct, of the form IfCond<Arg, Y, N> = ..., which will check the condition on the argument and evaluate to Y if it holds and N otherwise. For convenience, we can assign default values, and use the compiler to check conditions for us:

type IsZero<T extends number, Y=unknown, N=never> = T extends 0 ? Y : N;

const x: IsZero<0> = "dummy"; // compiles
const y: IsZero<1> = "dummy"; // Type "dummy" is not assignable to type 'never'

Using this, we can define some predicates:

type IfEmpty<T extends any[], Y=unknown, N=never> =
    T extends [] ? Y : N;

type IfFinite<T extends any[], Y=unknown, N=never> =
    IfEmpty<
        T,
        Y,
        T extends (infer S)[]
          ? S[] extends T
              ? N
              : Y
          : never
    >;

Note that we can use the technique from before to "pattern match" on a tuple to see if it is empty or not, by asking if (...args: T) => any extends (head: infer Head, ...tail: infer Tail) => any ? ... : .... Since we have a way to destructure tuples, and a way to prepend elements to them, we have the necessary primitives to treat tuples as cons lists. To concatenate two cons lists:

concat :: [a] -> [a] -> [a]
concat []     ys = ys
concat (x:xs) ys = x : concat xs ys

We also have to account for the case when our first tuple is actually an infinite array in order for the type to terminate. Now, we can translate into a Concat type by using recursion:

type Append<T extends any[], S extends any[]> =
    IfFinite<
        T,
        // If finite, proceed as normal
        ((...args: T) => any) extends ((head: infer Head, ...tail: infer Tail) => any)
            // Recurse if T has a head and tail
            ? Cons<Head, Append<Tail, S>>
            // Otherwise, T is empty, return the second tuple
            : S,
        // If infinite, the result is the first type
        T
    >

However, the compiler does not technically support recursive types like this, and it's likely that they could break in the future. Since this is still experimental, though, I may add something like this in anyway.

[kanwren]

Yeah, the compiler does not appropriately support this, and will actively disallow this recursion. I'll see if there's a way to get around this, but it just seems impossible for now.

Furthermore, when appending two tuples, there is no way to strongly type the length of the result, which is also a problem.

[kanwren]

Well, there is another hack that can be used to get around the limit on self-referential recursive types: using index types.

// The first type in the tuple, or 'never' if it does not exist
type Head<T extends any[]> = T extends [infer Head, ...any[]] ? Head : never;

// All elements after the head in the tuple, or 'never' if it does not exist
type Tail<T extends any[]> =
    ((...args: T) => any) extends ((head: any, ...tail: infer Tail) => any) ? Tail : never;

// The last type in the tuple, or 'never' if it does not exist
type Last<T extends any[]> = {
    0: Last<Tail<T>>;
    1: Head<T>;
}[T extends ([] | [any]) ? 1 : 0];

[kanwren]

Furthermore, only simple recursion is allowed in the above hack; you may use an accumulator, but you may not use the result of a recursion. That is, recursive type constructions must be tail recursive.

For example, the following type will not work:

// Can't recurse directly
type Snoc<A, T extends any[]> =
    T extends []
        ? [A]
        : T extends [any]
            ? [Head<T>, A]
            : Cons<Head<T>, Snoc<A, Tail<T>>>;

// Also doesn't work
type Snoc<A, T extends any[], Suffix extends any[] = []> =
    T extends []
        ? Cons<A, Suffix>
        : T extends [any]
            ? Cons<Head<T>, Cons<A, Suffix>>
            : Snoc<A, Tail<T>, Cons<Head<T>, Suffix>>;

// Not direct recursion, but not tail recursive:
type Snoc<A, T extends any[]> = {
    0: [A];
    1: Cons<Head<T>, Snoc<A, Tail<T>>>;
    2: [Head<T>, A];
}[IfEmpty<T, 0, IfHasTail<T, 1, 2>>];

// Works!
type Snoc<A, T extends any[], Suffix extends any[] = []> = {
    0: Cons<A, Suffix>;
    1: Snoc<A, Tail<T>, Cons<Head<T>, Suffix>>;
    2: Cons<Head<T>, Cons<A, Suffix>>;
}[IfEmpty<T, 0, IfHasTail<T, 1, 2>>];

[kanwren]

Now, we need a tail-recursive implementation of append with an accumulator. To do this, we reverse the input list, and then reverse it again, but onto the second list:

append :: [a] -> [a] -> [a]
append xs ys = go (reverse xs) ys
  where
    go (x:xs) acc = go xs (x:acc)
    go [] acc     = acc

Then, we just need to define a type Reverse<T extends any[], Suffix extends any[] = []> using the above methods, and Append should follow naturally.

[kanwren]

Finally, with some additional handling for finiteness:

type Reverse<T extends any[], Suffix extends any[] = []> = {
    0: Suffix;
    1: Reverse<Tail<T>, Cons<Head<T>, Suffix>>;
    2: Cons<Head<T>, Suffix>;
    3: T;
}[IfEmpty<T, 0, IfFinite<T, IfHasTail<T, 1, 2>, 3>>];

type Append<T extends any[], S extends any[]> = {
    0: S;
    1: Reverse<Reverse<T>, S>;
    2: Cons<Head<T>, S>;
    3: never;
}[IfEmpty<T, 0, IfFinite<T, IfHasTail<T, 1, 2>, 3>>];

[kanwren]

Note that it's possible to allow for Append<T, S> to be T if it is an infinite array type, but this could be surprising to anyone expecting it to be one or more elements of type T extends (infer E)[] ? E : never followed by S.

[kanwren]

Looking back, this can't be done nicely without some form of value-level inference, to map from a tuple type to its length. For example, Haskell uses typeclasses for this, and while you could do it in TypeScript, you would not be able to infer the correct instances, and would end up manually passing the equivalent of a successor-encoded natural number.