{-# LANGUAGE AllowAmbiguousTypes #-} {-# LANGUAGE ConstraintKinds #-} {-# LANGUAGE DataKinds #-} {-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE KindSignatures #-} {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE TypeApplications #-} {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE TypeInType #-} {-# LANGUAGE TypeOperators #-} {-# LANGUAGE UndecidableInstances #-} {-# LANGUAGE UndecidableSuperClasses #-} module Data.Diverse.TypeLevel where import Data.Diverse.TypeLevel.Internal import Data.Kind import GHC.TypeLits -- | Produce a runtime 'Int' value corresponding to a 'Nat' type. -- Based on https://github.com/VinylRecords/Vinyl/blob/a5ffd10fbc747c5366ae9806e61bf45f78c3eb33/Data/Vinyl/TypeLevel.hs -- This is used instead of 'KnownNat' because to avoid inefficient 'Integer' https://github.com/louispan/data-diverse/issues/8 -- AllowsAmbiguousTypes! Uses @TypeApplication@ instead of 'Proxy' class NatToInt (n :: Nat) where natToInt :: Int instance {-# OVERLAPPING #-} NatToInt 0 where natToInt = 0 {-# INLINE natToInt #-} instance {-# OVERLAPPABLE #-} (NatToInt m, n ~ (m + 1)) => NatToInt n where natToInt = 1 + natToInt @m {-# INLINE natToInt #-} -- | Ensures that @x@ is a unique member of @xs@, and that 'natToInt' can be used. type UniqueMember x xs = (Unique x xs, NatToInt (IndexOf x xs)) -- | Every x in @xs@ is a `UniqueMember x ys` type family UniqueMembers (xs :: [k]) (ys :: [k]) :: Constraint where UniqueMembers '[] ys = () UniqueMembers (x ': xs) ys = (UniqueMember x ys, UniqueMembers xs ys) -- | Ensures that @x@ is a unique member of @xs@, and that 'natToInt' can be used. type UniqueLabelMember l xs = (UniqueLabel l xs, NatToInt (IndexOf (KindAtLabel l xs) xs)) -- | Ensures that @x@ is a unique member of @xs@ if it exists, and that 'natToInt' can be used. type MaybeUniqueMember x xs = (Unique x xs, NatToInt (PositionOf x xs)) -- | Ensures that @x@ is a member of @xs@ at @n@, and that 'natToInt' can be used. type MemberAt n x xs = (NatToInt n, x ~ KindAtIndex n xs) -- | Ensures that @x@ is a member of @xs@ at @n@ if it exists, and that 'natToInt' can be used. type MaybeMemberAt n x xs = (NatToInt n, KindAtPositionIs n x xs) -- | Snoc @x@ to end of @xs@ if @x@ doesn't already exist in @xs@ type family SnocUnique (xs :: [k]) (x :: k) :: [k] where SnocUnique '[] x = '[x] SnocUnique (x ': xs) x = x ': xs SnocUnique (y ': xs) x = y ': SnocUnique xs x -- | For each @y@ in @ys@, snocs them to end of @xs@ if @y@ doesn't already exist in @xs@ type family AppendUnique (xs :: [k]) (ys :: [k]) :: [k] where AppendUnique '[] xs = xs AppendUnique xs '[] = xs AppendUnique xs xs = xs AppendUnique xs (y ': ys) = AppendUnique (SnocUnique xs y) ys -- | Ensures x is a unique member in @xs@ iff it exists in @ys@ type family UniqueIfExists ys x xs :: Constraint where UniqueIfExists '[] x xs = () UniqueIfExists (y ': ys) y xs = Unique y xs UniqueIfExists (y ': ys) x xs = UniqueIfExists ys x xs -- | Ensures that the type list contain unique types type IsDistinct (xs :: [k]) = IsDistinctImpl xs xs -- | Return the list of distinct types in a typelist type family Nub (xs :: [k]) :: [k] where Nub '[] = '[] Nub (x ': xs) = NubImpl xs x xs -- | Ensures that @x@ only ever appears once in @xs@ type Unique (x :: k) (xs :: [k]) = UniqueImpl xs x xs -- | Ensures that the @label@ in @tagged label v@ only ever appears once in @xs@. type UniqueLabel (l :: k1) (xs :: [k]) = UniqueLabelImpl xs l xs -- | Ensures that the @label@ list all 'UniqueLabel's type family UniqueLabels (ls :: [k1]) (xs :: [k]) :: Constraint where UniqueLabels '[] xs = () UniqueLabels (l ': ls) xs = (UniqueLabel l xs, UniqueLabels ls xs) -- | Get the first index of a type (Indexed by 0) -- Will result in type error if x doesn't exist in xs. type IndexOf (x :: k) (xs :: [k]) = IndexOfImpl xs x xs -- | Get the first index of a type (Indexed by 1) -- Will return 0 if x doesn't exists in xs. type PositionOf (x :: k) (xs :: [k]) = PositionOfImpl 0 x xs -- | Get the type at an index type KindAtIndex (n :: Nat) (xs :: [k]) = KindAtIndexImpl n xs n xs -- | Get the type at a label type KindAtLabel (l :: k1) (xs :: [k]) = KindAtLabelImpl l xs xs -- | It's actually ok for the position to be zero, but if it's not zero then the types must match type family KindAtPositionIs (n :: Nat) (x :: k) (xs :: [k]) :: Constraint where KindAtPositionIs 0 x xs = () KindAtPositionIs n x xs = (x ~ KindAtIndexImpl (n - 1) xs (n - 1) xs) -- | Get the types at an list of index type family KindsAtIndices (ns :: [Nat]) (xs :: [k]) :: [k] where KindsAtIndices '[] xs = '[] KindsAtIndices (n ': ns) xs = KindAtIndex n xs ': KindsAtIndices ns xs -- | Get the types with labels @ls@ from @xs@ type family KindsAtLabels (ls :: [k1]) (xs :: [k]) :: [k] where KindsAtLabels '[] xs = '[] KindsAtLabels (l ': ls) xs = KindAtLabel l xs ': KindsAtLabels ls xs -- | The typelist @xs@ without first @x@. It is okay for @x@ not to exist in @xs@ type family Remove (x :: k) (xs :: [k]) :: [k] where Remove x '[] = '[] Remove x (x ': xs) = xs Remove x (y ': xs) = y ': Remove x xs -- | The typelist @xs@ with the first @x@ replaced by @y@. It is okay for @x@ not to exist in @xs@ type Replace (x :: k) (y :: k) (xs :: [k]) = ReplaceImpl x y xs -- | The typelist @zs@ with the first @xs@ replaced by @ys@. -- @xs@ must be the same size as @ys@ type Replaces (xs :: [k]) (ys :: [k]) (zs :: [k]) = ReplacesImpl xs ys xs ys zs -- | The typelist @xs@ without the type at Nat @n@. @n@ must be within bounds of @xs@ type RemoveIndex (n :: Nat) (xs :: [k]) = RemoveIndexImpl n xs n xs -- | The typelist @xs@ without the type at Nat @n@ replaced by @y@. @n@ must be within bounds of @xs@ type ReplaceIndex (n :: Nat) (x :: k) (y :: k) (xs :: [k]) = ReplaceIndexImpl n xs n x y xs -- | The typelist @xs@ replaced by @ys@ at the indices @ns@. @ns@ and @ys@ must be the same length. @ns@ must be within bounds of @xs@ type ReplacesIndex (ns :: [Nat]) (ys :: [k]) (xs :: [k]) = ReplacesIndexImpl 0 ns ys xs -- | Get the typelist without the 'Head' type type family Tail (xs :: [k]) :: [k] where Tail '[] = TypeError ('Text "Tail error: empty type list") Tail (x ': xs) = xs -- | Get the first type in a typelist type family Head (xs :: [k]) :: k where Head '[] = TypeError ('Text "Head error: empty type list") Head (x ': xs) = x type family Last (xs :: [k]) :: k where Last '[] = TypeError ('Text "Last error: empty type list") Last (x ': x' ': xs) = Last (x' ': xs) Last '[x] = x -- | Ensures two typelists are the same length type SameLength (xs :: [k1]) (ys :: [k2]) = SameLengthImpl xs ys xs ys -- | Set complement. Returns the set of things in @xs@ that are not in @ys@. type family Complement (xs :: [k]) (ys :: [k]) :: [k] where Complement xs '[] = xs Complement xs (y ': ys) = Complement (Remove y xs) ys -- | Returns a @xs@ appended with @ys@ type family Append (xs :: [k]) (ys :: [k]) :: [k] where Append xs '[] = xs Append '[] ys = ys Append (x ': xs) ys = x ': Append xs ys -- | Returns the typelist without the 'Last' type type family Init (xs :: [k]) :: [k] where Init '[] = TypeError ('Text "Init error: empty type list") Init '[x] = '[] Init (x ': xs) = x ': Init xs -- | Takes two lists which must be the same length and returns a list of corresponding pairs. type Zip (xs :: [k]) (ys :: [k]) = ZipImpl xs ys xs ys -- | The result from evaluating a 'Case' with a type from a typelist. type family CaseResult (c ::[k1] -> k2) (x :: k1) :: k2 -- | Return a list of results from applying 'CaseResult' to every type in the @xs@ typelist. type family CaseResults (c ::[k1] -> k2) (xs :: [k1]) :: [k2] where CaseResults c '[] = '[] CaseResults c (x ': xs) = CaseResult c x ': CaseResults c xs -- | Tests if all the types in a typelist satisfy a constraint type family AllConstrained (c :: k -> Constraint) (xs :: [k]) :: Constraint where AllConstrained c '[] = () AllConstrained c (x ': xs) = (c x, AllConstrained c xs) -- https://hackage.haskell.org/package/vinyl-0.6.0/docs/Data-Vinyl-TypeLevel.html#t:AllConstrained -- | This is useful as a level function for @k@ in 'CaseFunc1' -- @C@ stands for constraints. -- @C0@ is a type level function of @Type -> Constraint@ class C0 a where instance C0 a where -- UndecidableSuperInstances :( -- @C2@ is a type level function of @(Type -> Constraint) -> (Type -> Constraint) -> (Type -> Constraint)@ class (c1 a, c2 a) => C2 c1 c2 a where instance (c1 a, c2 a) => C2 c1 c2 a where -- @C3@ is a type level function of @(Type -> Constraint) -> (Type -> Constraint) -> (Type -> Constraint) -> (Type -> Constraint)@ class (c1 a, c2 a, c3 a) => C3 c1 c2 c3 a where instance (c1 a, c2 a, c3 a) => C3 c1 c2 c3 a where class (c1 a, c2 a, c3 a, c4 a) => C4 c1 c2 c3 c4 a where instance (c1 a, c2 a, c3 a, c4 a) => C4 c1 c2 c3 c4 a where class (c1 a, c2 a, c3 a, c4 a, c5 a) => C5 c1 c2 c3 c4 c5 a where instance (c1 a, c2 a, c3 a, c4 a, c5 a) => C5 c1 c2 c3 c4 c5 a where class (c1 a, c2 a, c3 a, c4 a, c5 a, c6 a) => C6 c1 c2 c3 c4 c5 c6 a where instance (c1 a, c2 a, c3 a, c4 a, c5 a, c6 a) => C6 c1 c2 c3 c4 c5 c6 a where