Is it time to start deprecating FunDeps?

[AntC]

Now that the Type Equality coercions extension is stable and has been 
blessed by SPJ as "a functional-dependency-like mechanism (but using 
equalities) for the result type" [in 
http://hackage.haskell.org/trac/ghc/wiki/Records/OverloadedRecordFields#Hig
herranktypesandtypefunctions],
no code is compelled to use FunDeps.

[Note that this is orthogonal to the issue of overlaps. You can use the 
equalities mechanism happily with overlaps, see example below.
 This is also orthogonal to type functions/families/associated types. You 
can use the equalities mechanism happily without type families.]

There's plenty of code using FunDeps, so we couldn't just withdraw the 
extension. But we could start deprecating it.

Better still, given that there is a mechanical way to convert FunDeps to 
equalities, we could start treating the FunDep on a class declaration as 
documentation, and validate that the instances observe the mechanical 
translation.

Here's an example of the mechanical translation for HDeleteMany, the 
classic awkward example from HList.

The problem is to delete all occurences of element type e in a HList l. 
Here's the 'non-solution' naieve attempt from the HList paper:

    class HDeleteMany e l l' | e l -> l'
    instance HDeleteMany a HNil HNil       -- base case OK
    instance (HList l, HDeleteMany e l l')
          => HDeleteMany e (HCons e l) l'  -- element match, so omit
    instance (HList l, HDeleteMany e l l')
          => HDeleteMany e (HCons e' l) (HCons e' l')
                                           -- element not match, so retain
                                           -- + recurse on the tail

"The two overlapping instance heads for HCons are in no substitution 
ordering."

Here's the mechanical translation, which _does_ compile:

    class HDeleteMany e l l'                -- | e l -> l'
    instance (HNil ~ l')                    -- force the result
          => HDeleteMany a HNil l'          -- base case OK
    instance (HList l, HDeleteMany e l l')
          => HDeleteMany e (HCons e l) l'   -- same as above
    instance (HList l, HDeleteMany e l l'', (HCons e' l'') ~ l')
          => HDeleteMany e (HCons e' l) l'  -- force the result

The translation rules (applying for the 'target' term of a FunDep) are:
1. If the target is a bare typevar not appearing otherwise in the head,
   we're done OK.
Otherwise:
2. Replace the target with a fresh typevar.
   (This forces instance match without inspecting the use site.)
3. Add a type equality constraint
   equating the fresh typevar with the as-was target term.
   (This forces the result type, in the same way as a FunDep target.)


Possible GSOC project?