Higher kinded types in typescript

higher-kinded.ts

// The two main components are the interfaces
// Generic<T, Context> and GenericArg<"identifier">

// Generic basically structurally replaces types in T that are GenericArg<S>
// for some `S extends keyof Context` with `Context[S]`
// See the test cases for specific uses.

// ====== TESTING
// Pass through for trivial types
type Test00 = Generic<number>;
let t00: Assert<Test00, number> = true;
type Test01 = Generic<string>;
let t01: Assert<Test01, string> = true;
type Test02 = Generic<void>;
let t02: Assert<Test02, void> = true;
enum TestEnum { Green = 0, Blue = "STR" };
type Test03 = Generic<TestEnum>;
let t03: Assert<Test03, TestEnum> = true;
type Test04 = Generic<0 | 2 | "strconstrant">;
let t04: Assert<Test04, 0 | "strconstrant"> = true;
// Given a GenericArg<S> and a context {[K in S]: T} returns T 
type Test1 = Generic<GenericArg<"foo">, { foo: string }>;
let t1: Assert<Test1, string> = true;
// Given an object type, replaces all generics in each property
// GenericModel<foo> is replaced by GenericModel<foo=string>
type GenericModel = { prop: GenericArg<"foo"> };
type Test2 = Generic<GenericModel, { foo: string }>;
let t2: Assert<Test2, { prop: string }> = true;
// Homogeneous array types work fine
type Test3 = Generic<GenericModel[], { foo: string }>;
let t3: Assert<Test3, { prop: string }[]> = true;
// And types can be reused in other types.
// Here DerivedModel<bar> contains a GenericModel<foo=bar>
// A DerivedModel<bar=string> propagates into GenericModel<foo=bar=string>
type DerivedModel = { underlying: Generic<GenericModel, { foo: GenericArg<"bar"> }> };
type Test4 = Generic<DerivedModel, { bar: string }>;
let t4: Assert<Test4, { underlying: { prop: string } }> = true;
// Even works with spread parameters!
type FunctionWithSpreadParams = (input1: GenericArg<"foo">, ...input2: GenericArg<"bar">[]) => GenericArg<"foo">;
type Test5 = Generic<FunctionWithSpreadParams, { foo: string, bar: number }>;
// let t5: Assert<Test5, (input1: string, ...input2: number[]) => string> = true;
let t5: Assert<Test5, typeof RestParametersErrorSymbol> = true; // :/
// This is primarily because I couldn't get general tuple-types to work
type BadTupleType = [GenericArg<"foo">, ...GenericArg<"bar">[]];
type Test6 = Generic<BadTupleType, { foo: string, bar: number }>;
// let t6: Assert<Test6, [string, ...number[]]> = true;
let t6: Assert<Test6, typeof RestParametersErrorSymbol> = true; // :/
// An of course, object types in function parameters are working aswell :)
type GoodFunctionModel = (i: { input1: GenericArg<"foo">, input2: GenericArg<"bar"> }) => GenericArg<"foo">;
type Test7 = Generic<GoodFunctionModel, { foo: string, bar: number }>;
let t7: Assert<Test7, (i: { input1: string, input2: number }) => string> = true;
// More generic tests
type BiggerTupleModel = [GenericArg<"foo">, number, string, {bar: GenericArg<"bar">}, GenericArg<"foobar">[]];
type Test8 = Generic<BiggerTupleModel, {foo: string, bar: {complicated: string}, foobar: number}>;
let t8: Assert<Test8, [string, number, string, {bar: {complicated: string}}, number[]]> = true;

// ===== Example usage
// Nevertheless, this shows how we can use this.
// Basically, the keyword is higher-kinded types - in a way that is pleasent to read and write
// Declare a functor instance. The generic parameter is called "result"
interface Functor<F> {
    map<A, B>(functor: Generic<F, { result: A }>, mapping: (a: A) => B): Generic<F, { result: B }>;
}
type GenericArray = GenericArg<"result">[];
const arrayFunctor = {
    map<A, B>(arr: A[], mapping: (a: A) => B): B[] {
        return arr.map(mapping);
    }
} as Functor<GenericArray>;

type Maybe<T> = T | void;
const maybeFunctor = {
    map<A, B>(x: Maybe<A>, mapping: (a: A) => B): Maybe<B> {
        if (x === undefined || x === null) {
            return x as void;
        }
        return mapping(x as A);
    }
} as Functor<Maybe<GenericArg<"result">>>;

// Javascript of course does not support implicit arguments
// So you have to provide the functor instance yourself when you need it
function double<F>(functor: Functor<F>, structure: Generic<F, { result: number }>): Generic<F, { result: number }> {
    return functor.map(structure, n => 2 * n);
}
console.log(double(arrayFunctor, [0, 1, 2, 3, 4])); // Prints [ 0, 2, 4, 6, 8 ]

console.log(double(maybeFunctor, undefined)); // Prints undefined
console.log(double(maybeFunctor, 15)); // Prints 30

// ===== Heavy lifting done here
const GenericArgSymbol = Symbol("GenericArgumentSymbol");
interface GenericArg<T extends string> { [GenericArgSymbol]: T }

const GenericNotPresentErrorSymbol = Symbol("Generic-Arg couldn't be replaced. Not present in the arguments");
const RestParametersErrorSymbol = Symbol("can't infer rest parameters at the moment");

const GenericErrorSymbol = Symbol("Generic-Arg couldn't be converted. assert failed");
const ArrayErrorSymbol = Symbol("Head<T> is never, but T is not an actual array (infer U)[]. assert failed");
const ObjectErrorSymbol = Symbol("object couldn't be converted. assert failed");
const FunctionErrorSymbol = Symbol("function couldn't be converted. assert failed");
const OtherErrorSymbol = Symbol("unknown error. assert failed");
const UnreachableErrorSymbol = Symbol("thought unreachable. assert failed");

const MoreThanOneWrappedRestErrorSymbol = Symbol("only the first type in argument to Tuple can be a WrappedRest. assert failed");

const GenericWrappedSymbol = Symbol("GenericArgumentSymbol");
class WrappedRest<T> { [GenericWrappedSymbol]: T };
// If Tuple is actually an array U[], this results in never
// If Tuple is [H, ...] for some H, this results in H
type Head<Tuple extends any[]> = Tuple extends [infer H, ...any[]] ? H : never;
// BEWARE OF ACTUAL ARRAYS. If U[], then Tail<U[]> = U[]. Check with Head first
type Tail<Tuple extends any[]> = ((...t: Tuple) => void) extends ((h: any, ...rest: infer R) => void) ? R : never;
// Prepends Element before the existing tuple.
// If Tuple is an actual array, this results in a tuple with a rest parameter
type Unshift<Tuple extends any[], Element> = ((h: Element, ...t: Tuple) => void) extends (...t: infer R) => void ? R : never;

// Reverses an tuple. A WrappedRest<U> at the start or a rest parameter at the end will be converted into each other
type Reverse<Tuple extends any[]> = Reverse_<Tuple, []>;
type Reverse_<Tuple extends any[], R extends any[]>
    = {
        3: Tuple extends (infer U)[]
            ? Unshift<R, WrappedRest<U>>
            : typeof ArrayErrorSymbol; // Guarded above of us
        2: Head<Tuple> extends WrappedRest<infer U>
            ? R extends []
            ? Reverse_<Tail<Tuple>, U[]>
            : typeof MoreThanOneWrappedRestErrorSymbol
            : typeof UnreachableErrorSymbol, // Guarded above of us
        1: R,
        0: Reverse_<Tail<Tuple>, Unshift<R, Head<Tuple>>>
    } [ Tuple extends []
        ? 1
        : Head<Tuple> extends WrappedRest<infer U>
        ? 2
        : Head<Tuple> extends never
        ? 3
        : 0
    ];

type ReverseGenericTup_<T extends any[], Arg extends object, R extends any[]>
    = {
        2: T extends (infer U)[]
            ? typeof RestParametersErrorSymbol // Unshift<R, WrappedRest<Generic<U, Arg>>> // if this would work :)
            : typeof ArrayErrorSymbol, // Guarded above of us
        1: R,
        0: ReverseGenericTup_<Tail<T>, Arg, Unshift<R, Generic<Head<T>, Arg>>>;
    } [ T extends []
        ? 1
        : Head<T> extends never
        ? 2
        : 0
    ];

type GenericFun<T extends Function, Arg extends object>
    = T extends (...rest: infer A) => infer R
    ? GenericTup<A, Arg> extends infer GA
    ? GA extends any[]
    ? (...rest: GA) => Generic<R, Arg>
    : GA    // propagate any error
    : typeof UnreachableErrorSymbol // can't fail since GA is simply an alias
    : typeof FunctionErrorSymbol; // infers A and R, might fail if T is not actually a function?

type GenericTup<T extends any[], Arg extends object>
    = ReverseGenericTup_<T, Arg, []> extends infer H
    ? H extends any[]
    ? Reverse<H>
    : H // propagate any error
    : typeof UnreachableErrorSymbol; // H is simply an alias, it always infers

type AnyGenericArg = GenericArg<any>;
type AnyArray = any[];
type AnyObject = object;
type AnyFunction = (...args: any[]) => any;
// see also https://github.com/Microsoft/TypeScript/issues/14174
type Generic<T, Arg extends object = {}>
    = {
        gen: T extends GenericArg<infer S>
            ? S extends keyof Arg
            ? Arg[S]
            : typeof GenericNotPresentErrorSymbol
            : typeof GenericErrorSymbol;
        arr: T extends AnyArray
            ? Head<T> extends never
            ? T extends (infer U)[]
            ? Generic<U, Arg>[]
            : typeof ArrayErrorSymbol
            : GenericTup<T, Arg>
            : typeof UnreachableErrorSymbol; // Taken care above of us
        fun: T extends AnyFunction ? GenericFun<T, Arg> : typeof FunctionErrorSymbol;
        obj: T extends {}
            ? { [K in keyof T]: Generic<T[K], Arg> }
            : typeof ObjectErrorSymbol;
        trv: T;
        els: typeof OtherErrorSymbol;
    } [ T extends AnyGenericArg
        ? 'gen'
        : T extends AnyArray
        ? 'arr'
        : T extends AnyFunction
        ? 'fun'
        : T extends AnyObject
        ? 'obj'
        : T extends boolean | number | string | symbol | void | undefined | null | never | unknown
        ? 'trv'
        : 'els'
    ];
type Assert<A, B> = A extends B ? B extends A ? true : never : never

// type anyArr = any[];
// type fakeAnyArr = { [K in keyof anyArr]: anyArr[K]; };
// const isFakeReal: Assert<anyArr, fakeAnyArr> = true;
// type funcDecl1 = (...args: anyArr) => void;
// type funcDecl2 = fakeAnyArr extends [...infer U] ? (...args: [U]) => void : never;