Polymorphic recursion - syntax and uses?

Question

I've spent significant time looking over learnyouahaskell and I haven't found a good explanation of polymorphic recursion!

I understand basic recursive structures:

myFunction :: [Int] -> [Int]
myFunction [] = []
myFunction (x : xs) = (\x -> x + 1) x : myFunction xs

What would polymorphic recursion look like? And what are its benefits/uses?

Answer 1

Type inference for polymorphic recursion is undecidable, meaning the compiler cannot infer the type of such a function even when it is well-typed.

For example, an ordinary list applies List to the same (polymorphic) type on both sides:

data List a = Cons a (List a)

while this type taken from the Wikipedia article applies Nested to two different (polymorphic) types, a and [a]:

data Nested a = a :<: (Nested [a]) | Epsilon

From the same article, the compiler will fail to infer the type of a relatively straightforward length function

length Epsilon = 0
length (a :<: xs) = 1 + length xs

because length is applied to values of two different types in the second equation, Nested a and Nested [a].

The solution is to assert that the type is indeed Nested a -> Int.

length :: Nested a -> Int
length Epsilon = 0
length (a :<: xs) = 1 + length xs