Skip to content

Type equality unification shortcoming

The following program demonstrates cases where the equality f a ~ g b is not enough for the type checker to deduce f ~ g and a ~ b.

{-# LANGUAGE GADTs, TypeOperators, KindSignatures, PolyKinds, TypeFamilies, RankNTypes #-}
data a :=: b where Refl :: a :=: a
type family Arg x
type instance Arg (f x) = x
type family Func (x :: *) :: * -> *
type instance Func (f x) = f

congArg :: x :=: y -> Arg x :=: Arg y
congArg Refl = Refl
congFunc :: x :=: y -> Func x :=: Func y
congFunc Refl = Refl
inversion :: forall (f :: * -> *)(g :: * -> *)(a :: *)(b :: *). 
             f a :=: g b -> (f :=: g , a :=: b)
--inversion Refl = (Refl, Refl) -- Doesn't type check!
inversion eq = (congFunc eq , congArg eq) -- Does type check

-- Even simpler example that doesn't type check
-- foo :: f a ~ g b => f () -> g ()
-- foo x = x
Trac metadata
Trac field Value
Version 7.6.1
Type Bug
TypeOfFailure OtherFailure
Priority normal
Resolution Unresolved
Component Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information