Type Classes with Functional Dependencies by Mark Jones.

This is an old paper we studied long ago and functional dependency in type classes is not new to me. But Steve asked a very good question today. We are currently required to explicitly declare the functional dependency in a multi-parameter type class definition if one or more type variables are not mentioned in some members. Is it possible for the compiler to infer this automatically? Now the problems reamining:

• Does there exist a least constrained dependency among all dependencies that can make overloading resolvable in a type class? My first intuition is yes and all the dependencies form a complete partial order.
• If so, does there exist a decidable algorithm to find out?

We need to formally define the semantics of the dependencies and try to find an algorithm or disprove the existence.