Difference between revisions of "Functional dependencies"
m (Functional dependencies moved to Functional dependency) 

(No difference)

Revision as of 17:45, 12 April 2010
Functional dependencies are used to constrain the parameters of type classes. They let you state that in a multiparameter 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.
Contents
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 (a1a2) (b1b2)
{ ... 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 (a1a2) (b1b2)
{ ... 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 multiparameter 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)
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)
 TypeLevel Instant Insanity, Conrad Parker (2007)