Functional dependencies

Functional dependencies are used to constrain the parameters of type classes. They let you state that in a multi-parameter type class, one of the parameters can be determined from the others, so that the parameter determined by the others can, for example, be the return type but none of the argument types of some of the methods.

The GHC Users Guide has Functional Dependencies section.html#{{{2}}} {{{3}}}.

Examples

Suppose you want to implement some code to perform simple linear algebra:

data Vector = Vector Int Int deriving (Eq, Show)
data Matrix = Matrix Vector Vector deriving (Eq, Show)

You want these to behave as much like numbers as possible. So you might start by overloading Haskell's Num class:

instance Num Vector where
  Vector a1 b1 + Vector a2 b2 = Vector (a1+a2) (b1+b2)
  Vector a1 b1 - Vector a2 b2 = Vector (a1-a2) (b1-b2)
  {- ... and so on ... -}

instance Num Matrix where
  Matrix a1 b1 + Matrix a2 b2 = Matrix (a1+a2) (b1+b2)
  Matrix a1 b1 - Matrix a2 b2 = Matrix (a1-a2) (b1-b2)
  {- ... and so on ... -}

The problem comes when you want to start multiplying quantities. You really need a multiplication function which overloads to different types:

(*) :: Matrix -> Matrix -> Matrix
(*) :: Matrix -> Vector -> Vector
(*) :: Matrix -> Int -> Matrix
(*) :: Int -> Matrix -> Matrix
{- ... and so on ... -}

How do we specify a type class which allows all these possibilities?

We could try this:

class Mult a b c where
  (*) :: a -> b -> c

instance Mult Matrix Matrix Matrix where
  {- ... -}

instance Mult Matrix Vector Vector where
  {- ... -}

That, however, isn't really what we want. As it stands, even a simple expression like this has an ambiguous type unless you supply an additional type declaration on the intermediate expression:

m1, m2, m3 :: Matrix
(m1 * m2) * m3              -- type error; type of (m1*m2) is ambiguous
(m1 * m2) :: Matrix * m3    -- this is ok

After all, nothing is stopping someone from coming along later and adding another instance:

instance Mult Matrix Matrix (Maybe Char) where
  {- whatever -}

The problem is that c shouldn't really be a free type variable. When you know the types of the things that you're multiplying, the result type should be determined from that information alone.

You can express this by specifying a functional dependency, or fundep for short:

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

This tells Haskell that c is uniquely determined from a and b.

Fundeps have lots more uses than just implementing C++-style function overloading, of course. See the paper by Mark P. Jones for further details.

Fundeps are not standard Haskell 98. (Nor are multi-parameter type classes, for that matter.) They are, however, supported at least in GHC and Hugs and will almost certainly end up in Haskell'.

Another example

The following example makes use of the FlexibleInstances, MultiParamTypeClasses and FunctionalDependencies GHC extensions.

-- Read as: "container" type determines "elem" type.
class Extract container elem | container -> elem where
  extract :: container -> elem

The functional dependency "container -> elem" promises that we won't declare multiple instances with the same "container" type.

instance Extract (a,b) a where
  extract (x,_) = x

Because of the functional dependency we can't have the previous instance *and* this one:

-- instance Extract (a,b) b where ...

Because of the functional dependency we can say:

v = extract ('x', 3)

and it will infer the type

v :: Char

Without the functional dependency, both instances above would be allowed, and the type of v would be potentially ambiguous. Even if only one instance is defined, the type system will not figure it out without the functional dependency.

Tutorials

• Fun with functional dependencies, Thomas Hallgren (2001)
• Type-Level Instant Insanity, Conrad Parker (2007)

See also

• GHC documentation
• Functional dependencies vs. type families