ในวิทยาการคอมพิวเตอร์การเรียกซ้ำแบบโพลีมอร์ฟิก (เรียกอีกอย่างว่าความสามารถในการกำหนดประเภทของ Milner – Mycroftหรือแคลคูลัส Milner–Mycroft ) หมายถึงฟังก์ชันโพลีมอร์ฟิกแบบพาราเมตริก ที่เรียก ซ้ำ โดยที่พารามิเตอร์ประเภทจะเปลี่ยนแปลงไปในแต่ละการเรียกซ้ำ แทนที่จะคงที่ การอนุมานประเภทสำหรับการเรียกซ้ำแบบโพลีมอร์ฟิกเทียบเท่ากับการรวมแบบกึ่งสมบูรณ์ดังนั้นจึงไม่สามารถตัดสินได้และต้องใช้อัลกอริทึมแบบกึ่งสมบูรณ์ หรือ คำอธิบายประกอบประเภทที่โปรแกรมเมอร์จัดหาให้^{[ 1 ]}

พิจารณาชนิดข้อมูลแบบซ้อนกัน ต่อไปนี้ ในภาษา Haskell :

ข้อมูลNested a = a :<: ( Nested [ a ]) | Epsilon infixr 5 :<:ซ้อนกัน= 1 :<: [ 2 , 3 , 4 ] :<: [[ 5 , 6 ],[ 7 ],[ 8 , 9 ]] :<: เอปซิลอน

ฟังก์ชันความยาวที่กำหนดไว้บนชนิดข้อมูลนี้จะเป็นแบบเรียกซ้ำเชิงโพลีมอร์ฟิก เนื่องจากชนิดของอาร์กิวเมนต์จะเปลี่ยนจากNested aเป็นNested [a]ในการเรียกซ้ำ:

ความยาว:: ซ้อนกันa -> ความยาวจำนวนเต็มEpsilon = 0 ความยาว( _ :<: xs ) = 1 + ความยาวxs

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

ในการวิเคราะห์โปรแกรมตามประเภทการเรียกซ้ำแบบโพลีมอร์ฟิกมักเป็นสิ่งจำเป็นเพื่อให้ได้ความแม่นยำสูงในการวิเคราะห์ ตัวอย่างที่โดดเด่นของระบบที่ใช้การเรียกซ้ำแบบโพลีมอร์ฟิก ได้แก่การวิเคราะห์เวลาผูกมัด ของ Dussart, Henglein และ Mossin ^{[ 2 ]} และ ระบบการจัดการหน่วยความจำตามภูมิภาคของ Tofte–Talpin ^{[ 3 ]}เนื่องจากระบบเหล่านี้ถือว่านิพจน์ได้รับการกำหนดประเภทแล้วในระบบประเภทพื้นฐาน (ไม่จำเป็นต้องใช้การเรียกซ้ำแบบโพลีมอร์ฟิก) การอนุมานจึงสามารถตัดสินได้อีกครั้ง

โครงสร้างข้อมูล การเขียนโปรแกรมเชิงฟังก์ชันมักใช้การเรียกซ้ำแบบโพลีมอร์ฟิกเพื่อลดความซับซ้อนของการตรวจสอบข้อผิดพลาดของประเภทและแก้ปัญหาด้วยวิธีแก้ปัญหาชั่วคราว "ตรงกลาง" ที่น่ารังเกียจซึ่งกินหน่วยความจำในโครงสร้างข้อมูลแบบดั้งเดิม เช่น ต้นไม้ ในการอ้างอิงสองรายการต่อไปนี้ Okasaki (หน้า 144–146) ให้ตัวอย่าง CONS ในHaskellซึ่งระบบประเภทโพลีมอร์ฟิกจะแจ้งข้อผิดพลาดของโปรแกรมเมอร์โดยอัตโนมัติ^{[ 4 ]}ลักษณะการเรียกซ้ำคือคำจำกัดความของประเภทรับประกันว่าตัวสร้างภายนอกสุดมีองค์ประกอบเดียว ตัวที่สองเป็นคู่ ตัวที่สามเป็นคู่ของคู่ ฯลฯ เรียกซ้ำไปเรื่อยๆ ซึ่งเป็นการกำหนดรูปแบบการค้นหาข้อผิดพลาดอัตโนมัติในประเภทข้อมูล Roberts (หน้า 171) ให้ตัวอย่างที่เกี่ยวข้องในJavaโดยใช้คลาสเพื่อแสดงเฟรมสแต็ก ตัวอย่างที่ให้มาคือวิธีแก้ ปัญหา Tower of Hanoiซึ่งสแต็กจำลองการเรียกซ้ำแบบโพลีมอร์ฟิกด้วยโครงสร้างการแทนที่สแต็กแบบซ้อนกันที่จุดเริ่มต้น ชั่วคราว และจุดสิ้นสุด^{[ 5 ]}

