Polymorphic recursion

Consider the following nested datatype in Haskell:

dataNesteda=a:<:(Nested[a])|Epsiloninfixr5:<:nested=1:<:[2,3,4]:<:[[5,6],[7],[8,9]]:<:Epsilon

A length function defined over this datatype will be polymorphically recursive, as the type of the argument changes from Nested a to Nested [a] in the recursive call:

length::Nesteda->IntlengthEpsilon=0length(_:<:xs)=1+lengthxs

Note that Haskell normally infers the type signature for a function as simple-looking as this, but here it cannot be omitted without triggering a type error.

In type-based program analysis polymorphic recursion is often essential in gaining high precision of the analysis. Notable examples of systems employing polymorphic recursion include Dussart, Henglein and Mossin's binding-time analysis^[2] and the Tofte–Talpin region-based memory management system.^[3] As these systems assume the expressions have already been typed in an underlying type system (not necessary employing polymorphic recursion), inference can be made decidable again.

تستخدم هياكل بيانات البرمجة الوظيفية غالبًا الاستدعاء الذاتي متعدد الأشكال لتبسيط عمليات التحقق من أخطاء النوع وحل المشكلات التي تتطلب حلولًا مؤقتة "وسيطة" معقدة تستهلك الذاكرة بشكل كبير في هياكل البيانات التقليدية مثل الأشجار. في المرجعين التاليين،  يقدم أوكازاكي (ص 144-146) مثالًا على CONS في لغة هاسكل ، حيث يقوم نظام النوع متعدد الأشكال تلقائيًا بتحديد أخطاء المبرمج. ^{[ 4 ]} يتمثل الجانب الاستدعائي في أن تعريف النوع يضمن أن يكون للمنشئ الخارجي عنصر واحد، والثاني زوج، والثالث زوج من الأزواج، وهكذا بشكل استدعائي، مما يُنشئ نمطًا تلقائيًا لاكتشاف الأخطاء في نوع البيانات.  يقدم روبرتس (ص 171) مثالًا مشابهًا في لغة جافا ، باستخدام فئة لتمثيل إطار مكدس. المثال المعطى هو حل لمسألة برج هانوي ، حيث يحاكي المكدس الاستدعاء الذاتي متعدد الأشكال مع بنية استبدال مكدس متداخلة في البداية والمؤقتة والنهاية. ^{[ 5 ]}