Define a recursive array of even length in TypeScript

Question

I'm trying to write a TypeScript type declaration for a subset of Mapbox style expressions, a Lisp-like language built on JSON. For example:

["+", 1, ["*", 2, 2], 3]
= 8

One of the operators is "case", which lets you write conditional expressions:

["case", true, "yes", "no"]
= "yes"

This takes pairs of booleans and values, plus a fallback value (see docs).

Is there any way to model "an array of even length" in TypeScript, particularly one whose elements might recursively reference themselves? Here's an attempt:

type Expression = number | string | boolean | CallExpression;

type CallExpression = MathCall | CaseCall;

type MathCall = [
  '+' | '-' | '/' | '*' | '>' | '<',
  Expression,
  Expression,
];

type CaseCallBase = [
  'case',
  Expression,
  ...CaseCallParams,
];

type CaseCallParams = [
  // ~~~~~~~~~~~~~~ Type alias 'CaseCallParams' circularly references itself. (2456)
  Expression,
  Expression,
  ...([] | CaseCallParams)
];

I'm aware that there are ways to define a tuple of length N in TypeScript, but I haven't been able to avoid the circular reference error with these.

This is the closest I've come with an interface, though you have to spell out all the fields and cap it at a certain length. Defining an array with an interface feels awkward and leads to confusing errors, but I haven't found any alternatives.

type Expression = number | string | boolean | CallExpression;

type CallExpression = MathCall | CaseCall;

type MathCall = [
  '+' | '-' | '/' | '*' | '>' | '<',
  Expression,
  Expression,
];

interface CaseCall {
  0: 'case';
  1: Expression;
  2: Expression;
  3: Expression;
  4?: Expression;
  5?: Expression;
  6?: Expression;
  7?: Expression;
  // etc.
  length: 4 | 6 | 8 | 10 | 12; // ...
}

Is it possible to define this type more accurately and without the length cap?

Answer 1

I was able to generate a union of 55 tuples with maximum length - 110 elements. It means tuples with next length:

110 | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 | 22 | 24 | 26 | 28 | 30 | 32 | 34 | 36 | 38 | 40 | 42 | 44 | 46 | 48 | 50 | 52 | 54 | 56 | 58 | 60 | 62 | 64 | 66 | 68 | 70 | 72 | 74 | 76 | 78 | 80 | ... 13 more ... | 108

There is a limit up to 110 elements in the tuple

type MathCall = [
    '+' | '-' | '/' | '*' | '>' | '<',
    Expression,
    Expression,
];
type Expression = number | string | boolean | MathCall;


type CallParams = [Expression, Expression]

/**
 * It is not allowed to increase this number, at least in TS.4.4
 */
type MAXIMUM_ALLOWED_BOUNDARY = 110

type Mapped<
    Arr extends Array<unknown>,
    Result extends Array<unknown> = [],
    Original extends any[] = [],
    Count extends ReadonlyArray<number> = []
    > =
    (Count['length'] extends MAXIMUM_ALLOWED_BOUNDARY
        ? Result
        : (Arr extends []
            ? []
            : (Arr extends [infer H]
                ? [...Result, H, ...([] | Mapped<Original, [], [], [...Count, 1]>)]
                : (Arr extends [infer Head, ...infer Tail]
                    ? Mapped<[...Tail], [...Result, Head], Arr, [...Count, 1]>
                    : Readonly<Result>
                    )
            )
        )
    )

// Main result
type CaseCallParams = Mapped<CallParams>

// TESTS

// credits goes to https://stackoverflow.com/a/50375286
type UnionToIntersection<U> = (U extends any ? (k: U) => void : never) extends (
    k: infer I
) => void
    ? I
    : never;

// credits goes to https://github.com/microsoft/TypeScript/issues/13298#issuecomment-468114901
type UnionToOvlds<U> = UnionToIntersection<
    U extends any ? (f: U) => void : never
>;

type PopUnion<U> = UnionToOvlds<U> extends (a: infer A) => void ? A : never;

type IsUnion<T> = [T] extends [UnionToIntersection<T>] ? false : true;

type UnionToArray<T, A extends unknown[] = []> = IsUnion<T> extends true
    ? UnionToArray<Exclude<T, PopUnion<T>>, [PopUnion<T>, ...A]>
    : [T, ...A];

type Result = UnionToArray<CaseCallParams>[3]['length']; // 8
type Result_ = UnionToArray<CaseCallParams>[4]['length']; // 10
type Result__ = UnionToArray<CaseCallParams>[10]['length']; // 12
type Result___ = UnionToArray<CaseCallParams>[12]['length']; // 26
type Result____ = UnionToArray<CaseCallParams>[20]['length']; // 42
type Result_____ = UnionToArray<CaseCallParams>[50]['length']; // 102
type Result______ = UnionToArray<CaseCallParams>[54]['length']; // 110

// should end with 0 , 2 , 4 , 6 , 8
type EvenNumbers = UnionToArray<CaseCallParams>[number]['length']

Please let me know if it works for you.

Playground

I think it will be possible to increase the limit after Tail recursive evaluation of conditional types will be merged

ALso , you can define a function which will validate the length of the tuple:

type EvenEnd = '0' | '2' | '4' | '6' | '8'

type IsEven<T extends `${number}`> =
    (T extends `${infer Int}${infer Rest}`
        ? (
            Rest extends ''
            ? (Int extends EvenEnd
                ? true
                : false
            )
            : (Rest extends `${number}`
                ? IsEven<Rest>
                : false
            )
        )
        : false
    )

{
    type Test1 = IsEven<'80'> // true
    type Test2 = IsEven<'9010'> // true
    type Test3 = IsEven<'1'> // false
    type Test4 = IsEven<'99999999'> // false
}

type EvenLength<T extends Expression[]> =
    IsEven<`${T['length']}`> extends true
    ? T
    : never

const evenTuple = <
    T extends Expression,
    Tuple extends T[]
>(tuple: EvenLength<[...Tuple]>) => tuple

evenTuple([1, 3]) // ok
evenTuple([1, 3, 4]) // error

Playground 2

My article

UPDATE

Another one solution, which allows you to create a tuple with 999 elements.

type Expression = number | string | boolean | CallExpression;

type CallExpression = MathCall | CaseCall;

type MathCall = [
    '+' | '-' | '/' | '*' | '>' | '<',
    Expression,
    Expression,
];

type MAXIMUM_ALLOWED_BOUNDARY = 999

type Mapped<
    N extends number,
    Result extends Array<unknown> = [],
    > =
    (Result['length'] extends N
        ? Result
        : Mapped<N, [...Result, Result['length']]>
    )

// 0 , 1, 2 ... 998
type NumberRange = Mapped<MAXIMUM_ALLOWED_BOUNDARY>[number]


type Dictionary = {
    [Prop in NumberRange as `${Prop}`]: Prop
}

type EvenEnd = '0' | '2' | '4' | '6' | '8'

type IsEven<T extends `${number}`> =
    (T extends `${infer Int}${infer Rest}`
        ? (
            Rest extends ''
            ? (Int extends EvenEnd
                ? true
                : false
            )
            : (Rest extends `${number}`
                ? IsEven<Rest>
                : false
            )
        )
        : false
    )

type Compare<Num extends number> =
    Num extends number
    ? IsEven<`${Num}`> extends true
    ? Num
    : never
    : never

type EvenRange = Exclude<Compare<NumberRange>, 0>

type CaseCall<Exp = any> = {
    [Prop in Exclude<NumberRange, 0>]?: Exp
} & { length: EvenRange }

const tuple: CaseCall<Expression> = [1, 1, 1, 1] as const // ok
const tuple2: CaseCall<Expression> = [1, 1, 1] as const // expected error


const handle = <
    Exp extends Expression, Data extends Exp[]
>(
    arg: [...Data],
    ...check: [...Data]['length'] extends EvenRange ? [] : [never]
) => arg

handle([1, 1, 1]) // expected error
handle([1, 1]) // ok

Playground

UPDATE 2

Easier approach to create union of tuples with even length:

type MAXIMUM_ALLOWED_BOUNDARY = 50

type Mapped<
    Tuple extends Array<unknown>,
    Result extends Array<unknown> = [],
    Count extends ReadonlyArray<number> = []
    > =
    (Count['length'] extends MAXIMUM_ALLOWED_BOUNDARY
        ? Result
        : (Tuple extends []
            ? []
            : (Result extends []
                ? Mapped<Tuple, Tuple, [...Count, 1]>
                : Mapped<Tuple, Result | [...Result, ...Tuple], [...Count, 1]>)
        )
    )



type Result = Mapped<[string, number]>

// 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 | 22 | 24
type Test = Result['length']

Playground