• โพลีมอร์ฟิซึมที่มีลำดับสูงกว่า

• Meertens, Lambert (1983). "การตรวจสอบประเภทโพลีมอร์ฟิกแบบเพิ่มทีละขั้นในภาษา B" (PDF) . การประชุมวิชาการ ACM ว่าด้วยหลักการของภาษาการเขียนโปรแกรม (POPL), ออสติน, เท็กซัส .
• Mycroft, Alan (1984). "Polymorphic type schemes and recursive definitions". International Symposium on Programming, Toulouse, France . Lecture Notes in Computer Science. Vol. 167. pp.  217– 228. doi : 10.1007/3-540-12925-1_41 . ISBN 978-3-540-12925-7.
• Henglein, Fritz (1993). "การอนุมานประเภทด้วยการเรียกซ้ำแบบโพลีมอร์ฟิก" ACM Transactions on Programming Languages ​​and Systems . 15 (2): 253– 289. CiteSeerX  10.1.1.42.3091 . doi : 10.1145/169701.169692 . S2CID  17411856 .
• Kfoury, AJ ; Tiuryn, J.; Urzyczyn, P. (เมษายน 1993). "การสร้างประเภทใหม่ในกรณีที่มีการเรียกซ้ำแบบโพลีมอร์ฟิก" . ACM Transactions on Programming Languages ​​and Systems . 15 (2): 290– 311. doi : 10.1145/169701.169687 . ISSN  0164-0925 . S2CID  18059949 .
• Michael I. Schwartzbach (มิถุนายน 1995). "การอนุมานประเภทโพลีมอร์ฟิก"รายงานทางเทคนิค BRICS-LS- 95-3
• Emms, Martin ; Leiß, Hans (1996). "การขยายตัวตรวจสอบประเภทสำหรับ SML ด้วยการเรียกซ้ำแบบโพลีมอร์ฟิก—การพิสูจน์ความถูกต้อง"รายงานทางเทคนิค 96-101
• ริชาร์ด เบิร์ดและแลมเบิร์ต เมียร์เทนส์ (1998) "ประเภทข้อมูลที่ซ้อนกัน "
• C. Vasconcellos, L. Figueiredo, C. Camarao (2003). " การอนุมานประเภทเชิงปฏิบัติสำหรับการเรียกซ้ำแบบพหุรูป: การนำไปใช้ใน Haskell ". วารสารวิทยาศาสตร์คอมพิวเตอร์สากล .
• L. Figueiredo, C. Camarao. " การอนุมานประเภทสำหรับคำจำกัดความแบบเรียกซ้ำโพลีมอร์ฟิก: ข้อกำหนดใน Haskell "
• Hallett, J. J; Kfoury, AJ (กรกฎาคม 2548). "ตัวอย่างการเขียนโปรแกรมที่ต้องการการเรียกซ้ำแบบโพลีมอร์ฟิก" . Electronic Notes in Theoretical Computer Science . 136 : 57– 102. doi : 10.1016/j.entcs.2005.06.014 . hdl : 2144/1532 . ISSN  1571-0661 .

• ML มาตรฐานพร้อมการเรียกซ้ำแบบโพลีมอร์ฟิกโดย Hans Leiß, LMU Munich