Equivalence of functional dependencies <-> type families

fundep_to_tyfam.hs

-- First: split fundeps with multiple types on the RHS, like so:
-- LHS -> x0 x1 ... xn
-- becomes:
-- LHS -> x0, LHS -> x1, ..., LHS -> xn
-- now every fundep is of the form 'd0 d1 ... dn -> x'
-- Turn every such fundep into an open type family:
-- type family Cls_FD_k d0 d1 ... dn
-- and add an equality constraint 'x ~ Cls_FD_k d0 d1 ... dn'.
-- In some cases (generally speaking, when the fundeps do not form a cycle),
-- the type family can be inlined, replacing all uses of 'x' with 'Cls_FD_k d0 d1 ... dn'.
-- In some cases, the type family can be moved into the class.

-- Example:
class Monad m => MonadReader (r :: *) (m :: * -> *) | m -> r where ask :: m r

instance Monad m => MonadReader r (ReaderT r m) where -- ...

-- becomes:
type family MonadReader_FD_1 (m :: * -> *) :: *
class (Monad m, r ~ MonadReader_FD_1 m) => MonadReader (r :: *) (m :: * -> *) where ask :: m r
-- inline the type family:
class Monad m => MonadReader (m :: * -> *) where ask :: m (MonadReader_FD_1 m)

type instance MonadReader_FD_1 (ReaderT r m) = r
instance Monad m => MonadReader (ReaderT r m) where -- ...

-- In this case, the family can be moved into the class:
class MonadReader (m :: * -> *) where
  type MonadReader_FD_1 m :: *
  ask :: m r

instance Monad m => MonadReader (ReaderT r m) where
  type MonadReader_FD_1 (ReaderT r m) = r
  -- ...

-- A more complicated example (taken from <https://hackage.haskell.org/package/lens-4.17/docs/Control-Lens-Each.html>)
class Each s t a b | s -> a, t -> b, s b -> t, t a -> s where each :: Traversal s t a b

instance Each [a] [b] a b where -- ...

-- Create type families:
type family Each_FD_1 s :: *
type family Each_FD_2 t :: *
type family Each_FD_3 s b :: *
type family Each_FD_4 t a :: *
class (Each_FD_1 s ~ a, Each_FD_2 t ~ b, Each_FD_3 s b ~ t, Each_FD_4 t a ~ s) => Each s t a b where each :: Traversal s t a b

type instance Each_FD_1 [a] = a
type instance Each_FD_2 [b] = b
type instance Each_FD_3 [a] b = [b]
type instance Each_FD_4 [b] a = [a]
instance Each [a] [b] a b where -- ...

-- Here, there are cycles in the FDs, so we can't inline any of them.