In the past few months I have learnt a lot! Probably the coolest stuff has been about Functional Dependencies and Type Families, so this is my attempt to explain it in order to gain a better understanding and hopefully help someone else out there as well.

So please be kind if you see any mistake, let me know and I’ll try to fix it :)

A motivating example

One of the fun applications I’ve worked on is exchange-rates, which uses the RIO Monad (basically ReaderT + IO).

When defining dependencies using such effect is very common to do it using the Has typeclass approach (or how I prefer to call it, the classy lenses Has pattern) instead of passing the whole context / environment.

Following this approach, I have defined a polymorphic Ctx record that represents the application context (or dependencies). It looks as follows:

data Ctx m = Ctx
  { ctxLogger :: Logger m
  , ctxCache :: Cache m
  , ctxForexClient :: ForexClient m
  }

If we continue with the Has approach we would get something like this for our Logger m:

class HasLogger ctx where
  loggerL :: Lens' ctx (Logger m)

instance HasLogger (Ctx m) where
  loggerL = lens ctxLogger (\x y -> x { ctxLogger = y })

But… Oops, it doesn’t compile!

Couldn't match type ‘m1’ with ‘m’
      ‘m1’ is a rigid type variable bound by
        the type signature for:
          loggerL :: forall (m1 :: * -> *). Lens' (Ctx m) (Logger m1)
        at src/Context.hs:27:3-9
      ‘m’ is a rigid type variable bound by
        the instance declaration
        at src/Context.hs:26:10-47

The reason is that the compiler has no way to know that the m in Logger m (declared in the type class) is the same as the m in Ctx m (declared in the instance), therefore the inferred type ends up being Lens' (Ctx m) (Logger m1).

Functional Dependencies to the rescue

We can fix it by introducing a language extension named FunctionalDependencies, introduced in the paper Type Classes with Functional Dependencies by Mark P. Jones in March 2000.

We need to change our type class definition as below:

{-# LANGUAGE FlexibleInstances      #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE MultiParamTypeClasses  #-}

class HasLogger ctx m | ctx -> m where
  loggerL :: Lens' ctx (Logger m)

instance HasLogger (Ctx m) m where
  loggerL = lens ctxLogger (\x y -> x { ctxLogger = y })

Our type class has now two parameters, ctx and m, and in addition we define a functional dependency ctx -> m. This means that ctx uniquely determines the type of m, which constraints the possible instances and helps with type inference.

Notice the extensions we had to enable to make this compile.

Arithmetic example

Here’s another example taken from the Fun with Functional Dependencies paper by Thomas Hallgren. What’s simpler that adding two values together?

class Add a b c | a b -> c where
  add :: a -> b -> c

instance Add Zero b b
instance Add a b c => Add (Succ a) b (Succ c)

The functional dependency is pretty clear: given a and b we can add them together and produce c. So a and b uniquely determine c.

Notice how we don’t even need to define add, specifying the types is enough! If it’s still not clear, bear with me and let’s perform type substitution step by step (feel free to skip this part):

Given this instance, all we are saying is that:

instance Add Zero b b where

• a is defined as Zero.
• b is defined as b.
• c is defined as b.

Since we now know the types of a, b and c, defining the add function becomes redundant:

instance Add Zero b b where
  add Zero b = b

Clear now? Awesome! Let’s try this out in the REPL:

λ :t add (u::Three) (u::Zero)
Succ (Succ (Succ Zero))

Where u = undefined, just a convenient type alias.

Functional Dependencies have proven to be very useful since it solves a real problem. But software evolves and so Type Families were created, the topic of the next section.

Type Families

Type Families were introduced in the paper Fun with type functions by Oleg Kiselyov, Simon Peyton Jones and Chung-chieh Shan in May 2010.

This GHC extension allows functions on types to be expressed as straightforwardly as functions on values. This means that our functions are executed at compile time, during type checking.

So here’s how we can define our HasLogger class using Type Families instead:

{-# LANGUAGE TypeFamilies #-}

import Data.Kind (Type)

class HasLogger ctx where
  type LoggerF ctx :: Type -> Type
  loggerL :: Lens' ctx (Logger (LoggerF ctx))

instance HasLogger (Ctx m) where
  type LoggerF (Ctx m) = m
  loggerL = lens ctxLogger (\x y -> x { ctxLogger = y })

Our class has once again a single parameter ctx and our functional dependency is now expressed as an associated type of the class (type family). It behaves like a function at the type level, so we can call LoggerF a type function.

Notice how we explicitly define the kind of our type function to be Type -> Type (formerly * -> *). If we don’t do it the default inferred kind will just be Type (formerly *).

Arithmetic example

In a similar way, we can define the Add class using Type Families:

class Add a b where
  type AddF a b :: Type
  add :: a -> b -> AddF a b

instance Add Zero b where
  type AddF Zero b = b

instance Add a b => Add (Succ a) b where
  type AddF (Succ a) b = Succ (AddF a b)

The c parameter defined before is now replaced by the AddF a b type function. Here we define the kind of the type function as a good practice but it’s not necessary.

And again, we can try this out in the REPL:

λ :t add (u::Three) (u::Succ Zero)
Succ (Succ (Succ (Succ Zero)))

Polymorphic Mutable Ref

Furthermore, with Type Families we could define a polymorphic mutable ref class where m defines Ref (example taken from the paper Fun with type functions linked above).

class Mutation m where
  type Ref m :: Type -> Type
  newRef   :: a -> m (Ref m a)
  readRef  :: Ref m a -> m a
  writeRef :: Ref m a -> a -> m ()

instance Mutation IO where
  type Ref IO = IORef
  newRef   = newIORef
  readRef  = readIORef
  writeRef = writeIORef

instance Mutation (ST s) where
  type Ref (ST s) = STRef s
  newRef   = newSTRef
  readRef  = readSTRef
  writeRef = writeSTRef

Once the compiler knows what m is it’s over. It’ll know what the type of the mutable ref is as well. And as a bonus, type inference will work flawlessly.

Final Thoughts

Most use cases of FunctionalDependencies can be expressed using TypeFamilies, however there are some subtle differences that come to light only in complex scenarios.

Most library authors and developers prefer to use TypeFamilies nowadays. Its main advantage over FunctionalDependencies is speed but it’s also possible to express many cases that require the extensions TypeSynonymInstances, FlexibleInstances, MultiParamTypeClasses and UndecidableInstances without them.

So when is it more convenient to use the former? You can find a more detailed comparison in the following articles:

• https://wiki.haskell.org/Functional_dependencies_vs._type_families
• https://gitlab.haskell.org/ghc/ghc/wikis/tf-vs-fd

Special thanks to Dmitrii Kovanikov for reviewing the first draft!