Haskell: nonobvious examples of functional dependencies

Question

The examples of functional dependencies I've seen boil down to mapping container -> element, and arguments -> result (as in Mult Matrix Vector Vector). They seem to be better expressed with type functions. In database theory, more complex relationships are considered that are not of this form (like a -> b, b -> a).

Are there examples of usage of FDs in Haskell that cannot be nicely written using type functions?

Answer 1

As Manuel Chakravarty explains, type functions and functional dependencies have roughly the same expressiveness, you can translate one formulation into the other. They only begin to differ when you look at interaction with other language extensions like GADTs or UndecidableInstances. I gather that type families are currently favored for implementation in GHC because their interaction with GADTs and existential types is substantially simpler.

Answer 2

As Heinrich Apfelmus already said MPTC+FunDeps and TF alone are equivalent. Differences arise when they are combined with other extensions in particular with overlapping instances. TF are unsound when overlapping is permitted while FunDeps allow overlapping. For example it's easy implement type equality with FunDeps:

data HTrue
data HFalse

class  TypeEq a b eq | a b -> eq
instance                TypeEq a a HTrue
instance eq ~ HFalse => TypeEq a b eq

Key point here is overlapping. In principle it's possible to implement type equality without overlapping but it will require compiler support. That approach is described by Oleg here: http://okmij.org/ftp/Haskell/typeEQ.html

P.S. There was lengthy discussion on haskell-prime mailing list on this subject.