Personal tools

Functional dependencies

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Change category "Language" to subcategory "Language extensions")
m (Fixed a link)

Revision as of 20:02, 22 August 2007

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
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
is uniquely determined from

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