Specialization of polymorphic functions

Question

In his talk “Classes, Jim, but not as we know them” Simon Peyton-Jones talks about how type classes are implemented in GHC by having polymorphic functions taking an extra parameter that is a dictionary with the correct functions for the type(s) given to the function.

He then said that GHC often optimizes functions by special-casing functions and not actually passing this dictionary at runtime. He then said that this is not always possible because Haskell has polymorphic recursion, so even if you have the whole program, you cannot necessarily eliminate all polymorphism.

What did he mean by this? What is an example of a program where one cannot know the types a polymorphic function will be passed at compile time?

Answer 1

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.