Skip to content

GitLab

  • Menu
Projects Groups Snippets
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Sign in / Register
  • GHC GHC
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
    • Locked Files
  • Issues 4,866
    • Issues 4,866
    • List
    • Boards
    • Service Desk
    • Milestones
    • Iterations
  • Merge requests 451
    • Merge requests 451
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
    • Test Cases
  • Deployments
    • Deployments
    • Releases
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Code review
    • Insights
    • Issue
    • Repository
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • Glasgow Haskell Compiler
  • GHCGHC
  • Issues
  • #12114
Closed
Open
Created May 24, 2016 by MikeIzbicki@trac-MikeIzbicki

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
Edited Mar 10, 2019 by Richard Eisenberg
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information
Assignee
Assign to
Time tracking