Skip to content

Instantly share code, notes, and snippets.

@raganwald
Last active July 24, 2025 15:21
Show Gist options
  • Save raganwald/24d3334d6749987557ca4190023466b9 to your computer and use it in GitHub Desktop.
Save raganwald/24d3334d6749987557ca4190023466b9 to your computer and use it in GitHub Desktop.
Proof-of-concept of working around type-level TypeScript's 1,000 invocation limit on tail-recursive types
// --------- Utilities ---------
type Expect<T extends true> = T;
type Equal<X, Y> = (<T>() => T extends X ? 1 : 2) extends <T>() => T extends Y ? 1 : 2
? true
: false;
type Extends<A, B> = A extends B ? true : false;
type IsNever<T> = Extends<[T], [never]>;
type IsFalse<T> = T extends false ? true : false;
type FAIL = { type: "FAIL" };
type Fail<M extends string> = FAIL & { message: M };
type IsFail<T> = [T] extends [FAIL] ? true : false;
type RepeatTenTimes<S extends string> = `${S}${S}${S}${S}${S}${S}${S}${S}${S}${S}`;
// ---------- Foundational Types ----------
type BlankOr<T> = "" | T;
type Digit = `${0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9}`;
type StartsWithDigit = `${Digit}${string}`; // can start with a zero
type WholeNumber = `${bigint}` & StartsWithDigit; // cannot start with a zero, all numbers
namespace TestWholeNumber {
type _0 = Expect<IsFalse<Extends<"", WholeNumber>>>;
type _1 = Expect<IsFalse<Extends<"QWERTY", WholeNumber>>>;
type _6 = Expect<Extends<"6", WholeNumber>>;
type _42 = Expect<Extends<"42", WholeNumber>>;
type _HUGE = Expect<Extends<"900719925474099190071992547409919007199254740991", WholeNumber>>;
}
type AsWholeNumber<T extends string> =
`${T}` extends infer WholeNumberT extends WholeNumber
? WholeNumberT
: never;
// ---------- Jackson's Widowbird ----------
type DepthLimit = 100;
type DepthZero = [];
type Depth = unknown[];
type Deeper<T extends Depth> = [...T, unknown];
type IsDepthAtLimit<T extends Depth> = T["length"] extends DepthLimit ? true : false;
type BasicReturnToTop = { type: "ReturnToTop", parameters: any[] };
type ReturnToTopWith<Params extends any[]> = { type: "ReturnToTop", parameters: Params };
// ---------- Operations on Foundational Types ----------
type SplitLastDigit<N extends WholeNumber> = SplitLastDigitTop<N, "">;
type SplitLastDigitTop<N extends StartsWithDigit, ButLast extends BlankOr<WholeNumber>> =
SplitLastDigitImpl<N, ButLast, DepthZero> extends infer ReturnValue
? ReturnValue extends { type: "ReturnToTop", parameters: [infer N2 extends StartsWithDigit, infer ButLast2 extends BlankOr<WholeNumber>] }
? SplitLastDigitTop<N2, ButLast2>
: ReturnValue
: never;
type SplitLastDigitImpl<N extends StartsWithDigit, ButLast extends BlankOr<WholeNumber>, D extends unknown[]> =
N extends Digit
? [ButLast, N]
: N extends `${infer First extends Digit}${infer ButFirst extends StartsWithDigit}`
? IsDepthAtLimit<D> extends true
? ReturnToTopWith<[N, ButLast]>
: SplitLastDigitImpl<ButFirst, AsWholeNumber<`${ButLast}${First}`>, Deeper<D>>
: never;
namespace TestSplitLastDigit {
type TenThousandCharNumber = RepeatTenTimes<RepeatTenTimes<RepeatTenTimes<"1234567890">>>;
type TenThousandAndOneCharNumber = `${TenThousandCharNumber}6`;
type _TestTenThousandAndOne = Expect<Equal<[TenThousandCharNumber, "6"], SplitLastDigit<TenThousandAndOneCharNumber>>>;
}
// --------- Utilities ---------
type Expect<T extends true> = T;
type Equal<X, Y> = (<T>() => T extends X ? 1 : 2) extends <T>() => T extends Y ? 1 : 2
? true
: false;
type Extends<A, B> = A extends B ? true : false;
type IsNever<T> = Extends<[T], [never]>;
type IsFalse<T> = T extends false ? true : false;
type Assume<T, U> = T extends U ? T : U;
type FAIL = { type: "FAIL" };
type Fail<M extends string> = FAIL & { message: M };
type IsFail<T> = [T] extends [FAIL] ? true : false;
type RepeatTenTimes<S extends string> = `${S}${S}${S}${S}${S}${S}${S}${S}${S}${S}`;
// ---------- Foundational Types ----------
type BlankOr<T> = "" | T;
type Digit = `${0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9}`;
type StartsWithDigit = `${Digit}${string}`; // can start with a zero
type WholeNumber = `${bigint}` & StartsWithDigit; // cannot start with a zero, all numbers
namespace TestWholeNumber {
type _0 = Expect<IsFalse<Extends<"", WholeNumber>>>;
type _1 = Expect<IsFalse<Extends<"QWERTY", WholeNumber>>>;
type _6 = Expect<Extends<"6", WholeNumber>>;
type _42 = Expect<Extends<"42", WholeNumber>>;
type _HUGE = Expect<Extends<"900719925474099190071992547409919007199254740991", WholeNumber>>;
}
type AsWholeNumber<T extends string> =
`${T}` extends infer WholeNumberT extends WholeNumber
? WholeNumberT
: never;
// ---------- Higher Kinded Types ----------
//
// See: https://code.lol/post/programming/higher-kinded-types/$0
//
type GenericFunction = (..._: never[]) => unknown;
abstract class HKT {
readonly _1?: unknown;
readonly _2?: unknown;
readonly _3?: unknown;
readonly _4?: unknown;
new?: GenericFunction;
}
// quite the hack
type Apply<F extends HKT, _1, _2 extends any = never, _3 extends any = never, _4 extends any = never> = ReturnType<
(F &
{
readonly _1: _1;
readonly _2: _2;
readonly _3: _3;
readonly _4: _4;
}) extends infer G extends { new: GenericFunction } ? G["new"] : never
>;
// ---------- Jackson's Widowbird ----------
//
// This preliminary version relies on the recursive type incorporating the
// "widowbird" behaviour of jumping back up to the top inline with the
// "business logic" of the recursive type itself.
//
// Non-trivial to-do:
//
// 1. Refactor to use an equivalent of the M combinator instead of hard-coding
// a self-referential type, and;
// 2. Writing "top" such that it can encode all this logic into a decorated
// "myself" that manages depth and knows when to go ack to the top.
type DepthLimit = RepeatTenTimes<RepeatTenTimes<".">>;
type DepthZero = "";
type Depth = string;
type Deeper<T extends Depth> = `${T}.`;
type IsDepthAtLimit<T extends Depth> = Extends<T, DepthLimit>;
type BasicReturnToTop = { type: "ReturnToTop", parameters: any[] };
type ReturnToTopWith<Params extends any[]> = { type: "ReturnToTop", parameters: Params };
// ---------- Operations on Foundational Types ----------
type SplitLastDigit<N extends WholeNumber> = SplitLastDigitTop<N, "">;
type SplitLastDigitTop<N extends StartsWithDigit, ButLast extends BlankOr<WholeNumber>> =
Apply<SplitLastDigitHKT, N, ButLast, DepthZero> extends infer ReturnValue
? ReturnValue extends { type: "ReturnToTop", parameters: [infer N2 extends StartsWithDigit, infer ButLast2 extends BlankOr<WholeNumber>] }
? SplitLastDigitTop<N2, ButLast2>
: ReturnValue
: never;
// ---------- Wrapping SplitLastDigitImpl into an HKT ----------
interface SplitLastDigitHKT extends HKT {
new: (_N: Assume<this["_1"], StartsWithDigit>, _ButLast: Assume<this["_2"], BlankOr<WholeNumber>>, _D: Assume<this["_3"], Depth>) =>
[typeof _N, typeof _ButLast, typeof _D] extends [infer N, infer ButLast extends BlankOr<WholeNumber>, infer D extends Depth]
? IsDepthAtLimit<D> extends true
? ReturnToTopWith<[N, ButLast]>
: N extends Digit
? [ButLast, N]
: N extends `${infer First extends Digit}${infer ButFirst extends StartsWithDigit}`
? Apply<SplitLastDigitHKT, ButFirst, AsWholeNumber<`${ButLast}${First}`>, Deeper<D>>
: never
: never;
}
namespace TestSplitLastDigit {
// @ts-expect-error does not start with a digit
type _0 = SplitLastDigit<"">;
type _1 = Expect<Equal<["", "1"], SplitLastDigit<"1">>>;
type _2 = Expect<Equal<["1", "2"], SplitLastDigit<"12">>>;
type _3 = Expect<Equal<["12", "3"], SplitLastDigit<"123">>>;
type TenThousandCharNumber = RepeatTenTimes<RepeatTenTimes<RepeatTenTimes<"1234567890">>>;
type TenThousandAndOneCharNumber = `${TenThousandCharNumber}6`;
type _TestTenThousandAndOne = Expect<Equal<[TenThousandCharNumber, "6"], SplitLastDigit<TenThousandAndOneCharNumber>>>;
}
// --------- Utilities ---------
type Expect<T extends true> = T;
type Equal<X, Y> = (<T>() => T extends X ? 1 : 2) extends <T>() => T extends Y ? 1 : 2
? true
: false;
type Extends<A, B> = A extends B ? true : false;
type IsNever<T> = Extends<[T], [never]>;
type IsFalse<T> = T extends false ? true : false;
type Assume<T, U> = T extends U ? T : U;
type FAIL = { type: "FAIL" };
type Fail<M extends string> = FAIL & { message: M };
type IsFail<T> = [T] extends [FAIL] ? true : false;
type RepeatTenTimes<S extends string> = `${S}${S}${S}${S}${S}${S}${S}${S}${S}${S}`;
// ---------- Foundational Types ----------
type BlankOr<T> = "" | T;
type Digit = `${0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9}`;
type StartsWithDigit = `${Digit}${string}`; // can start with a zero
type WholeNumber = `${bigint}` & StartsWithDigit; // cannot start with a zero, all numbers
namespace TestWholeNumber {
type _0 = Expect<IsFalse<Extends<"", WholeNumber>>>;
type _1 = Expect<IsFalse<Extends<"QWERTY", WholeNumber>>>;
type _6 = Expect<Extends<"6", WholeNumber>>;
type _42 = Expect<Extends<"42", WholeNumber>>;
type _HUGE = Expect<Extends<"900719925474099190071992547409919007199254740991", WholeNumber>>;
}
type AsWholeNumber<T extends string> =
`${T}` extends infer WholeNumberT extends WholeNumber
? WholeNumberT
: never;
// ---------- Higher Kinded Types ----------
//
// See: https://code.lol/post/programming/higher-kinded-types/$0
//
type GenericFunction = (..._: never[]) => unknown;
abstract class HKT {
readonly _1?: unknown;
readonly _2?: unknown;
readonly _3?: unknown;
readonly _4?: unknown;
new?: GenericFunction;
}
// quite the hack
type Apply<F extends HKT, _1, _2 extends any = never, _3 extends any = never, _4 extends any = never> = ReturnType<
(F &
{
readonly _1: _1;
readonly _2: _2;
readonly _3: _3;
readonly _4: _4;
}) extends infer G extends { new: GenericFunction } ? G["new"] : never
>;
// ---------- Jackson's Widowbird ----------
//
// This preliminary version relies on the recursive type incorporating the
// "widowbird" behaviour of jumping back up to the top inline with the
// "business logic" of the recursive type itself.
//
// Non-trivial to-do:
//
// 1. Refactor to use an equivalent of the M combinator instead of hard-coding
// a self-referential type, and;
// 2. Writing "top" such that it can encode all this logic into a decorated
// "myself" that manages depth and knows when to go ack to the top.
type DepthLimit = RepeatTenTimes<RepeatTenTimes<".">>;
type DepthZero = "";
type Depth = string;
type Deeper<T extends Depth> = `${T}.`;
type IsDepthAtLimit<T extends Depth> = Extends<T, DepthLimit>;
type BasicReturnToTop = { type: "ReturnToTop", parameters: any[] };
type ReturnToTopWith<Params extends any[]> = { type: "ReturnToTop", parameters: Params };
// ---------- Operations on Foundational Types ----------
type SplitLastDigit<N extends WholeNumber> = SplitLastDigitTop<N, "">;
type SplitLastDigitTop<N extends StartsWithDigit, ButLast extends BlankOr<WholeNumber>> =
Apply<SplitLastDigitHKT, SplitLastDigitHKT, N, ButLast, DepthZero> extends infer ReturnValue
? ReturnValue extends { type: "ReturnToTop", parameters: [infer N2 extends StartsWithDigit, infer ButLast2 extends BlankOr<WholeNumber>] }
? SplitLastDigitTop<N2, ButLast2>
: ReturnValue
: never;
interface SplitLastDigitHKT extends HKT {
new: (
_Myself: Assume<this["_1"], HKT>, _N: Assume<this["_2"], StartsWithDigit>, _ButLast: Assume<this["_3"], BlankOr<WholeNumber>>, _D: Assume<this["_4"], Depth>
) =>
[
typeof _Myself, typeof _N, typeof _ButLast, typeof _D
] extends [
infer Myself extends HKT, infer N, infer ButLast extends BlankOr<WholeNumber>, infer D extends Depth
]
? N extends Digit
? [ButLast, N]
: N extends `${infer First extends Digit}${infer ButFirst extends StartsWithDigit}`
? IsDepthAtLimit<D> extends true
? ReturnToTopWith<[N, ButLast]>
: Apply<SplitLastDigitHKT, SplitLastDigitHKT, ButFirst, AsWholeNumber<`${ButLast}${First}`>, Deeper<D>>
: never
: never;
}
namespace TestSplitLastDigit {
// @ts-expect-error does not start with a digit
type _0 = SplitLastDigit<"">;
type _1 = Expect<Equal<["", "1"], SplitLastDigit<"1">>>;
type _2 = Expect<Equal<["1", "2"], SplitLastDigit<"12">>>;
type _3 = Expect<Equal<["12", "3"], SplitLastDigit<"123">>>;
type TenThousandCharNumber = RepeatTenTimes<RepeatTenTimes<RepeatTenTimes<"1234567890">>>;
type TenThousandAndOneCharNumber = `${TenThousandCharNumber}6`;
type _TestTenThousandAndOne = Expect<Equal<[TenThousandCharNumber, "6"], SplitLastDigit<TenThousandAndOneCharNumber>>>;
}
// --------- Utilities ---------
type Expect<T extends true> = T;
type Equal<X, Y> = (<T>() => T extends X ? 1 : 2) extends <T>() => T extends Y ? 1 : 2
? true
: false;
type Extends<A, B> = A extends B ? true : false;
type IsNever<T> = Extends<[T], [never]>;
type IsFalse<T> = T extends false ? true : false;
type Assume<T, U> = T extends U ? T : U;
type FAIL = { type: "FAIL" };
type Fail<M extends string> = FAIL & { message: M };
type IsFail<T> = [T] extends [FAIL] ? true : false;
// ---------- Counting small(!) numbers with strings
type RepeatTenTimes<S extends string> = `${S}${S}${S}${S}${S}${S}${S}${S}${S}${S}`;
// ---------- Foundational Types ----------
type BlankOr<T> = "" | T;
type Digit = `${0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9}`;
type StartsWithDigit = `${Digit}${string}`; // can start with a zero
type WholeNumber = `${bigint}` & StartsWithDigit; // cannot start with a zero, all numbers
namespace TestWholeNumber {
type _0 = Expect<IsFalse<Extends<"", WholeNumber>>>;
type _1 = Expect<IsFalse<Extends<"QWERTY", WholeNumber>>>;
type _6 = Expect<Extends<"6", WholeNumber>>;
type _42 = Expect<Extends<"42", WholeNumber>>;
type _HUGE = Expect<Extends<"900719925474099190071992547409919007199254740991", WholeNumber>>;
}
type AsWholeNumber<T extends string> =
`${T}` extends infer WholeNumberT extends WholeNumber
? WholeNumberT
: never;
// ---------- Higher Kinded Types ----------
//
// See: https://code.lol/post/programming/higher-kinded-types/$0
//
type GenericFunction = (..._: never[]) => unknown;
abstract class HKT {
readonly _1?: unknown;
readonly _2?: unknown;
readonly _3?: unknown;
readonly _4?: unknown;
new?: GenericFunction;
}
// quite the hack
type Apply<F extends HKT, _1, _2 extends any = never, _3 extends any = never, _4 extends any = never> = ReturnType<
(F &
{
readonly _1: _1;
readonly _2: _2;
readonly _3: _3;
readonly _4: _4;
}) extends infer G extends { new: GenericFunction } ? G["new"] : never
>;
// ---------- Jackson's Widowbird ----------
//
// This preliminary version relies on the recursive type incorporating the
// "widowbird" behaviour of jumping back up to the top inline with the
// "business logic" of the recursive type itself.
//
// Non-trivial to-do:
//
// 1. Refactor to use an equivalent of the M combinator instead of hard-coding
// a self-referential type, and;
// 2. Writing "top" such that it can encode all this logic into a decorated
// "myself" that manages depth and knows when to go ack to the top.
type DepthLimit = RepeatTenTimes<".........">;
type DepthZero = "";
type Depth = string;
type Deeper<T extends Depth> = `${T}.`;
type IsDepthAtLimit<T extends Depth> = Extends<T, DepthLimit>;
type BasicReturnToTop = { type: "ReturnToTop", parameters: any[] };
type ReturnToTopWith<Params extends any[]> = { type: "ReturnToTop", parameters: Params };
// ---------- Operations on Foundational Types ----------
type SplitLastDigit<N extends WholeNumber> = SplitLastDigitTop<N, "">;
type SplitLastDigitTop<N extends StartsWithDigit, ButLast extends BlankOr<WholeNumber>> =
Apply<SplitLastDigitHKT, SplitLastDigitHKT, N, ButLast, DepthZero> extends infer ReturnValue
? ReturnValue extends { type: "ReturnToTop", parameters: [infer N2 extends StartsWithDigit, infer ButLast2 extends BlankOr<WholeNumber>] }
? SplitLastDigitTop<N2, ButLast2>
: ReturnValue
: never;
interface SplitLastDigitHKT extends HKT {
new: (
_Myself: Assume<this["_1"], HKT>, _N: Assume<this["_2"], StartsWithDigit>, _ButLast: Assume<this["_3"], BlankOr<WholeNumber>>, _D: Assume<this["_4"], Depth>
) =>
[
typeof _Myself, typeof _N, typeof _ButLast, typeof _D
] extends [
infer Myself extends HKT, infer N, infer ButLast extends BlankOr<WholeNumber>, infer D extends Depth
]
? N extends Digit
? [ButLast, N]
: N extends `${infer First extends Digit}${infer ButFirst extends StartsWithDigit}`
? IsDepthAtLimit<D> extends true
? ReturnToTopWith<[N, ButLast]>
: Apply<Myself, Myself, ButFirst, AsWholeNumber<`${ButLast}${First}`>, Deeper<D>>
: never
: never;
}
// appears to be broken when the depth limit is 100, but works for 90!
namespace TestSplitLastDigit {
// @ts-expect-error does not start with a digit
type _0 = SplitLastDigit<"">;
type _1 = Expect<Equal<["", "1"], SplitLastDigit<"1">>>;
type _2 = Expect<Equal<["1", "2"], SplitLastDigit<"12">>>;
type _3 = Expect<Equal<["12", "3"], SplitLastDigit<"123">>>;
type _4 = Expect<Equal<["123", "4"], SplitLastDigit<"1234">>>;
type TenCharNumber = "1234567890";
type _TestTenAndOne = Expect<Equal<[TenCharNumber, "6"], SplitLastDigit<`${TenCharNumber}6`>>>;
type OneHundredCharNumber = RepeatTenTimes<TenCharNumber>;
type _TestFifty = Expect<Equal<
["1234567890123456789012345678901234567890123456789", "0"],
SplitLastDigit<"12345678901234567890123456789012345678901234567890">
>>;
type _TestOneHundred = Expect<Equal<
["123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789", "0"],
SplitLastDigit<OneHundredCharNumber>
>>;
type _TestOneHundredAndOne = Expect<Equal<[OneHundredCharNumber, "6"], SplitLastDigit<`${OneHundredCharNumber}6`>>>;
type OneThousandCharNumber = RepeatTenTimes<OneHundredCharNumber>;
type _TestOneThousandAndOne = Expect<Equal<[OneThousandCharNumber, "6"], SplitLastDigit<`${OneThousandCharNumber}6`>>>;
type TenThousandCharNumber = RepeatTenTimes<OneThousandCharNumber>;
type _TestTenThousandAndOne = Expect<Equal<[TenThousandCharNumber, "6"], SplitLastDigit<`${TenThousandCharNumber}6`>>>;
}
// --------- Utilities ---------
type Expect<T extends true> = T;
type Equal<X, Y> = (<T>() => T extends X ? 1 : 2) extends <T>() => T extends Y ? 1 : 2
? true
: false;
type Extends<A, B> = A extends B ? true : false;
type IsNever<T> = Extends<[T], [never]>;
type IsFalse<T> = T extends false ? true : false;
type Assume<T, U> = T extends U ? T : U;
type FAIL = { type: "FAIL" };
type Fail<M extends string> = FAIL & { message: M };
type IsFail<T> = [T] extends [FAIL] ? true : false;
// ---------- Counting small(!) numbers with strings
type RepeatTenTimes<S extends string> = `${S}${S}${S}${S}${S}${S}${S}${S}${S}${S}`;
// ---------- Foundational Types ----------
type BlankOr<T> = "" | T;
type Digit = `${0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9}`;
type StartsWithDigit = `${Digit}${string}`; // can start with a zero
type WholeNumber = `${bigint}` & StartsWithDigit; // cannot start with a zero, all numbers
namespace TestWholeNumber {
type _0 = Expect<IsFalse<Extends<"", WholeNumber>>>;
type _1 = Expect<IsFalse<Extends<"QWERTY", WholeNumber>>>;
type _6 = Expect<Extends<"6", WholeNumber>>;
type _42 = Expect<Extends<"42", WholeNumber>>;
type _HUGE = Expect<Extends<"900719925474099190071992547409919007199254740991", WholeNumber>>;
}
type AsWholeNumber<T extends string> =
`${T}` extends infer WholeNumberT extends WholeNumber
? WholeNumberT
: never;
// ---------- Higher Kinded Types ----------
//
// See: https://code.lol/post/programming/higher-kinded-types/$0
//
type GenericFunction = (..._: never[]) => unknown;
abstract class HKT {
readonly _1?: unknown;
readonly _2?: unknown;
readonly _3?: unknown;
readonly _4?: unknown;
new?: GenericFunction;
}
// quite the hack
type Apply<F extends HKT, _1, _2 extends any = never, _3 extends any = never, _4 extends any = never> = ReturnType<
(F &
{
readonly _1: _1;
readonly _2: _2;
readonly _3: _3;
readonly _4: _4;
}) extends infer G extends { new: GenericFunction } ? G["new"] : never
>;
// ---------- Jackson's Widowbird ----------
//
// This preliminary version relies on the recursive type incorporating the
// "widowbird" behaviour of jumping back up to the top inline with the
// "business logic" of the recursive type itself.
//
// Non-trivial to-do:
//
// 1. Refactor to use an equivalent of the M combinator instead of hard-coding
// a self-referential type, and;
// 2. Writing "top" such that it can encode all this logic into a decorated
// "myself" that manages depth and knows when to go ack to the top.
type DepthLimit = RepeatTenTimes<".........">;
type DepthZero = "";
type Depth = string;
type Deeper<T extends Depth> = `${T}.`;
type IsDepthAtLimit<T extends Depth> = Extends<T, DepthLimit>;
type BasicReturnToTop = { type: "ReturnToTop", parameters: any[] };
type ReturnToTopWith<Params extends any[]> = { type: "ReturnToTop", parameters: Params };
// ---------- Operations on Foundational Types ----------
type SplitLastDigit<N extends WholeNumber> = SplitLastDigitTop<N, "">;
type SplitLastDigitTop<N extends StartsWithDigit, ButLast extends BlankOr<WholeNumber>> =
Apply<SplitLastDigitHKT, SplitLastDigitHKT, N, ButLast, DepthZero> extends infer ReturnValue
? ReturnValue extends { type: "ReturnToTop", parameters: [infer N2 extends StartsWithDigit, infer ButLast2 extends BlankOr<WholeNumber>] }
? SplitLastDigitTop<N2, ButLast2>
: ReturnValue
: never;
// TODO: Extract the limit check
// Refactor logic order
interface SplitLastDigitHKT extends HKT {
new: (
_Myself: Assume<this["_1"], HKT>, _N: Assume<this["_2"], StartsWithDigit>, _ButLast: Assume<this["_3"], BlankOr<WholeNumber>>, _D: Assume<this["_4"], Depth>
) =>
[
typeof _Myself, typeof _N, typeof _ButLast, typeof _D
] extends [
infer Myself extends HKT, infer N, infer ButLast extends BlankOr<WholeNumber>, infer D extends Depth
]
? IsDepthAtLimit<D> extends true
? ReturnToTopWith<[N, ButLast]>
: N extends Digit
? [ButLast, N] // generate case
: N extends `${infer First extends Digit}${infer ButFirst extends StartsWithDigit}`
? Apply<Myself, Myself, ButFirst, AsWholeNumber<`${ButLast}${First}`>, Deeper<D>>
: never
: never;
}
// appears to be broken when the depth limit is 100, but works for 90!
namespace TestSplitLastDigit {
// @ts-expect-error does not start with a digit
type _0 = SplitLastDigit<"">;
type _1 = Expect<Equal<["", "1"], SplitLastDigit<"1">>>;
type _2 = Expect<Equal<["1", "2"], SplitLastDigit<"12">>>;
type _3 = Expect<Equal<["12", "3"], SplitLastDigit<"123">>>;
type _4 = Expect<Equal<["123", "4"], SplitLastDigit<"1234">>>;
type TenCharNumber = "1234567890";
type _TestTenAndOne = Expect<Equal<[TenCharNumber, "6"], SplitLastDigit<`${TenCharNumber}6`>>>;
type OneHundredCharNumber = RepeatTenTimes<TenCharNumber>;
type _TestFifty = Expect<Equal<
["1234567890123456789012345678901234567890123456789", "0"],
SplitLastDigit<"12345678901234567890123456789012345678901234567890">
>>;
type _TestOneHundred = Expect<Equal<
["123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789", "0"],
SplitLastDigit<OneHundredCharNumber>
>>;
type _TestOneHundredAndOne = Expect<Equal<[OneHundredCharNumber, "6"], SplitLastDigit<`${OneHundredCharNumber}6`>>>;
type OneThousandCharNumber = RepeatTenTimes<OneHundredCharNumber>;
type _TestOneThousandAndOne = Expect<Equal<[OneThousandCharNumber, "6"], SplitLastDigit<`${OneThousandCharNumber}6`>>>;
type TenThousandCharNumber = RepeatTenTimes<OneThousandCharNumber>;
type _TestTenThousandAndOne = Expect<Equal<[TenThousandCharNumber, "6"], SplitLastDigit<`${TenThousandCharNumber}6`>>>;
}
// --------- Utilities ---------
type _xx = "" extends `${string}${string}` ? true : false;
type Expect<T extends true> = T;
type Equal<X, Y> = (<T>() => T extends X ? 1 : 2) extends <T>() => T extends Y ? 1 : 2
? true
: false;
type Extends<A, B> = A extends B ? true : false;
type IsNever<T> = Extends<[T], [never]>;
type IsFalse<T> = T extends false ? true : false;
type Assume<T, U> = T extends U ? T : U;
type AssumeOrDefault<T, U, Default> = T extends U ? T : Default;
type FAIL = { type: "FAIL" };
type Fail<M extends string> = FAIL & { message: M };
type IsFail<T> = [T] extends [FAIL] ? true : false;
type Update<T, K extends keyof any, V> = Omit<T, K> & { [Property in K]: V };
namespace TestUpdate {
type _0 = Expect<Equal<123, Update<{}, "id", 123>["id"]>>;
type _1 = Expect<Equal<123, Update<{ id: 456 }, "id", 123>["id"]>>;
}
// ---------- Counting small(!) numbers with strings
type RepeatFiveTimes<S extends string> = `${S}${S}${S}${S}${S}`;
type RepeatTenTimes<S extends string> = `${S}${S}${S}${S}${S}${S}${S}${S}${S}${S}`;
// ---------- Foundational Types ----------
type BlankOr<T> = "" | T;
type Digit = `${0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9}`;
type StartsWithDigit = `${Digit}${string}`; // can start with a zero
type WholeNumber = `${bigint}` & StartsWithDigit; // cannot start with a zero, all numbers
namespace TestWholeNumber {
type _0 = Expect<IsFalse<Extends<"", WholeNumber>>>;
type _1 = Expect<IsFalse<Extends<"QWERTY", WholeNumber>>>;
type _6 = Expect<Extends<"6", WholeNumber>>;
type _42 = Expect<Extends<"42", WholeNumber>>;
type _HUGE = Expect<Extends<"900719925474099190071992547409919007199254740991", WholeNumber>>;
}
type AsWholeNumber<T extends string> =
`${T}` extends infer WholeNumberT extends WholeNumber
? WholeNumberT
: never;
// ---------- Higher Kinded Types ----------
//
// See: https://code.lol/post/programming/higher-kinded-types/$0
//
type GenericFunction = (..._: never[]) => unknown;
abstract class HKT {
readonly _1?: unknown;
readonly _2?: unknown;
readonly _3?: unknown;
readonly _4?: unknown;
new?: GenericFunction;
}
// quite the hack
type Apply<F extends HKT, _1, _2 extends any = never, _3 extends any = never, _4 extends any = never> = ReturnType<
(F &
{
readonly _1: _1;
readonly _2: _2;
readonly _3: _3;
readonly _4: _4;
}) extends infer G extends { new: GenericFunction } ? G["new"] : never
>;
// both paramters required or it breaks
interface Reverse extends HKT {
new: (_1: Assume<this["_1"], string>, _2: this["_2"] extends string ? this["_2"] : "") =>
[typeof _1, typeof _2] extends [infer Source extends string, infer AccumulatedResult extends string]
? Source extends `${infer Head extends string}${infer ButHead extends string}`
? Apply<Reverse, ButHead, `${Head}${AccumulatedResult}`>
: AccumulatedResult
: never;
}
type GenericReverse<Source extends string, AccumulatedResult extends string = ""> =
Source extends `${infer Head extends string}${infer ButHead extends string}`
? GenericReverse<ButHead, `${Head}${AccumulatedResult}`>
: AccumulatedResult;
// this recursive type is coupled to itself
interface LastButLast extends HKT {
new: (_1: Assume<this["_1"], string>, _2: Assume<this["_2"], string>) =>
[typeof _1, typeof _2] extends [infer Source extends string, infer AccumulatedButLast extends string]
? Source extends `${infer Head extends string}${infer ButHead extends string}`
? ButHead extends ""
? [Head, AccumulatedButLast]
: Apply<LastButLast, ButHead, `${AccumulatedButLast}${Head}`>
: never
: never;
}
// can we decorate?
namespace TestReverse {
type _Reverse = Expect<Equal<"wen", Apply<Reverse, "new", "">>>;
type _GenericReverse = Expect<Equal<"cba", GenericReverse<"abc">>>;
type _LastButLast = Expect<Equal<["c", "ab"], Apply<LastButLast, "abc", "">>>;
}
// Q: Given a simple HKT that is not recursive, can we wrap it in a recursive HKT? If that recursive HKY invokes itself
// by name, can it recurse more than fifty deep?
//
// Wondering if the answer is "no" because the means of paramaterization is the creation of a new intersection type
// and therefore not true recursion but actually a hetero tail call (which I believe is not optimized)
interface Head extends HKT {
new: (_1: Assume<this["_1"], string>) =>
[typeof _1] extends [infer Source]
? Source extends `${infer Head extends string}${string}`
? Head
: ""
: never;
}
namespace TestHead {
type _0 = Expect<Equal<"", Apply<Head, "">>>;
type _1 = Expect<Equal<"a", Apply<Head, "a">>>;
type _10 = Expect<Equal<"1", Apply<Head, "1234567890">>>;
type _100 = Expect<Equal<"1", Apply<Head, RepeatTenTimes<"1234567890">>>>;
type _1000 = Expect<Equal<"1", Apply<Head, RepeatTenTimes<RepeatTenTimes<"1234567890">>>>>;
type _10000 = Expect<Equal<"1", Apply<Head, RepeatTenTimes<RepeatTenTimes<RepeatTenTimes<"1234567890">>>>>>;
}
interface HeadButHead extends HKT {
new: (_1: Assume<this["_1"], string>) =>
[typeof _1] extends [infer Source]
? Source extends `${infer Head extends string}${infer ButHead extends string}`
? [Head, ButHead]
: ["", ""]
: never;
}
namespace TestHeadButHead {
type _0 = Expect<Equal<["", ""], Apply<HeadButHead, "">>>;
type _1 = Expect<Equal<["a", ""], Apply<HeadButHead, "a">>>;
type _11 = Expect<Equal<["0", "1234567890"], Apply<HeadButHead, "01234567890">>>;
type _101 = Expect<Equal<["0", RepeatTenTimes<"1234567890">], Apply<HeadButHead, `0${RepeatTenTimes<"1234567890">}`>>>;
type _1001 = Expect<Equal<["0", RepeatTenTimes<RepeatTenTimes<"1234567890">>], Apply<HeadButHead, `0${RepeatTenTimes<RepeatTenTimes<"1234567890">>}`>>>;
type _10001 = Expect<Equal<["0", RepeatTenTimes<RepeatTenTimes<RepeatTenTimes<"1234567890">>>], Apply<HeadButHead, `0${RepeatTenTimes<RepeatTenTimes<RepeatTenTimes<"1234567890">>>}`>>>;
}
// Experiment: A bog-standard recursive type that applies HeadButHead
// Works up to the 1,000 call limit on tail-recursion
type TailGeneric<Source extends string> =
Apply<HeadButHead, Source> extends [infer Head extends string, infer ButHead extends string]
? ButHead extends ""
? Head
: TailGeneric<ButHead>
: never;
namespace TestTailGeneric {
type _0 = Expect<Equal<"", TailGeneric<"">>>;
type _1 = Expect<Equal<"0", TailGeneric<"0">>>;
type _10 = Expect<Equal<"0", TailGeneric<"1234567890">>>;
type _100 = Expect<Equal<"0", TailGeneric<RepeatTenTimes<"1234567890">>>>;
type _1000 = Expect<Equal<"0", TailGeneric<RepeatTenTimes<RepeatTenTimes<"1234567890">>>>>;
// @ts-expect-error limit on tail recursion is 1,000 invocations
type _10000 = Expect<Equal<"0", TailGeneric<RepeatTenTimes<RepeatTenTimes<RepeatTenTimes<"1234567890">>>>>>;
}
namespace DocumentRoleOfInferOnExtendsPredicate {
type NoInfers<S extends string> =
S extends `${string}${string}` ? true : false;
type _n0 = Expect<Equal<true, NoInfers<"">>>;
type _n1 = Expect<Equal<true, NoInfers<"a">>>;
type _n2 = Expect<Equal<true, NoInfers<"ab">>>;
type _n3 = Expect<Equal<true, NoInfers<"abc">>>;
// type both infers
type BothInfers<S extends string> =
S extends `${infer H extends string}${infer BH extends string}` ? `'${H}' '${BH}'` : false;
type _b0 = Expect<Equal<false, BothInfers<"">>>;
type _b1 = Expect<Equal<"'a' ''", BothInfers<"a">>>;
type _b2 = Expect<Equal<"'a' 'b'", BothInfers<"ab">>>;
type _b3 = Expect<Equal<"'a' 'bc'", BothInfers<"abc">>>;
type StringExtendsEmpty<S extends string> =
S extends `${infer Last extends string}${infer ButLast extends ""}` ? Last : false;
type _e0 = Expect<Equal<false, StringExtendsEmpty<"">>>;
type _e1 = Expect<Equal<"a", StringExtendsEmpty<"a">>>;
type _e2 = Expect<Equal<false, StringExtendsEmpty<"ab">>>;
type _e3 = Expect<Equal<false, StringExtendsEmpty<"abc">>>;
type StringExtendsString<S extends string> =
S extends `${infer Last extends string}${infer ButLast extends string}` ? [Last, ButLast] : false;
type _es0 = Expect<Equal<false, StringExtendsString<"">>>;
type _es1 = Expect<Equal<["a", ""], StringExtendsString<"a">>>;
type _es2 = Expect<Equal<["a", "b"], StringExtendsString<"ab">>>;
type _es3 = Expect<Equal<["a", "bc"], StringExtendsString<"abc">>>;
}
type HKTParameters<G extends HKT> = Parameters<G["new"] extends GenericFunction ? G["new"] : GenericFunction>;
type NumberOfHKTParameters<G extends HKT> = HKTParameters<G>["length"];
type TypeOfOfHKTParameter<G extends HKT, I extends TupleIndices<HKTParameters<G>>> = HKTParameters<G>[I];
type TupleIndices<T extends readonly any[]> =
Extract<keyof T, `${number}`> extends `${infer N extends number}` ? N : never;
// a generic approach to composition
interface Compose<F extends HKT, G extends HKT> extends HKT {
new: (
_1: Assume<this["_1"], HKTParameters<G>["0"]>,
_2?: Assume<this["_2"], HKTParameters<G>["1"]>,
_3?: Assume<this["_3"], HKTParameters<G>["2"]>,
_4?: Assume<this["_4"], HKTParameters<G>["3"]>
) =>
Apply<F,
Apply<G, Assume<this["_1"], HKTParameters<G>["0"]>, Assume<this["_2"], HKTParameters<G>["1"]>, Assume<this["_3"], HKTParameters<G>["2"]>, Assume<this["_4"], HKTParameters<G>["3"]>>
>
}
interface Dup extends HKT {
new: (_1: Assume<this["_1"], string>) => `${typeof _1}${typeof _1}`;
}
interface Catenate extends HKT {
new: (_1: Assume<this["_1"], string>, _2: Assume<this["_2"], string>) => `${typeof _1}${typeof _2}`;
}
namespace TestCatenate {
type _0 = Expect<Equal<"lmnop", Apply<Catenate, "lmn", "op">>>;
}
interface NOOP<F extends HKT> extends HKT {
new: (
_1: Assume<this["_1"], HKTParameters<F>["0"]>,
_2?: Assume<this["_2"], HKTParameters<F>["1"]>,
_3?: Assume<this["_3"], HKTParameters<F>["2"]>,
_4?: Assume<this["_4"], HKTParameters<F>["3"]>
) =>
Apply<F, Assume<this["_1"], HKTParameters<F>["0"]>, Assume<this["_2"], HKTParameters<F>["1"]>, Assume<this["_3"], HKTParameters<F>["2"]>, Assume<this["_4"], HKTParameters<F>["3"]>>
}
namespace TestCompose {
type _0 = Expect<Equal<"abcabc", Apply<Dup, "abc">>>;
type _1 = Expect<Equal<"cba", Apply<Reverse, "abc", "">>>;
type _2 = Expect<Equal<"abcabcabcabc", Apply<Compose<Dup, Dup>, "abc">>>;
type _3 = Apply<NOOP<Dup>, "abc">
type _4 = Expect<Equal<"xyzxyz", Apply<NOOP<Dup>, "xyz">>>;
type _5 = Apply<Compose<Dup, Catenate>, "lmn", "op">
}
// T is an "indirectly self-aware" type that takes itself (or a decorated version of itself)
// as a "myself" parameter for recursion. It calls myself, and passing myself to myself.
interface M<T extends HKT> extends HKT {
new: (
_1: Assume<this["_1"], HKTParameters<T>["1"]>,
_2?: Assume<this["_2"], HKTParameters<T>["2"]>,
_3?: Assume<this["_3"], HKTParameters<T>["3"]>,
) =>
HKTParameters<T>["0"] extends HKT
? Apply<T, T, Assume<this["_1"], HKTParameters<T>["1"]>, Assume<this["_2"], HKTParameters<T>["2"]>, Assume<this["_3"], HKTParameters<T>["3"]>>
: never;
}
interface LastButLastDecoupled extends HKT {
new: (_1: Assume<this["_1"], HKT>, _2: Assume<this["_2"], string>, _3: Assume<this["_3"], string>) =>
Assume<this["_2"], string> extends `${infer Head extends string}${infer ButHead extends string}`
? ButHead extends ""
? [Head, Assume<this["_3"], string>]
: Apply<Assume<this["_1"], HKT>, Assume<this["_1"], HKT>, ButHead, `${Assume<this["_3"], string>}${Head}`>
: ["", ""];
}
namespace TestM {
type _0 = Expect<Equal<["", ""], Apply<M<LastButLastDecoupled>, "", "">>>;
type _3 = Expect<Equal<["z", "xy"], Apply<M<LastButLastDecoupled>, "xyz", "">>>;
}
// T is an "indirectly self-aware" type that takes itself (or a decorated version of itself)
// as a "myself" parameter for recursion. It calls myself without passing myself, this
// recursive combinator handles that
interface Y<T extends HKT> extends HKT {
new: (
_1: Assume<this["_1"], HKTParameters<T>["1"]>,
_2?: Assume<this["_2"], HKTParameters<T>["2"]>,
_3?: Assume<this["_3"], HKTParameters<T>["3"]>,
) =>
HKTParameters<T>["0"] extends HKT
? Apply<T, Y<T>, Assume<this["_1"], HKTParameters<T>["1"]>, Assume<this["_2"], HKTParameters<T>["2"]>, Assume<this["_3"], HKTParameters<T>["3"]>>
: never;
}
namespace TestY {
// works for 47 (is this actually fifty if we include the test generics wrapping the call?)
type _1a = Expect<Equal<["7", "1234567890123456789012345678901234567890123456"], Apply<Y<LastButLastDecoupledY>, "12345678901234567890123456789012345678901234567", "">>>;
// does not work for 48
// @ts-expect-error
type _1b = Expect<Equal<["8", "12345678901234567890123456789012345678901234567"], Apply<Y<LastButLastDecoupledY>, "123456789012345678901234567890123456789012345678", "">>>;
}
type DepthLimit = 20;
type DepthZero = [];
type Depth = unknown[];
type Deeper<T extends Depth> = [...T, unknown];
type IsDepthAtLimit<D extends Depth> = D["length"] extends DepthLimit ? true : false;
type BasicReturnToTop = { type: "ReturnToTop", parameters: any[] };
type ReturnToTopWith<Params extends any[]> = { type: "ReturnToTop", parameters: Params };
// This is a version of Y that can "return to top" when the depth has reached a limit
interface YD<T extends HKT, D extends Depth> extends HKT {
new: (
_1: Assume<this["_1"], HKTParameters<T>["1"]>,
_2?: Assume<this["_2"], HKTParameters<T>["2"]>,
_3?: Assume<this["_3"], HKTParameters<T>["3"]>,
) =>
HKTParameters<T>["0"] extends HKT
? IsDepthAtLimit<D> extends true
? ReturnToTopWith<[Assume<this["_1"], HKTParameters<T>["1"]>, Assume<this["_2"], HKTParameters<T>["2"]>, Assume<this["_3"], HKTParameters<T>["3"]>]>
: Apply<T, YD<T, Deeper<D>>, Assume<this["_1"], HKTParameters<T>["1"]>, Assume<this["_2"], HKTParameters<T>["2"]>, Assume<this["_3"], HKTParameters<T>["3"]>>
: never;
}
// assumes y style call: apply myself to the parameters, myself is not a parameter
interface LastButLastDecoupledY extends HKT {
new: (_1: Assume<this["_1"], HKT>, _2: Assume<this["_2"], string>, _3: Assume<this["_3"], string>) =>
Assume<this["_2"], string> extends `${infer Head extends string}${infer ButHead extends string}`
? ButHead extends ""
? [Head, Assume<this["_3"], string>]
: Apply<Assume<this["_1"], HKT>, ButHead, `${Assume<this["_3"], string>}${Head}`>
: ["", ""];
}
namespace TestYD {
type _0 = Expect<Equal<["", ""], Apply<YD<LastButLastDecoupledY, DepthZero>, "", "">>>;
// works fine for up to DepthLimit characters
type _10 = Expect<Equal<["0", "123456789"], Apply<YD<LastButLastDecoupledY, DepthZero>, "1234567890", "">>>;
type _20 = Expect<Equal<["0", "1234567890123456789"], Apply<YD<LastButLastDecoupledY, DepthZero>, "12345678901234567890", "">>>;
// returns to top over limit
type _21 = Expect<Equal<ReturnToTopWith<["1", "12345678901234567890", never]>, Apply<YD<LastButLastDecoupledY, DepthZero>, "123456789012345678901", "">>>;
}
type LastButLastTop<Source extends string, ACC extends String = ""> =
Apply<YD<LastButLastDecoupledY, DepthZero>, Source, ACC> extends infer Result
? Result extends { type: "ReturnToTop", parameters: [infer NewSource extends string, infer NewACC extends string, ...any[]] }
? LastButLastTop<NewSource, NewACC>
: Result extends [infer Last extends string, infer ButLast extends string, ...any[]]
? [Last, ButLast]
: [Result]
: Fail<"WTF">;
namespace TestLastButLastTop {
type _0 = Expect<Equal<["", ""], LastButLastTop<"">>>;
type _1 = Expect<Equal<["z", ""], LastButLastTop<"z">>>;
type _3 = Expect<Equal<["z", "xy"], LastButLastTop<"xyz">>>;
type _10 = Expect<Equal<["0", "123456789"], LastButLastTop<"1234567890">>>;
type _20 = Expect<Equal<["0", "1234567890123456789"], LastButLastTop<"12345678901234567890">>>;
// recurse correctly over the limit
type _101 = Expect<Equal<["0", RepeatTenTimes<"1234567890">], LastButLastTop<`${RepeatTenTimes<"1234567890">}0`>>>;
type _1001 = Expect<Equal<["0", RepeatTenTimes<RepeatTenTimes<"1234567890">>], LastButLastTop<`${RepeatTenTimes<RepeatTenTimes<"1234567890">>}0`>>>;
type _10001 = Expect<Equal<["0", RepeatTenTimes<RepeatTenTimes<RepeatTenTimes<"1234567890">>>], LastButLastTop<`${RepeatTenTimes<RepeatTenTimes<RepeatTenTimes<"1234567890">>>}0`>>>;
}
type _ = Parameters<LastButLastDecoupledY["new"]>[1]
type Top2<F extends { new: GenericFunction }, Source extends Parameters<F["new"]>[1], ACC extends Parameters<F["new"]>[2]> =
Apply<YD<F, DepthZero>, Source, ACC> extends infer Result
? Result extends { type: "ReturnToTop", parameters: [infer NewSource extends Parameters<F["new"]>[1], infer NewACC extends Parameters<F["new"]>[2], ...any[]] }
? Top2<F, NewSource, NewACC>
: Result
: Fail<"2">;
namespace TestTop2 {
type _0 = Expect<Equal<["", ""], Top2<LastButLastDecoupledY, "", "">>>;
type _1 = Expect<Equal<["z", ""], Top2<LastButLastDecoupledY, "z", "">>>;
type _3 = Expect<Equal<["z", "xy"], Top2<LastButLastDecoupledY, "xyz", "">>>;
type _10 = Expect<Equal<["0", "123456789"], Top2<LastButLastDecoupledY, "1234567890", "">>>;
type _20 = Expect<Equal<["0", "1234567890123456789"], Top2<LastButLastDecoupledY, "12345678901234567890", "">>>;
// recurse correctly over the limit
type _101 = Expect<Equal<["0", RepeatTenTimes<"1234567890">], Top2<LastButLastDecoupledY, `${RepeatTenTimes<"1234567890">}0`, "">>>;
type _1001 = Expect<Equal<["0", RepeatTenTimes<RepeatTenTimes<"1234567890">>], Top2<LastButLastDecoupledY, `${RepeatTenTimes<RepeatTenTimes<"1234567890">>}0`, "">>>;
type _10001 = Expect<Equal<["0", RepeatTenTimes<RepeatTenTimes<RepeatTenTimes<"1234567890">>>], Top2<LastButLastDecoupledY, `${RepeatTenTimes<RepeatTenTimes<RepeatTenTimes<"1234567890">>>}0`, "">>>;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment