Is it time to start deprecating FunDeps?

[Roman Cheplyaka]

1. What do you mean by deprecating? Deprecate it in GHC? What does it
   have to do with Haskell'?
2. What do you gain by doing so?
3. How do you translate cyclic dependencies?

Roman

* AntC <anthony_clayden at clear.net.nz> [2013-04-30 05:31:09+0000]
> 
> 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?
> 
> 
> 
> 
> _______________________________________________
> Haskell-prime mailing list
> Haskell-prime at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-prime