Yeah, when first starting out it can be tempting to gloss over all of the constraints and classes stuff as being mathematically solved by the compiler, but if you’re trying to build up an understanding of how this actually works, it’s best to learn the actual algorithm used, which is far more limited in power than high-school algebra.
First, start with single-parameter type classes. When a constraint needs to be solved, and the class of the constraint has one type parameter, the compiler looks at what it knows about the type given to that parameter—it might be entirely unknown, or it might have a head—for example, the head of the type Array Int is Array, and the head of the type String -> Maybe Int is Function (because String -> Maybe Int is just the infix notation for Function String (Maybe Int)). The compiler then looks in the module of the class and the module of the head of the parameter, if any, for instances that could match the parameter type. If a single unambiguous match is found, it is used, and any constraints on that instance are now themselves solved. Otherwise, an error is raised; no attempt is made to backtrack or otherwise refine the search. (I’m ignoring instance chains for the moment but they don’t complicate the story much.)
Next, graduate to multi-parameter type classes, which are solved similarly, except now there are multiple parameters to consider. Every parameter may or may not contribute a head, and every head contributed has its module searched. An instance needs to match all of the parameters in order to be considered. For example, if you’re looking for a solution to Foo Int t, where t is an unknown type, and there is an instance of type Foo Int String, the compiler won’t consider that a match, because t may or may not actually be String—it’s unknown! Again, if there is a single unambiguous match, the compiler can proceed, and otherwise it raises an error.
Now we can explain functional dependencies, which only apply to multi-parameter type classes. The main practical effect of a functional dependency is to change the above algorithm such that not all of the parameters in a constraint need to match—only enough parameters to cover all the others with fundeps! So to revisit the previous example, if the Foo class was defined as class Foo a b | a -> b, that means that a is sufficient when looking for a match, because b can then be covered by the a -> b fundep. Foo Int t now can be solved with a Foo Int String instance, and the compiler will unify t with String and proceed. (Of course, unifying t and String may not end up being possible in the context of the rest of the program, which will cause a different error to be raised.) In order for this to not break instance coherence—roughly, the idea that there’s only ever one way to use instances to solve constraints—functional dependencies also add an additional restriction on how instances can be defined. In the running example, it’s now illegal to define both a Foo Int String instance and a Foo Int Boolean instance, whereas that would have been legal without the fundep.
If all this stuff reminds you of how you solve algebraic equations or how mathematical relations work, that can be a good source of intuition—but don’t expect the compiler to solve anything other than by following the rote steps outlined above!
. Maybe someone more knowledgable can explain how