Make injectivity check less conservative
The following injective type family fails to compile in GHC 8.0
type family Snoc (xs :: [k]) (y::k) = r | r -> xs y where
Snoc '[] y = '[y]
Snoc (x ': xs) y = x ': (Snoc xs y)The error message is
• Type family equations violate injectivity annotation:
forall k (y :: k). Snoc '[] y = '[y] -- Defined at FAlgebra.hs:49:5
forall k (xs :: [k]) (x :: k) (y :: k).
Snoc (x : xs) y = x : Snoc xs y -- Defined at FAlgebra.hs:52:5
• In the equations for closed type family ‘Snoc’
In the type family declaration for ‘Snoc’I think the problem is related to injectivity rule 5 from [this page](https://ghc.haskell.org/trac/ghc/wiki/InjectiveTypeFamilies) being too conservative. In particular, if you substitute '[] for Snoc xs y in the RHS of the second rule, then the two rules will unify but have different LHSs. This substitution is invalid, however, because the Snoc type family will never result in an empty list.
Trac metadata
| Trac field | Value |
|---|---|
| Version | 8.0.1 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | Compiler (Type checker) |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture |