TypeScript Higher Kinded Types using generic representation

madness.ts

declare class Fail<Message extends string, Detail> { #_: Fail<Message, Detail> }

///
enum $A {}; enum $B {}; enum $C {}; enum $D {}; enum $E {}; enum $F {}; enum $G {}; enum $H {};


///


declare class Barrier<T, Tag> { #body: T; #tag: Tag }
type Lambda<Var, Body> = { lambda: Var, do: Barrier<Body, Var> }


type Rewrite<Fun, ConstructedArg> = // Like `Apply`, but doesn't `Construct` the result
    Construct<Fun> extends infer ConstructedFun
    ? ConstructedFun extends Lambda<infer Var, infer Body>
        ? ReplaceVar<Body, Var, {_: ConstructedArg}>
        : Fail<"Expected a lambda, got:", ConstructedFun>
    : never


type Apply<Fun, ConstructedArg> = // Apply a lambda to a *constructed* argument
    Construct<Fun> extends infer ConstructedFun
    ? ConstructedFun extends Lambda<infer Var, infer Body>
        ? Construct<ReplaceVar<Body, Var, {_: ConstructedArg}>>
        : Fail<"Expected a lambda, got:", ConstructedFun>
    : never


type Construct<Rep> =
      Rep extends never
    ? never

    // Constant type, like {_: number}
    : Rep extends { _: infer T }
    ? T

    // Record type, like {obj: {x: {_: number}, y: {_: string}}}
    : Rep extends { obj: infer R }
    ? R extends Record<string, unknown>
        ? {[K in keyof R]: Construct<R[K]>}
        : Fail<"Expected a record with string keys, got:", R>

    // Intersection type
    : Rep extends { and: [infer A, infer B] }
    ? Construct<A> & Construct<B>

    // Array or tuple type
    : Rep extends { arr: infer A }
    ? A extends unknown[]
        ? {[K in keyof A]: Construct<A[K]>}
        : Fail<"Expected an array or tuple type, got:", A>

    // Union type, like {union: [{_: number}, {_: string}]}
    : Rep extends { union: infer U }
    ? U extends unknown[]
        ? {[K in keyof U]: Construct<U[K]>}[number]
        : Fail<"Expected a tuple type, got:", U>

    // Generic function (see examples later)
    : Rep extends { gen: infer Arg, returning: infer Ret }
        ? <A>(arg: Apply<Arg, A>) => Apply<Ret, A>

    // Normal function, e.g. {fun: {arr: [{_: number}, {_: string}]}, returning: {_: string[]}}
    // means (number, string) -> string[]
    : Rep extends { fun: infer Args, returning: infer Ret }
        ? Construct<Args> extends infer ConstructedArgs
            ? ConstructedArgs extends unknown[]
                ? (...args: ConstructedArgs) => Construct<Ret>
                : Fail<"Expected an array or tuple type, got:",  ConstructedArgs>
            : never

    // Application of a lambda to an argument
    : Rep extends { app: infer App, arg: infer Arg }
        ? Apply<App, Construct<Arg>>

    : Rep extends { var: infer Var }
    ? Fail<"Cannot construct a free variable:", Var>

    : Rep extends Lambda<infer Var, infer Body>
    ? Lambda<Var, Body>

    : Fail<"Cannot construct:", Rep>;


type ReplaceVar<T, Var, New> =
    T extends {var: Var}
    ? New

    : T extends Function
    ? T

    : T extends Barrier<infer Inner, infer Tag>
        ? Var extends Tag
            ? T
            : Barrier<ReplaceVar<Inner, Var, New>, Tag>
    : T extends Record<any, any> | any[]
        ? {[K in keyof T]: ReplaceVar<T[K], Var, New>}

    : T;



namespace GenericTypeExample {
    enum $T {}
    type ArrRep = Lambda<$T, {
        obj: {
            getItem: { fun: { arr: [index: {_: number}] }, returning: {var: $T} },
            setItem: { fun: { arr: [index: {_: number}, value: {var: $T}] }, returning: {_: void} },
            len: { fun: { arr: [] }, returning: {_: number} },
        }
    }>;

    type Arr<T> = Apply<ArrRep, T>;
    type StringArr = Arr<string>;
    type PointArr = Arr<{x: number, y: number}>;


    namespace Explanation {
        // Here we will encode a representaiton of a generic array type `Arr<T>` with three methods:
        type Arr<T> = {
            getItem: (index: number) => T,
            setItem: (index: number, value: T) => void,
            len: () => number,
        }

        // A generic type is just a function taking a type and returning a type.

        enum $T {} // This is our 'type variable'

        // `Lambda` encodes a type-level function
        type ArrRep = Lambda<$T, {
            // `obj` encodes a record type
            obj: {

                // function which
                // takes a `number` --------+   returns `$T`: ------------+
                //                          V                             V
                getItem: { fun: { arr: [{_: number}] }, returning: {var: $T} },

                // function which
                // takes a `number` --------+   and `$T` ---+    returns `void`: ---+
                //                          V               V                       V
                setItem: { fun: { arr: [{_: number}, {var: $T}] }, returning: {_: void} },

                // function which
                // takes no args --+  returns a `number` --+
                //                 V                       V
                len: { fun: { arr: [] }, returning: {_: number} },
            }
        }>

        // So when we run `Apply<ArrRep, string>`, we essentially get this:
        type StringArrRep = {
            obj: {
                getItem: { fun: { arr: [{_: number}] }, returning: {_: string }},
                setItem: { fun: { arr: [{_: number}, {_: string}] }, returning: {_: void} },
                len: { fun: { arr: [] }, returning: {_: number} },
            }
        };

        // We can use the `Rewrite` helper function to verify that! (hover over `_X`)
        type _X = Rewrite<ArrRep, string>


        // Quality-of-life-improvement: you can use named tuples in function arguments.
        type ArrRep2 = Lambda<$T, {
            obj: {
                getItem: { fun: { arr: [index: {_: number}] }, returning: {var: $T} },
                setItem: { fun: { arr: [index: {_: number}, value: {var: $T}] }, returning: {_: void} },
                len: { fun: { arr: [] }, returning: {_: number} },
            }
        }>;
        // Now you get proper argument names:
        type StringArr = Apply<ArrRep2, string>;

    }

}

//// Generic function example

// {gen: Lambda, returning: Lambda} accepts two lambdas `gen` and `returning`
// `gen` should, given a type `T`, return the argument type for the function
// `returning` should, given a type `T`, return the return type for the functino
// From this, a generic function is constructed.
/*(implementation snippet)
    : Rep extends { gen: infer Arg, returning: infer Ret }
    ? <A>(arg: Apply<Arg, A>) => Apply<Ret, A>
*/





// Example 1.
type idRep = Lambda<$A, {var: $A}>;
type toPairRep = Lambda<$A, {arr: [{var: $A}, {var: $A}]}>;
type MakePair = Construct<{gen: idRep, returning: toPairRep}>;
// MakePair: <A>(arg: A) => [A, A]


// Example 2. From array to (pair | null)
type toArrayRep = Lambda<$A, {arr: {var: $A}[]}>;
type toNullablePairRep = Lambda<$A, {union: [{_: null}, {app: toPairRep, arg: {var: $A}}]}>;
type FromArrayToNullablePair = Construct<{gen: toArrayRep, returning: toNullablePairRep}>;
// FromArrayToNullablePair: <A>(arg: A[]) => [A, A] | null




//// Higher kinded type example


// This function takes a `Lambda` representation!
/*
type Pure<F kind 2> = {
    pure: <A>(a: A) => F<A>
}
*/
type PureRep = Lambda<$F, {
    obj: {
        pure : {
            gen: Lambda<$A, {var: $A}>,
            returning: {var: $F},
        }
    }
}>;
type Pure<FRep> = Apply<PureRep, FRep>;


type ArrayPure = Pure<toArrayRep>;
(fun: ArrayPure) => {
    const y = fun.pure(42)
}





//// More complex higher kinded type example

/*
type Functor<F kind 2> = {
    map: <A>(fa: F<A>) => <B>(fn: (A => B)) => F<B>
}
*/
type FunctorRep = Lambda<$F, {
    obj: {
        map: {
            gen: {var: $F},
            returning: Lambda<$A, {
                gen: Lambda<$B, {fun: {arr: [{var: $A}]}, returning: {var: $B}}>,
                returning: {var: $F},
            }>,
        }
    }
}>;
type Functor<FRep> = Apply<FunctorRep, FRep>;

/*
type PureFunctor<F kind 2> = Pure<F> & Functor<F>

type PureFunctor<F kind 2> = {
    pure: <A>(a: A) => F<A>,
    map: <A>(fa: F<A>) => <B>(fn: (A => B)) => F<B>,
}
*/
type PureFunctorRep = Lambda<$F, {
    and: [
        {app: PureRep, arg: {var: $F}},
        {app: FunctorRep, arg: {var: $F}},
    ]
}>;
type PureFunctor<FRep> = Apply<PureFunctorRep, FRep>;


type ArrayFunctor = Functor<toArrayRep>;
type ArrayPureFunctor = PureFunctor<toArrayRep>;



(fun: ArrayFunctor) => {
    const y = fun.map([1, 2, 3])(x => [x, x.toString()] as const)
}

(fun: ArrayPureFunctor) => {
    const y = fun.map(fun.map([1, 2, 3])(x => [x, x.toString()] as const))(([a, b]) => [b, a])
}


// Hmmm... this doesn't type check.
// Type 'A' is not assignable to type 'ReplaceVar<A, $B, { _: A; }>'
const arrFunctor: Functor<toArrayRep> = {
    map: <A>(elts: A[]) => <B>(fn: (_: A) => B) => elts.map(fn)
};


// How do I parametrize over `F` _and_ `A`?
<F>(functor: Functor<F>) => {

}