-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Fast type-safe modular arithmetic
--
-- Modular arithmetic, promoting moduli to the type level, with an
-- emphasis on performance. Originally part of the arithmoi
-- package.
@package mod
@version 0.2.0.0
-- | Modular arithmetic, promoting moduli to the type level, with an
-- emphasis on performance. Originally part of the arithmoi
-- package.
--
-- This module supports moduli of arbitrary size. Use
-- Data.Mod.Word to achieve better performance, when your moduli
-- fit into Word.
module Data.Mod
-- | This data type represents integers modulo m, equipped with
-- useful instances.
--
-- For example, 3 :: Mod 10 stands for the class of integers
-- congruent to <math>
--
--
-- >>> :set -XDataKinds
--
-- >>> 3 + 8 :: Mod 10 -- 3 + 8 = 11 ≡ 1 (mod 10)
-- 1
--
--
-- Note: Mod 0 has no inhabitants, eventhough <math>
-- is technically isomorphic to <math>.
data Mod (m :: Nat)
-- | The canonical representative of the residue class, always between 0
-- and <math> (inclusively).
--
--
-- >>> :set -XDataKinds
--
-- >>> -1 :: Mod 10
-- 9
--
unMod :: Mod m -> Natural
-- | If an argument is coprime with the modulus, return its modular
-- inverse. Otherwise return Nothing.
--
--
-- >>> :set -XDataKinds
--
-- >>> invertMod 3 :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
-- Just 7
--
-- >>> invertMod 4 :: Mod 10 -- 4 and 10 are not coprime
-- Nothing
--
invertMod :: KnownNat m => Mod m -> Maybe (Mod m)
-- | Drop-in replacement for ^ with much better performance.
-- Negative powers are allowed, but may throw DivideByZero, if an
-- argument is not coprime with the modulus.
--
--
-- >>> :set -XDataKinds
--
-- >>> 3 ^% 4 :: Mod 10 -- 3 ^ 4 = 81 ≡ 1 (mod 10)
-- 1
--
-- >>> 3 ^% (-1) :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
-- 7
--
-- >>> 4 ^% (-1) :: Mod 10 -- 4 and 10 are not coprime
-- (*** Exception: divide by zero
--
(^%) :: (KnownNat m, Integral a) => Mod m -> a -> Mod m
infixr 8 ^%
instance GHC.Generics.Generic (Data.Mod.Mod m)
instance GHC.Classes.Ord (Data.Mod.Mod m)
instance GHC.Classes.Eq (Data.Mod.Mod m)
instance Control.DeepSeq.NFData (Data.Mod.Mod m)
instance GHC.Show.Show (Data.Mod.Mod m)
instance GHC.TypeNats.KnownNat m => GHC.Read.Read (Data.Mod.Mod m)
instance GHC.TypeNats.KnownNat m => GHC.Real.Real (Data.Mod.Mod m)
instance GHC.TypeNats.KnownNat m => GHC.Enum.Enum (Data.Mod.Mod m)
instance GHC.TypeNats.KnownNat m => GHC.Enum.Bounded (Data.Mod.Mod m)
instance GHC.TypeNats.KnownNat m => GHC.Num.Num (Data.Mod.Mod m)
instance GHC.TypeNats.KnownNat m => Data.Semiring.Semiring (Data.Mod.Mod m)
instance GHC.TypeNats.KnownNat m => Data.Semiring.Ring (Data.Mod.Mod m)
instance GHC.TypeNats.KnownNat m => Data.Euclidean.GcdDomain (Data.Mod.Mod m)
instance GHC.TypeNats.KnownNat m => Data.Euclidean.Euclidean (Data.Mod.Mod m)
instance GHC.TypeNats.KnownNat m => Data.Euclidean.Field (Data.Mod.Mod m)
instance GHC.TypeNats.KnownNat m => GHC.Real.Fractional (Data.Mod.Mod m)
instance GHC.TypeNats.KnownNat m => Foreign.Storable.Storable (Data.Mod.Mod m)
instance GHC.TypeNats.KnownNat m => Data.Primitive.Types.Prim (Data.Mod.Mod m)
instance GHC.TypeNats.KnownNat m => Data.Vector.Unboxed.Base.Unbox (Data.Mod.Mod m)
instance GHC.TypeNats.KnownNat m => Data.Vector.Generic.Mutable.Base.MVector Data.Vector.Unboxed.Base.MVector (Data.Mod.Mod m)
instance GHC.TypeNats.KnownNat m => Data.Vector.Generic.Base.Vector Data.Vector.Unboxed.Base.Vector (Data.Mod.Mod m)
-- | Modular arithmetic, promoting moduli to the type level, with an
-- emphasis on performance. Originally part of the arithmoi
-- package.
--
-- This module supports only moduli, which fit into Word. Use the
-- (slower) Data.Mod module for handling arbitrary-sized moduli.
module Data.Mod.Word
-- | This data type represents integers modulo m, equipped with
-- useful instances.
--
-- For example, 3 :: Mod 10 stands for the class of integers
-- congruent to <math>
--
--
-- >>> :set -XDataKinds
--
-- >>> 3 + 8 :: Mod 10 -- 3 + 8 = 11 ≡ 1 (mod 10)
-- 1
--
--
-- Note: Mod 0 has no inhabitants, eventhough <math>
-- is technically isomorphic to <math>.
data Mod (m :: Nat)
-- | The canonical representative of the residue class, always between 0
-- and <math> (inclusively).
--
--
-- >>> :set -XDataKinds
--
-- >>> -1 :: Mod 10
-- 9
--
unMod :: Mod m -> Word
-- | If an argument is coprime with the modulus, return its modular
-- inverse. Otherwise return Nothing.
--
--
-- >>> :set -XDataKinds
--
-- >>> invertMod 3 :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
-- Just 7
--
-- >>> invertMod 4 :: Mod 10 -- 4 and 10 are not coprime
-- Nothing
--
invertMod :: KnownNat m => Mod m -> Maybe (Mod m)
-- | Drop-in replacement for ^ with a bit better performance.
-- Negative powers are allowed, but may throw DivideByZero, if an
-- argument is not coprime with the modulus.
--
--
-- >>> :set -XDataKinds
--
-- >>> 3 ^% 4 :: Mod 10 -- 3 ^ 4 = 81 ≡ 1 (mod 10)
-- 1
--
-- >>> 3 ^% (-1) :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
-- 7
--
-- >>> 4 ^% (-1) :: Mod 10 -- 4 and 10 are not coprime
-- (*** Exception: divide by zero
--
(^%) :: (KnownNat m, Integral a) => Mod m -> a -> Mod m
infixr 8 ^%
instance Data.Primitive.Types.Prim (Data.Mod.Word.Mod m)
instance Foreign.Storable.Storable (Data.Mod.Word.Mod m)
instance GHC.Generics.Generic (Data.Mod.Word.Mod m)
instance GHC.Classes.Ord (Data.Mod.Word.Mod m)
instance GHC.Classes.Eq (Data.Mod.Word.Mod m)
instance Control.DeepSeq.NFData (Data.Mod.Word.Mod m)
instance GHC.Show.Show (Data.Mod.Word.Mod m)
instance GHC.TypeNats.KnownNat m => GHC.Read.Read (Data.Mod.Word.Mod m)
instance GHC.TypeNats.KnownNat m => GHC.Real.Real (Data.Mod.Word.Mod m)
instance GHC.TypeNats.KnownNat m => GHC.Enum.Enum (Data.Mod.Word.Mod m)
instance GHC.TypeNats.KnownNat m => GHC.Enum.Bounded (Data.Mod.Word.Mod m)
instance GHC.TypeNats.KnownNat m => GHC.Num.Num (Data.Mod.Word.Mod m)
instance GHC.TypeNats.KnownNat m => Data.Semiring.Semiring (Data.Mod.Word.Mod m)
instance GHC.TypeNats.KnownNat m => Data.Semiring.Ring (Data.Mod.Word.Mod m)
instance GHC.TypeNats.KnownNat m => Data.Euclidean.GcdDomain (Data.Mod.Word.Mod m)
instance GHC.TypeNats.KnownNat m => Data.Euclidean.Euclidean (Data.Mod.Word.Mod m)
instance GHC.TypeNats.KnownNat m => Data.Euclidean.Field (Data.Mod.Word.Mod m)
instance GHC.TypeNats.KnownNat m => GHC.Real.Fractional (Data.Mod.Word.Mod m)
instance Data.Vector.Unboxed.Base.Unbox (Data.Mod.Word.Mod m)
instance Data.Vector.Generic.Mutable.Base.MVector Data.Vector.Unboxed.Base.MVector (Data.Mod.Word.Mod m)
instance Data.Vector.Generic.Base.Vector Data.Vector.Unboxed.Base.Vector (Data.Mod.Word.Mod m)