Functional Dependencies

Brief Explanation

References

•  Type Classes with Functional Dependencies (paper) by Mark P. Jones, in ESOP 2000. A semi-formal description of a more restricted system than implemented by GHC and Hugs.
•  Sound and Decidable Type Inference for Functional Dependencies by Gregory J. Duck, Simon Peyton Jones, Peter J. Stuckey and Martin Sulzmann, in ESOP 2004. ( extended version)
•  Description from the GHC User's manual.
•  Problem with functional dependencies (email) by Simon Peyton Jones - is there a conclusion here? Further work?

Tickets

#36

add FunctionalDependencies

#90

solve the MultiParamTypeClassDilemma

Pros

• In GHC and Hugs for a long time.

Cons

• Recently, some problems with FDs have been identified, see also the material on AssociatedTypes.
• There are (at least) three different versions of FDs:
  1. Mark Jones' original proposal. Problem: It excludes some uses of FDs.
  2. GHC's implementation. Problem: It makes type checking undecidable. (See Duck et al. for an example.)
  3. Chameleon's implementation. Problem: Needs type inference based on constraint handling rules (not just HM). Doesn't support separate compilation atm.