Copyright | (c) Galois Inc 2014-2019 |
---|---|
Maintainer | Joe Hendrix <jhendrix@galois.com> |
Safe Haskell | Trustworthy |
Language | Haskell98 |
This defines a type NatRepr
for representing a type-level natural
at runtime. This can be used to branch on a type-level value. For
each n
, NatRepr n
contains a single value containing the value
n
. This can be used to help use type-level variables on code
with data dependendent types.
The TestEquality
and DecidableEq
instances for NatRepr
are implemented using unsafeCoerce
, as is the isZeroNat
function. This
should be typesafe because we maintain the invariant that the integer value
contained in a NatRepr value matches its static type.
Synopsis
- data NatRepr (n :: Nat)
- natValue :: NatRepr n -> Natural
- intValue :: NatRepr n -> Integer
- knownNat :: forall n. KnownNat n => NatRepr n
- withKnownNat :: forall n r. NatRepr n -> (KnownNat n => r) -> r
- data IsZeroNat n where
- ZeroNat :: IsZeroNat 0
- NonZeroNat :: IsZeroNat (n + 1)
- isZeroNat :: NatRepr n -> IsZeroNat n
- isZeroOrGT1 :: NatRepr n -> Either (n :~: 0) (LeqProof 1 n)
- data NatComparison m n where
- compareNat :: NatRepr m -> NatRepr n -> NatComparison m n
- decNat :: 1 <= n => NatRepr n -> NatRepr (n - 1)
- predNat :: NatRepr (n + 1) -> NatRepr n
- incNat :: NatRepr n -> NatRepr (n + 1)
- addNat :: NatRepr m -> NatRepr n -> NatRepr (m + n)
- subNat :: n <= m => NatRepr m -> NatRepr n -> NatRepr (m - n)
- divNat :: 1 <= n => NatRepr (m * n) -> NatRepr n -> NatRepr m
- halfNat :: NatRepr (n + n) -> NatRepr n
- withDivModNat :: forall n m a. NatRepr n -> NatRepr m -> (forall div mod. n ~ ((div * m) + mod) => NatRepr div -> NatRepr mod -> a) -> a
- natMultiply :: NatRepr n -> NatRepr m -> NatRepr (n * m)
- someNat :: Integral a => a -> Maybe (Some NatRepr)
- mkNatRepr :: Natural -> Some NatRepr
- maxNat :: NatRepr m -> NatRepr n -> Some NatRepr
- natRec :: forall p f. NatRepr p -> f 0 -> (forall n. NatRepr n -> f n -> f (n + 1)) -> f p
- natRecStrong :: forall p f. NatRepr p -> f 0 -> (forall n. NatRepr n -> (forall m. m <= n => NatRepr m -> f m) -> f (n + 1)) -> f p
- natRecBounded :: forall m h f. m <= h => NatRepr m -> NatRepr h -> f 0 -> (forall n. n <= h => NatRepr n -> f n -> f (n + 1)) -> f (m + 1)
- natForEach :: forall l h a. NatRepr l -> NatRepr h -> (forall n. (l <= n, n <= h) => NatRepr n -> a) -> [a]
- natFromZero :: forall h a. NatRepr h -> (forall n. n <= h => NatRepr n -> a) -> [a]
- data NatCases m n where
- testNatCases :: forall m n. NatRepr m -> NatRepr n -> NatCases m n
- lessThanIrreflexive :: forall f (a :: Nat). f a -> LeqProof (1 + a) a -> Void
- lessThanAsymmetric :: forall m f n. LeqProof (n + 1) m -> LeqProof (m + 1) n -> f n -> Void
- widthVal :: NatRepr n -> Int
- minUnsigned :: NatRepr w -> Integer
- maxUnsigned :: NatRepr w -> Integer
- minSigned :: 1 <= w => NatRepr w -> Integer
- maxSigned :: 1 <= w => NatRepr w -> Integer
- toUnsigned :: NatRepr w -> Integer -> Integer
- toSigned :: 1 <= w => NatRepr w -> Integer -> Integer
- unsignedClamp :: NatRepr w -> Integer -> Integer
- signedClamp :: 1 <= w => NatRepr w -> Integer -> Integer
- data LeqProof m n where
- decideLeq :: NatRepr a -> NatRepr b -> Either (LeqProof a b) (LeqProof a b -> Void)
- testLeq :: forall m n. NatRepr m -> NatRepr n -> Maybe (LeqProof m n)
- testStrictLeq :: forall m n. m <= n => NatRepr m -> NatRepr n -> Either (LeqProof (m + 1) n) (m :~: n)
- leqRefl :: forall f n. f n -> LeqProof n n
- leqTrans :: LeqProof m n -> LeqProof n p -> LeqProof m p
- leqAdd2 :: LeqProof x_l x_h -> LeqProof y_l y_h -> LeqProof (x_l + y_l) (x_h + y_h)
- leqSub2 :: LeqProof x_l x_h -> LeqProof y_l y_h -> LeqProof (x_l - y_h) (x_h - y_l)
- leqMulCongr :: LeqProof a x -> LeqProof b y -> LeqProof (a * b) (x * y)
- leqProof :: m <= n => f m -> g n -> LeqProof m n
- withLeqProof :: LeqProof m n -> (m <= n => a) -> a
- isPosNat :: NatRepr n -> Maybe (LeqProof 1 n)
- leqAdd :: forall f m n p. LeqProof m n -> f p -> LeqProof m (n + p)
- leqSub :: forall m n p. LeqProof m n -> LeqProof p m -> LeqProof (m - p) n
- leqMulPos :: forall p q x y. (1 <= x, 1 <= y) => p x -> q y -> LeqProof 1 (x * y)
- leqAddPos :: (1 <= m, 1 <= n) => p m -> q n -> LeqProof 1 (m + n)
- addIsLeq :: f n -> g m -> LeqProof n (n + m)
- withAddLeq :: forall n m a. NatRepr n -> NatRepr m -> (n <= (n + m) => NatRepr (n + m) -> a) -> a
- addPrefixIsLeq :: f m -> g n -> LeqProof n (m + n)
- withAddPrefixLeq :: NatRepr n -> NatRepr m -> (m <= (n + m) => a) -> a
- addIsLeqLeft1 :: forall n n' m. LeqProof (n + n') m -> LeqProof n m
- dblPosIsPos :: forall n. LeqProof 1 n -> LeqProof 1 (n + n)
- leqMulMono :: 1 <= x => p x -> q y -> LeqProof y (x * y)
- plusComm :: forall f m g n. f m -> g n -> (m + n) :~: (n + m)
- mulComm :: forall f m g n. f m -> g n -> (m * n) :~: (n * m)
- plusMinusCancel :: forall f m g n. f m -> g n -> ((m + n) - n) :~: m
- minusPlusCancel :: forall f m g n. n <= m => f m -> g n -> ((m - n) + n) :~: m
- addMulDistribRight :: forall n m p f g h. f n -> g m -> h p -> ((n * p) + (m * p)) :~: ((n + m) * p)
- withAddMulDistribRight :: forall n m p f g h a. f n -> g m -> h p -> (((n * p) + (m * p)) ~ ((n + m) * p) => a) -> a
- withSubMulDistribRight :: forall n m p f g h a. m <= n => f n -> g m -> h p -> (((n * p) - (m * p)) ~ ((n - m) * p) => a) -> a
- mulCancelR :: (1 <= c, (n1 * c) ~ (n2 * c)) => f1 n1 -> f2 n2 -> f3 c -> n1 :~: n2
- mul2Plus :: forall f n. f n -> (n + n) :~: (2 * n)
- lemmaMul :: 1 <= n => p w -> q n -> (w + ((n - 1) * w)) :~: (n * w)
- type family (a :: Nat) + (b :: Nat) :: Nat where ...
- type family (a :: Nat) - (b :: Nat) :: Nat where ...
- type family (a :: Nat) * (b :: Nat) :: Nat where ...
- type (<=) (x :: Nat) (y :: Nat) = (x <=? y) ~ True
- class TestEquality (f :: k -> Type) where
- testEquality :: f a -> f b -> Maybe (a :~: b)
- data (a :: k) :~: (b :: k) :: forall k. k -> k -> Type where
- data Some (f :: k -> *)
Documentation
data NatRepr (n :: Nat) Source #
A runtime presentation of a type-level Nat
.
This can be used for performing dynamic checks on a type-level natural numbers.
Instances
TestEquality NatRepr Source # | |
Defined in Data.Parameterized.NatRepr.Internal | |
HashableF NatRepr Source # | |
ShowF NatRepr Source # | |
OrdF NatRepr Source # | |
DecidableEq NatRepr Source # | |
IsRepr NatRepr Source # | |
KnownNat n => KnownRepr NatRepr (n :: Nat) Source # | |
Defined in Data.Parameterized.NatRepr.Internal | |
Eq (NatRepr m) Source # | |
KnownNat n => Data (NatRepr n) Source # | |
Defined in Data.Parameterized.NatRepr.Internal gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> NatRepr n -> c (NatRepr n) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (NatRepr n) # toConstr :: NatRepr n -> Constr # dataTypeOf :: NatRepr n -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (NatRepr n)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (NatRepr n)) # gmapT :: (forall b. Data b => b -> b) -> NatRepr n -> NatRepr n # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> NatRepr n -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> NatRepr n -> r # gmapQ :: (forall d. Data d => d -> u) -> NatRepr n -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> NatRepr n -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> NatRepr n -> m (NatRepr n) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> NatRepr n -> m (NatRepr n) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> NatRepr n -> m (NatRepr n) # | |
Show (NatRepr n) Source # | |
Hashable (NatRepr n) Source # | |
Defined in Data.Parameterized.NatRepr.Internal | |
PolyEq (NatRepr m) (NatRepr n) Source # | |
knownNat :: forall n. KnownNat n => NatRepr n Source #
This generates a NatRepr from a type-level context.
withKnownNat :: forall n r. NatRepr n -> (KnownNat n => r) -> r Source #
isZeroOrGT1 :: NatRepr n -> Either (n :~: 0) (LeqProof 1 n) Source #
Every nat is either zero or >= 1.
data NatComparison m n where Source #
Result of comparing two numbers.
compareNat :: NatRepr m -> NatRepr n -> NatComparison m n Source #
withDivModNat :: forall n m a. NatRepr n -> NatRepr m -> (forall div mod. n ~ ((div * m) + mod) => NatRepr div -> NatRepr mod -> a) -> a Source #
someNat :: Integral a => a -> Maybe (Some NatRepr) Source #
Turn an Integral
value into a NatRepr
. Returns Nothing
if the given value is negative.
maxNat :: NatRepr m -> NatRepr n -> Some NatRepr Source #
Return the maximum of two nat representations.
Recursor for natural numbeers.
:: NatRepr p | |
-> f 0 | base case |
-> (forall n. NatRepr n -> (forall m. m <= n => NatRepr m -> f m) -> f (n + 1)) | inductive step |
-> f p |
Strong induction variant of the recursor.
natRecBounded :: forall m h f. m <= h => NatRepr m -> NatRepr h -> f 0 -> (forall n. n <= h => NatRepr n -> f n -> f (n + 1)) -> f (m + 1) Source #
Bounded recursor for natural numbers.
If you can prove: - Base case: f 0 - Inductive step: if n <= h and (f n) then (f (n + 1)) You can conclude: for all n <= h, (f (n + 1)).
natForEach :: forall l h a. NatRepr l -> NatRepr h -> (forall n. (l <= n, n <= h) => NatRepr n -> a) -> [a] Source #
Apply a function to each element in a range; return the list of values obtained.
natFromZero :: forall h a. NatRepr h -> (forall n. n <= h => NatRepr n -> a) -> [a] Source #
Apply a function to each element in a range starting at zero; return the list of values obtained.
Strict order
lessThanIrreflexive :: forall f (a :: Nat). f a -> LeqProof (1 + a) a -> Void Source #
The strict order (defined by n < m <- n + 1 <= m, is irreflexive.
lessThanAsymmetric :: forall m f n. LeqProof (n + 1) m -> LeqProof (m + 1) n -> f n -> Void Source #
The strict order on the naturals is irreflexive.
Bitvector utilities
minUnsigned :: NatRepr w -> Integer Source #
Return minimum unsigned value for bitvector with given width (always 0).
maxUnsigned :: NatRepr w -> Integer Source #
Return maximum unsigned value for bitvector with given width.
minSigned :: 1 <= w => NatRepr w -> Integer Source #
Return minimum value for bitvector in two's complement with given width.
maxSigned :: 1 <= w => NatRepr w -> Integer Source #
Return maximum value for bitvector in two's complement with given width.
toSigned :: 1 <= w => NatRepr w -> Integer -> Integer Source #
toSigned w i
interprets the least-significant w
bits in i
as a
signed number in two's complement notation and returns that value.
unsignedClamp :: NatRepr w -> Integer -> Integer Source #
unsignedClamp w i
rounds i
to the nearest value between
0
and 2^w-1
(inclusive).
signedClamp :: 1 <= w => NatRepr w -> Integer -> Integer Source #
signedClamp w i
rounds i
to the nearest value between
-2^(w-1)
and 2^(w-1)-1
(inclusive).
LeqProof
data LeqProof m n where Source #
LeqProof m n
is a type whose values are only inhabited when m
is less than or equal to n
.
decideLeq :: NatRepr a -> NatRepr b -> Either (LeqProof a b) (LeqProof a b -> Void) Source #
(<=) is a decidable relation on nats.
testLeq :: forall m n. NatRepr m -> NatRepr n -> Maybe (LeqProof m n) Source #
x
checks whether testLeq
yx
is less than or equal to y
.
testStrictLeq :: forall m n. m <= n => NatRepr m -> NatRepr n -> Either (LeqProof (m + 1) n) (m :~: n) Source #
leqAdd2 :: LeqProof x_l x_h -> LeqProof y_l y_h -> LeqProof (x_l + y_l) (x_h + y_h) Source #
Add both sides of two inequalities
leqSub2 :: LeqProof x_l x_h -> LeqProof y_l y_h -> LeqProof (x_l - y_h) (x_h - y_l) Source #
Subtract sides of two inequalities.
leqMulCongr :: LeqProof a x -> LeqProof b y -> LeqProof (a * b) (x * y) Source #
Congruence rule for multiplication
LeqProof combinators
withLeqProof :: LeqProof m n -> (m <= n => a) -> a Source #
leqAdd :: forall f m n p. LeqProof m n -> f p -> LeqProof m (n + p) Source #
Produce proof that adding a value to the larger element in an LeqProof is larger
leqSub :: forall m n p. LeqProof m n -> LeqProof p m -> LeqProof (m - p) n Source #
Produce proof that subtracting a value from the smaller element is smaller.
leqMulPos :: forall p q x y. (1 <= x, 1 <= y) => p x -> q y -> LeqProof 1 (x * y) Source #
Multiplying two positive numbers results in a positive number.
withAddLeq :: forall n m a. NatRepr n -> NatRepr m -> (n <= (n + m) => NatRepr (n + m) -> a) -> a Source #
addPrefixIsLeq :: f m -> g n -> LeqProof n (m + n) Source #
Arithmetic proof
plusComm :: forall f m g n. f m -> g n -> (m + n) :~: (n + m) Source #
Produce evidence that +
is commutative.
mulComm :: forall f m g n. f m -> g n -> (m * n) :~: (n * m) Source #
Produce evidence that *
is commutative.
plusMinusCancel :: forall f m g n. f m -> g n -> ((m + n) - n) :~: m Source #
Cancel an add followed by a subtract
addMulDistribRight :: forall n m p f g h. f n -> g m -> h p -> ((n * p) + (m * p)) :~: ((n + m) * p) Source #
withAddMulDistribRight :: forall n m p f g h a. f n -> g m -> h p -> (((n * p) + (m * p)) ~ ((n + m) * p) => a) -> a Source #
withSubMulDistribRight :: forall n m p f g h a. m <= n => f n -> g m -> h p -> (((n * p) - (m * p)) ~ ((n - m) * p) => a) -> a Source #
Re-exports typelists basics
type family (a :: Nat) + (b :: Nat) :: Nat where ... infixl 6 #
Addition of type-level naturals.
Since: base-4.7.0.0
type family (a :: Nat) - (b :: Nat) :: Nat where ... infixl 6 #
Subtraction of type-level naturals.
Since: base-4.7.0.0
type family (a :: Nat) * (b :: Nat) :: Nat where ... infixl 7 #
Multiplication of type-level naturals.
Since: base-4.7.0.0
type (<=) (x :: Nat) (y :: Nat) = (x <=? y) ~ True infix 4 #
Comparison of type-level naturals, as a constraint.
Since: base-4.7.0.0
class TestEquality (f :: k -> Type) where #
This class contains types where you can learn the equality of two types from information contained in terms. Typically, only singleton types should inhabit this class.
testEquality :: f a -> f b -> Maybe (a :~: b) #
Conditionally prove the equality of a
and b
.
Instances
data (a :: k) :~: (b :: k) :: forall k. k -> k -> Type where infix 4 #
Propositional equality. If a :~: b
is inhabited by some terminating
value, then the type a
is the same as the type b
. To use this equality
in practice, pattern-match on the a :~: b
to get out the Refl
constructor;
in the body of the pattern-match, the compiler knows that a ~ b
.
Since: base-4.7.0.0
Instances
Category ((:~:) :: k -> k -> Type) | Since: base-4.7.0.0 |
TestEquality ((:~:) a :: k -> Type) | Since: base-4.7.0.0 |
Defined in Data.Type.Equality | |
NFData2 ((:~:) :: Type -> Type -> Type) | Since: deepseq-1.4.3.0 |
Defined in Control.DeepSeq | |
NFData1 ((:~:) a) | Since: deepseq-1.4.3.0 |
Defined in Control.DeepSeq | |
a ~ b => Bounded (a :~: b) | Since: base-4.7.0.0 |
a ~ b => Enum (a :~: b) | Since: base-4.7.0.0 |
Defined in Data.Type.Equality | |
Eq (a :~: b) | Since: base-4.7.0.0 |
(a ~ b, Data a) => Data (a :~: b) | Since: base-4.7.0.0 |
Defined in Data.Data gfoldl :: (forall d b0. Data d => c (d -> b0) -> d -> c b0) -> (forall g. g -> c g) -> (a :~: b) -> c (a :~: b) # gunfold :: (forall b0 r. Data b0 => c (b0 -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (a :~: b) # toConstr :: (a :~: b) -> Constr # dataTypeOf :: (a :~: b) -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (a :~: b)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (a :~: b)) # gmapT :: (forall b0. Data b0 => b0 -> b0) -> (a :~: b) -> a :~: b # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> (a :~: b) -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> (a :~: b) -> r # gmapQ :: (forall d. Data d => d -> u) -> (a :~: b) -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> (a :~: b) -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> (a :~: b) -> m (a :~: b) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> (a :~: b) -> m (a :~: b) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> (a :~: b) -> m (a :~: b) # | |
Ord (a :~: b) | Since: base-4.7.0.0 |
Defined in Data.Type.Equality | |
a ~ b => Read (a :~: b) | Since: base-4.7.0.0 |
Show (a :~: b) | Since: base-4.7.0.0 |
NFData (a :~: b) | Since: deepseq-1.4.3.0 |
Defined in Control.DeepSeq |
data Some (f :: k -> *) Source #
Instances
OrdC (Some :: (k -> Type) -> Type) Source # | |
TestEqualityC (Some :: (k -> Type) -> Type) Source # | This instance demonstrates where the above class is useful: namely, in types with existential quantification. |
Defined in Data.Parameterized.ClassesC | |
TestEquality f => Eq (Some f) Source # | |
OrdF f => Ord (Some f) Source # | |
ShowF f => Show (Some f) Source # | |
HashableF f => Hashable (Some f) Source # | |
Defined in Data.Parameterized.Some |