[GHC] #13657: Documentation: Functional dependencies by other means

[GHC]

#13657: Documentation: Functional dependencies by other means
-------------------------------------+-------------------------------------
           Reporter:  AntC           |             Owner:  (none)
               Type:  bug            |            Status:  new
           Priority:  normal         |         Milestone:
          Component:  Documentation  |           Version:  8.0.1
           Keywords:                 |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  Documentation
  Unknown/Multiple                   |  bug
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:  10431
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 There's an idiom that's briefly mentioned under Equality constraints
 [section 10.14.1], but is more general and more powerful.

 The trouble: is where to document it? Because you get the power from a
 combination of extensions:
 * -XMultiParamTypeClasses [10.8.1.1]
 * Superclass constraints, which can also be MultiParam [10.8.1.2]
 * -XFunctionalDependencies [10.8.2]
 * and/or superclass Equality constraints with Type families, having the
 effect of FunDeps [10.14.1]
 * The overall effect can satisfy the FunDep Coverage conditions, which
 means you might not need -XUndecidableInstances [10.8.3.5]

 10.14.1 says:
 > Equality constraints can also appear in class and instance contexts. The
 former enable a simple translation of programs using functional
 dependencies into programs using family synonyms instead.

 That's not wrong; but by talking about "class and instance contexts" in
 the same breath does fail to emphasise that:
 * whereas Instance constraints don't apply until after the instance has
 been selected\\(And it's a common newbie mistake to think they restrict
 the selection.)
 * superclass constraints apply during type improvement __before__
 selecting instances\\as described here
 http://stackoverflow.com/questions/35252562/find-an-element-in-an-
 hlist/35260970#35260970 "superclass context is critical ..." [thanks
 @DFeuer]
 * This behaviour means that even if you don't explicitly put a FunDep `|
 ... -> ...` on a class:
  * If you put a superclass equality constraint on a class, that induces a
 FunDep as explained in 10.14.1; but just as much
  * If you put a superclass __class__ constraint on a class, and that
 superclass has a FunDep, that also induces a FunDep.
  * and so on for a superclass constraint of a superclass constraint of a
 superclass constraint ....


 I suggest the bulk of the write-up goes under a new sub-section for
 FunDeps:

 ----

 == 10.8.2.3 Functional dependency-like behaviour through superclass
 constraints

 Constraints in the class context can achieve the effect of Functional
 dependencies even without the explicit vertical bar and dependency arrow
 syntax in the class declaration. Either:

 * Using an Equality constraint to a Type family [10.14.1]; or
 * A superclass constraint that does have an explicit Functional
 dependency.
 * Or a superclass constraint which is itself constrained in one of those
 ways.

 A class declaration of the form
 {{{
 class C a b | a -> b
 }}}
 can equivalently be given as
 {{{
 class (F a ~ b) => C a b where
   type F a
 }}}
 That is, we represent every functional dependency (FD) `a1 .. an -> b` by
 an FD type family `F a1 .. an` and a superclass context equality `F a1 ..
 an ~ b`, essentially giving a name to the functional dependency. [See
 10.14.1; using `(~)` needs -XTypeFamilies or -XGADTs.]  In class
 instances, we define the type instances of FD families in accordance with
 the class head.

 Or class `C` can equivalently be given as
 {{{
 class (D a b) => C a b ...

 class D a b | a -> b
 -- or
 class (G a ~ b) => D a b where
   type G a
 }}}
 The class instances for `D` will closely follow those for `C`. So there is
 not much gain in expressivity. Consider also:
 {{{
 class (D a c) => E a b c ...

 -- class D as above
 }}}
 for which the `D` instances will be more compact than `E`.

 Note that `D` might not declare any methods, but merely be used for type
 improvement.

 Method signatures for class `C` are not affected by either of these ways
 for achieving dependencies.

 ----

 Reference this thread: https://mail.haskell.org/pipermail/glasgow-haskell-
 users/2017-April/026515.html, with some fancier examples of pseudo-
 FunDeps.

 See also #10431.

 Is this power made clear in the theoretical literature? It's kinda
 implicit in the TypeFamilies2008 paper; but note that was written
 concurrently with Type Families development; and published before the work
 was completed. Specifically, supporting Type Families and `(~)` in
 superclass constraints was delivered a long time after the rest of the
 work.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13657>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler