# Functional dependencies

### From HaskellWiki

ConradParker (Talk | contribs) (add links to tutorials about fundeps) |
(Adding kmc's example.) |
||

Line 67: | Line 67: | ||

[[User:AndrewBromage]] |
[[User:AndrewBromage]] |
||

+ | |||

+ | == Another example == |
||

+ | |||

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

+ | |||

+ | <haskell> |
||

+ | -- Read as: "container" type determines "elem" type. |
||

+ | class Extract container elem | container -> elem where |
||

+ | extract :: container -> elem |
||

+ | </haskell> |
||

+ | |||

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

+ | |||

+ | <haskell> |
||

+ | instance Extract (a,b) a where |
||

+ | extract (x,_) = x |
||

+ | </haskell> |
||

+ | |||

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

+ | |||

+ | <haskell>-- instance Extract (a,b) b where ...</haskell> |
||

+ | |||

+ | Because of the functional dependency we can say: |
||

+ | |||

+ | <haskell>v = extract ('x', 3)</haskell> |
||

+ | |||

+ | and it will infer the type <haskell>v :: Char</haskell> |
||

+ | |||

+ | 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 == |
== Tutorials == |

## Revision as of 23:01, 17 November 2009

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.

## 1 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 -}

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

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

## 2 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.

## 3 Tutorials

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