computer science

Polymorphic recursion

Polymorphic recursion is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Polymorphic recursion rather than just read about it. In short: In computer science, polymorphic recursion (also referred to as Milner–Mycroft typability or the Milner–Mycroft calculus) refers to a recursive parametrically polymorphic function where the type parameter changes with each recursive invocation made, instead of staying constant. Type inference for polymorphic recursion is equivalent to semi-unification and therefore undecidable and requires the use of a semi-algorith…

Key takeaways

Polymorphic recursion belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Polymorphic recursion to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Polymorphic recursion from memory before moving on to harder problems.

Reference excerpt

In computer science, polymorphic recursion (also referred to as Milner–Mycroft typability or the Milner–Mycroft calculus) refers to a recursive parametrically polymorphic function where the type parameter changes with each recursive invocation made, instead of staying constant. Type inference for polymorphic recursion is equivalent to semi-unification and therefore undecidable and requires the use of a semi-algorithm or programmer-supplied type annotations.

Example

Nested datatypes Consider the following nested datatype in Haskell:

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:

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.

Higher-ranked types

Applications

Program analysis 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 and the Tofte–Talpin region-based memory management system. 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.

Data structures, error detection, graph solutions Functional programming data structures often use polymorphic recursion to simplify type error checks and solve problems with nasty "middle" temporary solutions that devour memory in more traditional data structures such as trees. In the two citations that follow, Okasaki (pp. 144–146) gives a CONS example in Haskell wherein the polymorphic type system automatically flags programmer errors. The recursive aspect is that the type definition assures that the outermost constructor has a single element, the second a pair, the third a pair of pairs, etc. recursively, setting an automatic error finding pattern in the data type. Roberts (p. 171) gives a related example in Java, using a Class to represent a stack frame. The example given is a solution to the Tower of Hanoi problem wherein a stack simulates polymorphic recursion with a beginning, temporary and ending nested stack substitution structure.

See also Higher-ranked polymorphism

Notes

Further reading Meertens, Lambert (1983). "Incremental polymorphic type checking in B" (PDF). ACM Symposium on Principles of Programming Languages (POPL), Austin, Texas. 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). "Type inference with polymorphic recursion". ACM Transactions on Programming Languages and Systems. 15 (2): 253–289. CiteSeerX 10.1.1.42.3091. doi:10.1145/169701.169692. S2CID 17411856. {{cite journal}}: Cite uses deprecated parameter |citeseerx= (help) Kfoury, A. J.; Tiuryn, J.; Urzyczyn, P. (April 1993). "Type reconstruction in the presence of polymorphic recursion". ACM Transactions on Programming Languages and Systems. 15 (2): 290–311. doi:10.1145/169701.169687. ISSN 0164-0925. S2CID 18059949. Michael I. Schwartzbach (June 1995). "Polymorphic type inference". Technical Report BRICS-LS-95-3. Emms, Martin; Leiß, Hans (1996). "Extending the type checker for SML by polymorphic recursion—A correctness proof". Technical Report 96-101. Richard Bird and Lambert Meertens (1998). "Nested Datatypes". C. Vasconcellos, L. Figueiredo, C. Camarao (2003). "Practical Type Inference for Polymorphic Recursion: an Implementation in Haskell". Journal of Universal Computer Science. L. Figueiredo, C. Camarao. "Type Inference for Polymorphic Recursive Definitions: a Specification in Haskell". Hallett, J. J; Kfoury, A. J. (July 2005). "Programming Examples Needing Polymorphic Recursion". Electronic Notes in Theoretical Computer Science. 136: 57–102. doi:10.1016/j.entcs.2005.06.014. hdl:2144/1532. ISSN 1571-0661.

External links Standard ML with polymorphic recursion by Hans Leiß, LMU Munich

Worked examples

Example 1 — a first encounter with Polymorphic recursion

Start with the simplest possible case. Write down what Polymorphic recursion claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Polymorphic recursion before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Polymorphic recursion ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Polymorphic recursion

In research: Polymorphic recursion appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Polymorphic recursion in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Polymorphic recursion is common in secondary-school and first-year university syllabi. It links to neighbouring topics Object-oriented programming, Polymorphism (computer science), Recursion, so understanding it makes those chapters shorter.
In everyday life: Look for Polymorphic recursion outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Polymorphic recursion in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Polymorphic recursion means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Polymorphic recursion out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Polymorphic recursion in simple terms?

Why does Polymorphic recursion matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Polymorphic recursion?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Polymorphic recursion.