Version 17 (modified by ross@…, 9 years ago) (diff)


Functional Dependencies

Brief Explanation

Functional dependencies (borrowed from relational databases) restrict the instances of a multi-parameter type class, e.g.

class ... => C a b c | a -> b

says that any two instances of C that agree in the first parameter must also agree in the second. They are a partial solution to the following problems with MPTCs:

  • ambiguity
  • imprecise types and late error reporting, arising from deferred context reduction (see FlexibleContexts).



add FunctionalDependencies
solve the MultiParamTypeClassDilemma


  • In GHC and Hugs for a long time.
  • Used in important libraries, notably monad transformers.
  • MultiParamTypeClasses are of limited use without functional dependencies or something equivalent.


  • There are (at least) three different versions of FDs, none of which is satisfactory:
    1. Mark Jones's original proposal. Problem: It excludes some uses of FDs (see below).
    2. GHC's implementation. Problem: It makes type checking undecidable (see below).
    3. Chameleon's implementation. Problem: Needs type inference based on constraint handling rules (not just HM). Doesn't support separate compilation atm.
  • Including the dependent type parameters makes types more cluttered, and prevents hiding of these types (see AssociatedTypes).
  • AssociatedTypes seem to be more promising.

Original Proposal

This is the system proposed in the original paper, with names according to the FD-CHR paper. Suppose a class C has a functional dependency X -> Y.

Restrictions on instances

The original paper imposed two restrictions on instances of the class C (sect. 6.1):

  1. Coverage. For any instance
    instance ... => C t
    any variable occurring free in tY must also occur free in tX.
  1. Consistency. If there is a second instance
    instance ... => C s
    then any substitution unifying tX with sX must also unify tY with sY.

Haskell 98 requires that the context of an instance declaration use only type variables that appear in the head. It was originally thought that this could be relaxed (original paper, sect. 6.3), to variables determined by those in the head, but this can lead to non-termination (CHR paper, ex. 16).

Improvement of inferred types

"Improvement", as used by Mark Jones, means using information about what instances could match a predicate to instantiate its type variables, or to fail. Note that since context reduction is deferred (see FlexibleContexts), this refers not to what instances are available, but what instances are possible.

A functional dependency X -> Y allows two improvement rules:

  1. FD improvement. If a context contains predicates C t and C s such that tX = sX, infer tY = sY.
  2. Instance improvement. Given a predicate C s and an instance declaration
    instance ... => C t
    such that sX = S tX for some substitution S, infer sY = S tY. (This rule is justified by the above "consistency" condition.)


With FlexibleInstances and no OverlappingInstances, this system is coherent and decidable (CHR paper, corr. 1).

Unfortunately the "coverage" condition rules out instances like the following, from the monad transformer library:

class (Monoid w, Monad m) => MonadWriter w m | m -> w
instance MonadWriter w m => MonadWriter w (ReaderT r m)

GHC and Hugs

GHC and Hugs implement the following relaxed version of the above "coverage" condition:

  1. Dependency. For any instance
    instance ctxt => C t
    any variable occurring free in tY must be dependent (using dependencies of classes in the context) on variables that occur free in tX.

They thus accept instances like the above MonadWriter example. Unfortunately, this relaxation breaks the guarantees of termination and coherence.

Loss of termination

The following instances (CHR paper, ex. 6) seem reasonable:

class Mul a b c | a b -> c where
        (.*.) :: a -> b -> c

instance Mul Int Int Int where (.*.) = (*)
instance Mul Int Float Float where x .*. y = fromIntegral x * y
instance Mul a b c => Mul a [b] [c] where x .*. v = map (x.*.) v

and yet instance inference fails to terminate for the following (erroneous) definition:

f = \ b x y -> if b then x .*. [y] else y

Loss of confluence

The following instances (adapted from CHR paper, ex. 18) are sensitive to the order in which rules are applied:

class B a b | a -> b
class C a b c | a -> b where f :: a -> b -> c -> Bool

instance B a b => C [a] [b] Bool

Given the constraint C [a] [b] Bool, C [a] [c] d,

  • if we apply the dependency first, and then reduce using the instances, we obtain b = c, B a b, C [a] [b] d.
  • if we first reduce using the instances, we obtain B a b, C [a] [c] d.

(GHC and Hugs yield the former, because they defer context reduction: see FlexibleContexts).

Proposed Fixes

The following are alternatives.

Modified coverage condition

The following complex relaxation of the "coverage" condition is safe (CHR paper, sect. 6), and allows the instances in the monad transformer library:

  1. For any instance
    instance ... => C t
    • any variable occurring free in tY must also occur free in tX, or
    • the functional dependency is full (involves all the arguments of the class), and the arguments tY are type variables determined by the free variables of tX.

The fullness condition restores confluence, while the variable argument condition restores termination.

Note that functional dependencies corresponding to associated type synonyms are always full.

Modified instance improvement

Assume the dependency condition in place of coverage. For an instance

instance ... => C t

if tY is not covered by tX, then for any constraint C s with sX = S tX, there cannot be another matching instance (as it would violate the consistency condition). Hence we can unify s with S t. Local confluence is straight-forward. (In the above confluence example, d is instantiated to Bool and both alternatives reduce to b = c, d = Bool, B a b).

A restriction on instances to guarantee termination would also be needed.

Attachments (1)

Download all attachments as: .zip