kind-apply-0.4.0.0: Utilities to work with lists of types
Safe HaskellNone
LanguageHaskell2010

Data.PolyKinded.Atom

Description

Atoms represent the shape of a type, possibly with variables, which can be Interpreted given a list of types.

Synopsis

Atoms

data Atom d (k :: TYPE r) where Source #

Shape of a type, possibly with type variables.

>>> :kind Kon [] :@: Var0 -- the type [a] for unknown a
Kon [] :@: Var0 :: Atom (* -> xs) *

Representation of type families

Expand

Type families are represented using first-class-families.

For example, the type-level n + m :: Nat-- may expand to the following--

n + m         -- using (+) from GHC.TypeNats
~
Eval (n + m)  -- using Eval from Fcf.Core and (+) from Fcf.Data.Nat

which may be encoded as the following Atom (using Var0 for n and Var1 for m):

Eval ((Kon (+) :@: Var0) :@: Var1)  -- Eval as Atom's constructor
  :: Atom (Nat -> Nat -> Type) Nat

kind-generics uses a different, more systematic encoding of type families for GenericK instances; see fcf-family for more details. For example, n + m is instead expanded to the following:

n + m
~
Eval (NDFamily (MkName "base" "GHC.TypeNats" "+") P0 '(n, '(m, '())))

which gets encoded as the following Atom:

Eval (Kon (NDFamily (MkName "base" "GHC.TypeNats" "+") P0)
        :@: ((Kon '(,) :@: Var0) :@: ((Kon '(,) :@: Var1) :@: Kon '())))
  :: Atom (Nat -> Nat -> Type) Nat

Constructors

Var :: forall d k1. TyVar d k1 -> Atom d k1

Represents a type variable.

Kon :: forall k1 d. k1 -> Atom d k1

Represents a constant type, like Int.

(:@:) :: forall d k1 k2. Atom d (k1 -> k2) -> Atom d k1 -> Atom d k2

Represents type application.

(:&:) :: forall d. Atom d Constraint -> Atom d Constraint -> Atom d Constraint infixr 5

Represents the conjunction of two constraints.

ForAll :: forall d1 d. Atom (d1 -> d) Type -> Atom d Type

Represents universal quantification.

(:=>>:) :: forall d. Atom d Constraint -> Atom d Type -> Atom d Type infixr 5

Represents constraint requirement, the "thick arrow" =>.

Eval :: forall d k1. Atom d (Exp k1) -> Atom d k1

Represents a type family application.

type (:$:) (f :: k1 -> k2) (x :: Atom d k1) = ('Kon f :: Atom d (k1 -> k2)) ':@: x Source #

Represents an applied constructor. Instead of Kon [] :: Var0$ you can write @[] :$: Var0$.

type (:~:) (a :: Atom d k1) (b :: Atom d k1) = (('Kon ((~) :: k1 -> k1 -> Constraint) :: Atom d (k1 -> k1 -> Constraint)) ':@: a) ':@: b Source #

Represents (homogeneous) type equality.

type (:~~:) (a :: Atom d k1) (b :: Atom d k2) = (('Kon ((~~) :: k1 -> k2 -> Constraint) :: Atom d (k1 -> k2 -> Constraint)) ':@: a) ':@: b Source #

Represents heterogeneous type equality.

Type variables

data TyVar d (k :: TYPE r) where Source #

Well-scoped de Bruijn representation of type variables. TyVar d represents all the possible type variables which can refer to the holes in kind d.

We recommend using the aliases Var0, Var1, ... instead of the constructors, for further clarity.

Constructors

VZ :: forall x xs. TyVar (x -> xs) x

First hole in d.

VS :: forall xs k1 x. TyVar xs k1 -> TyVar (x -> xs) k1

Successor hole, increases the hole reference by 1.

Aliases for specific variables

type Var0 = 'Var ('VZ :: TyVar (k -> xs) k) Source #

type Var1 = 'Var ('VS ('VZ :: TyVar (k -> xs) k) :: TyVar (x -> k -> xs) k) Source #

type Var2 = 'Var ('VS ('VS ('VZ :: TyVar (k -> xs) k) :: TyVar (x1 -> k -> xs) k) :: TyVar (x -> x1 -> k -> xs) k) Source #

type Var3 = 'Var ('VS ('VS ('VS ('VZ :: TyVar (k -> xs) k) :: TyVar (x2 -> k -> xs) k) :: TyVar (x1 -> x2 -> k -> xs) k) :: TyVar (x -> x1 -> x2 -> k -> xs) k) Source #

type Var4 = 'Var ('VS ('VS ('VS ('VS ('VZ :: TyVar (k -> xs) k) :: TyVar (x3 -> k -> xs) k) :: TyVar (x2 -> x3 -> k -> xs) k) :: TyVar (x1 -> x2 -> x3 -> k -> xs) k) :: TyVar (x -> x1 -> x2 -> x3 -> k -> xs) k) Source #

type Var5 = 'Var ('VS ('VS ('VS ('VS ('VS ('VZ :: TyVar (k -> xs) k) :: TyVar (x4 -> k -> xs) k) :: TyVar (x3 -> x4 -> k -> xs) k) :: TyVar (x2 -> x3 -> x4 -> k -> xs) k) :: TyVar (x1 -> x2 -> x3 -> x4 -> k -> xs) k) :: TyVar (x -> x1 -> x2 -> x3 -> x4 -> k -> xs) k) Source #

type Var6 = 'Var ('VS ('VS ('VS ('VS ('VS ('VS ('VZ :: TyVar (k -> xs) k) :: TyVar (x5 -> k -> xs) k) :: TyVar (x4 -> x5 -> k -> xs) k) :: TyVar (x3 -> x4 -> x5 -> k -> xs) k) :: TyVar (x2 -> x3 -> x4 -> x5 -> k -> xs) k) :: TyVar (x1 -> x2 -> x3 -> x4 -> x5 -> k -> xs) k) :: TyVar (x -> x1 -> x2 -> x3 -> x4 -> x5 -> k -> xs) k) Source #

type Var7 = 'Var ('VS ('VS ('VS ('VS ('VS ('VS ('VS ('VZ :: TyVar (k -> xs) k) :: TyVar (x6 -> k -> xs) k) :: TyVar (x5 -> x6 -> k -> xs) k) :: TyVar (x4 -> x5 -> x6 -> k -> xs) k) :: TyVar (x3 -> x4 -> x5 -> x6 -> k -> xs) k) :: TyVar (x2 -> x3 -> x4 -> x5 -> x6 -> k -> xs) k) :: TyVar (x1 -> x2 -> x3 -> x4 -> x5 -> x6 -> k -> xs) k) :: TyVar (x -> x1 -> x2 -> x3 -> x4 -> x5 -> x6 -> k -> xs) k) Source #

type Var8 = 'Var ('VS ('VS ('VS ('VS ('VS ('VS ('VS ('VS ('VZ :: TyVar (k -> xs) k) :: TyVar (x7 -> k -> xs) k) :: TyVar (x6 -> x7 -> k -> xs) k) :: TyVar (x5 -> x6 -> x7 -> k -> xs) k) :: TyVar (x4 -> x5 -> x6 -> x7 -> k -> xs) k) :: TyVar (x3 -> x4 -> x5 -> x6 -> x7 -> k -> xs) k) :: TyVar (x2 -> x3 -> x4 -> x5 -> x6 -> x7 -> k -> xs) k) :: TyVar (x1 -> x2 -> x3 -> x4 -> x5 -> x6 -> x7 -> k -> xs) k) :: TyVar (x -> x1 -> x2 -> x3 -> x4 -> x5 -> x6 -> x7 -> k -> xs) k) Source #

type Var9 = 'Var ('VS ('VS ('VS ('VS ('VS ('VS ('VS ('VS ('VS ('VZ :: TyVar (k -> xs) k) :: TyVar (x8 -> k -> xs) k) :: TyVar (x7 -> x8 -> k -> xs) k) :: TyVar (x6 -> x7 -> x8 -> k -> xs) k) :: TyVar (x5 -> x6 -> x7 -> x8 -> k -> xs) k) :: TyVar (x4 -> x5 -> x6 -> x7 -> x8 -> k -> xs) k) :: TyVar (x3 -> x4 -> x5 -> x6 -> x7 -> x8 -> k -> xs) k) :: TyVar (x2 -> x3 -> x4 -> x5 -> x6 -> x7 -> x8 -> k -> xs) k) :: TyVar (x1 -> x2 -> x3 -> x4 -> x5 -> x6 -> x7 -> x8 -> k -> xs) k) :: TyVar (x -> x1 -> x2 -> x3 -> x4 -> x5 -> x6 -> x7 -> x8 -> k -> xs) k) Source #

Intepretation

type family Interpret (t :: Atom d k) (tys :: LoT d) :: k where ... Source #

Replaces the holes in the Atom t by the elements of the list of types tys. The amount and kind of types in tys must match statically those required by the Atom.

>>> :kind! Interpret ([] :$: Var0) (LoT1 Int)
Interpret ([] :$: Var0) (LoT1 Int) :: *
= [Int]

Equations

Interpret ('Var v :: Atom d k) (tys :: LoT d) = InterpretVar v tys 
Interpret ('Kon t :: Atom d k) (tys :: LoT d) = t 
Interpret (f ':@: x :: Atom d k2) (tys :: LoT d) = Interpret f tys (Interpret x tys) 
Interpret (c ':&: d2 :: Atom d1 Constraint) (tys :: LoT d1) = (Interpret c tys, Interpret d2 tys) 
Interpret ('ForAll f :: Atom d Type) (tys :: LoT d) = ForAllI f tys 
Interpret (c ':=>>: f :: Atom d Type) (tys :: LoT d) = SuchThatI c f tys 
Interpret ('Eval f :: Atom d a) (tys :: LoT d) = Eval (Interpret f tys) 

type family InterpretVar (t :: TyVar d k) (tys :: LoT d) :: k where ... Source #

Obtains the type in the list tys referenced by the type variable t.

>>> :kind! Interpret Var0 (LoT2 Int Bool)
Interpret Var0 (LoT2 Int Bool) :: *
= Int
>>> :kind! Interpret Var1 (LoT2 Int Bool)
Interpret Var1 (LoT2 Int Bool) :: *
= Bool

Equations

InterpretVar ('VZ :: TyVar (k -> k') k) (tys :: LoT (k -> k')) = HeadLoT tys 
InterpretVar ('VS v :: TyVar (k2 -> k') k1) (tys :: LoT (k2 -> k')) = InterpretVar v (TailLoT tys) 

type family Satisfies (cs :: [Atom d Constraint]) (tys :: LoT d) where ... Source #

Interprets a list of Atom representing constraints into the actual constraints. This is a specialization of Interpret for the case of constraints.

>>> :kind! Satisfies '[Eq :$: Var0, Show :$: Var0] (LoT1 Int)
Satisfies '[Eq :$: Var0, Show :$: Var0] (LoT1 Int) :: Constraint
= (Eq Int, (Show Int, () :: Constraint))

Equations

Satisfies ('[] :: [Atom d Constraint]) (tys :: LoT d) = () 
Satisfies (c ': cs :: [Atom d Constraint]) (tys :: LoT d) = (Interpret c tys, Satisfies cs tys) 

type family ContainsTyVar (v :: TyVar d k) (t :: Atom d p) :: Bool where ... Source #

Determines whether a given type variable v is used within an Atom t. If not, we know that the atom is constant with respect to that variable.

Equations

ContainsTyVar (v :: TyVar d p) ('Var v :: Atom d p) = 'True 
ContainsTyVar (v :: TyVar d k) ('Var w :: Atom d p) = 'False 
ContainsTyVar (v :: TyVar d k) ('Kon t :: Atom d p) = 'False 
ContainsTyVar (v :: TyVar d k) (f ':@: x :: Atom d p2) = Or (ContainsTyVar v f) (ContainsTyVar v x) 
ContainsTyVar (v :: TyVar d k) (x ':&: y :: Atom d Constraint) = Or (ContainsTyVar v x) (ContainsTyVar v y) 
ContainsTyVar (v :: TyVar d k) (c ':=>>: f :: Atom d Type) = Or (ContainsTyVar v c) (ContainsTyVar v f) 
ContainsTyVar (v :: TyVar xs k) ('ForAll f :: Atom xs Type) = ContainsTyVar ('VS v :: TyVar (x -> xs) k) f 

Auxiliary types for interpretation

newtype ForAllI (f :: Atom (d1 -> d) Type) (tys :: LoT d) where Source #

Auxiliary type for interpretation of the ForAll atom. Required because a type family like Interpret cannot return a polymorphic type.

Constructors

ForAllI :: forall {d1} {d} (f :: Atom (d1 -> d) Type) (tys :: LoT d). (forall (t :: d1). Interpret f (t ':&&: tys)) -> ForAllI f tys 

newtype SuchThatI (c :: Atom d Constraint) (f :: Atom d Type) (tys :: LoT d) where Source #

Auxiliary type for interpretation of the (:=>>:) atom. Required because a type family like Interpret cannot return a type with constraints.

Constructors

SuchThatI 

Fields

Records a type as constructor + list of variables

newtype WrappedI (f :: Atom d Type) (tys :: LoT d) Source #

Records a value of type f applied to the list tys.

>>> :t WrapI [1] :: WrappedI ([] :$: Var0) (LoT1 Int)
WrapI [1] :: WrappedI ([] :$: Var0) (LoT1 Int)

Constructors

WrapI 

Fields

toWrappedI :: forall {d1} {ks} (f :: Atom (d1 -> ks) Type) (tys :: LoT ks) (t :: d1). ForAllI f tys -> WrappedI f (t ':&&: tys) Source #

fromWrappedI :: forall {d1} {d} (f :: Atom (d1 -> d) Type) (tys :: LoT d). (forall (t :: d1). WrappedI f (t ':&&: tys)) -> ForAllI f tys Source #