Skip to content

Instantly share code, notes, and snippets.

@decorator-factory
Created December 18, 2021 13:36
Show Gist options
  • Save decorator-factory/2dea7a641c80222e9238f660c55e1e7f to your computer and use it in GitHub Desktop.
Save decorator-factory/2dea7a641c80222e9238f660c55e1e7f to your computer and use it in GitHub Desktop.
TypeScript Higher Kinded Types using generic representation
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>) => {
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment