[1] 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.
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.
144–146) gives a CONS example in Haskell wherein the polymorphic type system automatically flags programmer errors.
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.