2015-03-14

Multi-parameter type classes are used when writing a class that needs to be parameterized over two (or more) different types. When would you want to do this? Let's look at a simple example adapted from the Haskell Wikibook.

class Collection c where
    insert :: c -> e -> c

-- Make lists an instance of Collection:
instance Collection [a] where
    insert xs x = x:xs -- this doesn't work

As the Haskell Wikibook tells us, this will not compile. The e comes from nowhere. Its type is not constrained so it can be anything. The only thing we could possibly do is pass it to id. In the Collection instance, we can't cons x and xs because we do not have any assurance that xs are a list of the x type.

What we really need is a way to show that there is some relation between c and e (and therefore a relation between x and xs). This is where multi-parameter type classes come in.

Multi-Parameter Type Classes

The following code is a correct version of the above.

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
class Collection c e where
    insert :: c -> e -> c

-- Make lists an instance of Collection:
instance Collection [a] a where
    insert xs x = x:xs

This code compiles. In the Collection instance, we make sure that the c type becomes a list of a, and the e type becomes an a.

There is, however, one small problem with this code. A given c should always determine the type of e. If c is [a], then e will always be a. It will never be something else like String, Int, b, etc. How can we enforce this we we are writing our type class?

There are basically two solutions, functional dependencies and type families.

I'll give one more example to motivate this. Imagine an Add type class that represents two types that are able to be added together.

{-# LANGUAGE MultiParamTypeClasses #-}
class Add a b c where
    plus :: a -> b -> c

instance Add Integer Integer Integer where
    plus x y = x + y

-- we don't actually want to allow this
instance Add Integer Integer Double where
    plus x y = fromIntegral x + fromIntegral y

It's easy to see that the type of c will be determined based on the type of a and b. We don't actually want to allow both Add Integer Integer Integer and Add Integer Integer Double. In order to get the type system to throw an error when the user does this, we need to use either functional dependencies or type families.

Functional Dependencies

Functional Dependencies are the simpler of the two solutions.

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}
class Add a b c | a b -> c where
    plus :: a -> b -> c

instance Add Integer Integer Integer where
    plus x y = x + y

-- The following instance declaration throws an error!
-- Just like we wanted.
instance Add Integer Integer Double where
    plus x y = fromIntegral x + fromIntegral y

-- The following instance works because a and b are unique.
instance Add Integer Double Double where
    plus x y = fromIntegral x + y

In the type class definition we use a vertical bar followed by the constraints we want to impose. In a b -> c, we are saying that a and b are able to uniquely determine c.

Type Families

Type families are a much more powerful solution. It is possible to do many things with type families. I will only introduce a small use-case which will solve our problem above. The following is a solution using type families.

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE TypeFamilies #-}
class Add a b where
    type SumType a b
    plus :: a -> b -> SumType a b

instance Add Integer Integer where
    type SumType Integer Integer = Integer
    plus x y = x + y

-- The following instance declaration throws an error.
instance Add Integer Integer where
    type SumType Integer Integer = Double
    plus x y = fromIntegral x + fromIntegral y

In the class definition, we are creating a type alias SumType a b and using it in type of plus. In the instance declaration, we are assigning SumType a b to be equal to Integer, so in the class definition wherever you see SumType a b, you can replace it with Integer. Therefore, in the instance definition, the type of plus becomes Integer -> Integer -> Integer.

Conclusion

Let's go back and look at our original example. How can we write it with functional dependencies and type families?

The following is using functional dependencies.

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE FunctionalDependencies #-}
class Collection c e | c -> e where
    insert :: c -> e -> c

instance Collection [a] a where
    insert xs x = x:xs

The following is using type families.

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE TypeFamilies #-}
class Collection c where
    type CollectedType c
    insert :: c -> CollectedType c -> c

instance Collection [a] where
    type CollectedType [a] = a
    insert xs x = x:xs

Multi-parameter type classes, functional dependencies, and type families are all very powerful. When programming in Haskell, it is good to know when to use them. Lots of useful documentation can be found with a quick google search.

tags: haskell