Functional dependencies

From HaskellWiki
Revision as of 04:11, 11 September 2007 by ConradParker (talk | contribs) (add links to tutorials about fundeps)
Jump to: navigation, search

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.


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'.