typescript - คำนวณจุดคงที่ของชนิด

สมมติว่าเรามีฟังก์ชันประเภทบางประเภท F<T> และเราต้องการคำนวณจุดคงที่ของมัน type X=F<X> แม้ว่าสิ่งนี้อาจใช้ได้กับประเภทที่เป็นวัตถุ

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

สำหรับฟังก์ชันประเภททั่วไปมากขึ้น มันไม่ได้:

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

หากไม่มีการคำนวณระดับประเภทแบบเลื่อนออกซึ่งกำหนดโดย interface จะเป็นเรื่องยากที่จะหลีกเลี่ยงการสร้างอินสแตนซ์ไม่สิ้นสุด สิ่งที่ดีที่สุดที่ฉันทำได้คือเพียงเลื่อนมันออกไป:

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

นอกจากนี้สามารถแก้ไขได้โดยการใส่โหนดที่ไม่จำเป็นเข้าไปในต้นไม้ แต่สิ่งนั้นไม่ใช่สิ่งที่ฉันต้องการ

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

ทั้งสองไม่ได้กำหนด Tree โดยตรง

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

จะคำนวณจุดคงที่ที่หายากนั้นได้อย่างไร?

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

คำตอบ #1

ฉันไม่รู้วิธีสร้างจุดคงที่เชิงตัวอักษรของฟังก์ชันชนิด แต่คุณสามารถสร้างชนิดที่อ้างอิงตัวเองโดยทางอ้อมผ่านคุณสมบัติ ขึ้นอยู่กับว่าคุณใช้มันทำอะไร นั่นอาจเพียงพอแล้ว

ฉันมาที่คำถามของคุณเพราะฉันกำลังคิดเกี่ยวกับวิธีการพิมพ์ต้นไม้ไวยากรณ์นามธรรม โดยเฉพาะอย่างยิ่ง ฉันต้องการพิมพ์ AST สำหรับกลุ่มภาษาที่เกี่ยวข้องกัน ตัวอย่างเช่น เราอาจมีชนิดสำหรับนิพจน์ที่เกี่ยวข้องกับการบวกตัวแปรเข้าด้วยกัน เช่น 'a + b + c' และเราอาจมีชนิดอีกหนึ่งสำหรับนิพจน์ที่เกี่ยวข้องกับตัวแปร การบวก และการคูณ เช่น 'a*b + c'.

ฉันต้องการให้สิ่งเหล่านี้เป็นชนิดแบบคงที่จริง ๆ — ฉันไม่ต้องการใช้เพียงชนิด AST ขนาดใหญ่เพียงชนิดเดียวเพื่อควบคุมทั้งหมด แต่ฉันก็ต้องการให้ชนิดเหล่านี้สามารถขยายเพิ่มเติมได้ด้วย ฉันไม่ต้องการที่จะต้องกำหนดไวยากรณ์ทั้งหมดใหม่ทุกครั้งที่ฉันเพิ่มชนิดใหม่ของโหนด AST

ดังนั้นฉันจึงคิดว่า ถ้าคุณสามารถมีพารามิเตอร์ทั่วไปที่สอดคล้องกับรูปแบบภาษาต่าง ๆ คุณก็สามารถกำหนดโหนด AST แบบนี้ได้:

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

จากนั้นคุณสามารถกำหนดเวอร์ชันทั่วไปของไวยากรณ์ได้ดังนี้:

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

และเปลี่ยนมันให้เป็นมอนอไทป์โดยการสร้างจุดคงที่

AbelianGroupGrammer = AbelianGroupBaseGrammer<AbelianGroupGrammer>

คุณสามารถขยายมันไปยังภาษาที่ใหญ่กว่าได้ดังนี้

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

นี่ใช้ไม่ได้ใน TypeScript คุณจะได้รับข้อผิดพลาด Type alias 'AbelianGroupGrammer' อ้างอิงตัวเองแบบวงกลม

แต่ถ้าคุณซ่อนการอ้างอิงตัวเองไว้ภายในคุณสมบัติของวัตถุ คุณก็สามารถได้ผลลัพธ์เหมือนกัน เวอร์ชันนี้ทำการตรวจสอบประเภทโดยไม่มีข้อผิดพลาด:

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
}