typescript - Beräkna typens fixpunkt

Antag att vi har någon typ-funktion F<T>, och vi vill beräkna dess fixpunkt type X=F<X>. Även om detta kan fungera med typer som är objekt

interface Tree1<T> { left: T; right: T }
interface Tree extends Tree1<Tree> {}
declare const t: Tree;
const r = t.left.right; // OK

för mer generiska typfunktioner gör det inte:

type Tree1<T> = null | { left: T; right: T }
interface Tree extends Tree1<Tree> {} // can't extend not-object

Utan en uppskjuten typnivåberäkning som ges av interface är det svårt att undvika oändlig instansiering. Det bästa jag kunde göra är helt enkelt att försena det:

interface Tree1<T> { left: T; right: T }
type Temp1<T> = { a: null | [T[keyof T], T[keyof T]] }
interface Temp2 extends Temp1<Temp2> {}
declare const t: Temp2;
const r = t.a; // Type instantiation is excessively deep

Det är också möjligt att åtgärda det genom att införa extraneous noder i trädet, men det är inte det jag är ute efter.

type Tree1<T> = null | { left: T; right: T }
type Tree = Tree1<{ref: Tree}> // OK

Ingen av dem definierar direkt Tree.

type Tree = null | { left: Tree, right: Tree }

Hur beräknar man den svårfångade fasta punkten?

type Tree1<T> = null | { left: T; right: T }
type Tree = ???
const t: Tree = {left: null, right: {left: null, right: null}};

Svar #1

Jag känner inte till något sätt att skapa en bokstavlig fixpunkt av en typfunktion, men du kan konstruera en typ som refererar till sig själv indirekt genom en egenskap. Beroende på vad du använder den till kan det vara tillräckligt bra.

Jag kom till din fråga eftersom jag har funderat på hur man ska typa abstrakta syntaxträd. Specifikt vill jag typa AST:er för en relaterad familj av språk. Till exempel kan vi ha en typ för uttryck som involverar addition av variabler, som "a + b + c", och vi kan ha en annan typ för uttryck som involverar variabler, addition och multiplikation, såsom "a*b + c".

Jag vill att dessa ska vara riktiga statiska typer — jag vill inte bara använda en stor AST-typ för att styra dem alla. Men jag vill också att typerna ska kunna utökas. Jag vill inte behöva definiera om hela grammatiken varje gång jag lägger till en ny typ av AST-nod.

Så jag tänkte, om du kunde ha en generisk parameter som motsvarar språkvárianten, skulle du kunna definiera AST-noder på det här sättet:

type Plus<α extends Grammer> = { 
    kind: "plus"
    left: Expr<α>
    right: Expr<α>
}

Då kan du definiera en generell version av grammatiken så här:

type AbelianGroupBaseGrammer<α extends Grammer> = Variable<α> | Plus<α>

Och gör det till en monotyp genom att konstruera en fixpunkt

AbelianGroupGrammer = AbelianGroupBaseGrammer<AbelianGroupGrammer>

Du kan utöka det till större språk på detta sätt

type RingBaseGrammar<α extends Grammer> = AbelianGroupBaseGrammer<α> | Times<α>

Det här fungerar inte i TypeScript, du får felet Type alias 'AbelianGroupGrammer' refererar cirkulärt till sig själv

Men om du gömmer självreferensen inom en objekt-egenskap kan du få samma effekt. Denna version gör typkontroll utan fel:

type Grammer = {
    "expression": unknown
}

type Expr<α extends Grammer> = α["expression"]

type Plus<α extends Grammer> = { 
    kind: "plus"
    left: Expr<α>
    right: Expr<α>
}

type Times<α extends Grammer> = { 
    kind: "times"
    left: Expr<α>
    right: Expr<α>
}

type Variable<α> = { 
    kind: "variable"
    name: string
}

type AbelianGroupBaseGrammer<α extends Grammer> = { 
    "expression": Variable<α> | Plus<α>
}

type AbelianGroupGrammer = { 
    "expression": Expr<AbelianGroupBaseGrammer<AbelianGroupGrammer>>
}

type RingBaseGrammer<α extends Grammer> = { 
    "expression": Expr<AbelianGroupBaseGrammer<α>> | Times<α>
}

type RingGrammer = {
    "expression": Expr<RingBaseGrammer<RingGrammer>>
}

const x : Expr<AbelianGroupGrammer> = {kind: "variable", name: "x"}
const y : Expr<AbelianGroupGrammer> = {kind: "variable", name: "y"}
const x_plus_y : Expr<AbelianGroupGrammer> = {kind:"plus", left: x, right: y}
const x_times_x_plus_y : Expr<RingGrammer> = {kind:"times", left: x, right: x_plus_y}

function group2ring(a : Expr<AbelianGroupGrammer>) : Expr<RingGrammer> { 
    return a
}