Here's a typical example of polymorphic recursion. Let's say we have a data type similar to a list, but each element has a type twice as "big" as the previous one:
data Poly a = Nil | Cons a (Poly (a,a)) deriving Show
foo :: Poly Int
foo = Cons 3 (Cons (4,5) (Cons ((6,7),(8,9)) Nil))
length' :: Poly a -> Int
length' Nil = 0
length' (Cons _ xs) = 1 + length' xs
Notice that the recursive call to length'
has a different type from the original call.
Since it's impossible to know statically which such lists might be created, we can't eliminate all dictionaries from the program.