-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Fast type-safe modular arithmetic
--   
--   <a>Modular arithmetic</a>, promoting moduli to the type level, with an
--   emphasis on performance. Originally part of <a>arithmoi</a> package.
@package mod
@version 0.1.2.2


-- | <a>Modular arithmetic</a>, promoting moduli to the type level, with an
--   emphasis on performance. Originally part of <a>arithmoi</a> package.
--   
--   This module supports moduli of arbitrary size. Use
--   <a>Data.Mod.Word</a> to achieve better performance, when your moduli
--   fit into <a>Word</a>.
module Data.Mod

-- | This data type represents <a>integers modulo m</a>, equipped with
--   useful instances.
--   
--   For example, 3 :: <a>Mod</a> 10 stands for the class of integers
--   congruent to &lt;math&gt;
--   
--   <pre>
--   &gt;&gt;&gt; :set -XDataKinds
--   
--   &gt;&gt;&gt; 3 + 8 :: Mod 10 -- 3 + 8 = 11 ≡ 1 (mod 10)
--   (1 `modulo` 10)
--   </pre>
--   
--   <b>Warning:</b> division by residue, which is not <a>coprime</a> with
--   the modulo, throws <a>DivideByZero</a>. Consider using
--   <a>invertMod</a> for non-prime moduli.
data Mod (m :: Nat)

-- | The canonical representative of the residue class, always between 0
--   and &lt;math&gt; inclusively.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XDataKinds
--   
--   &gt;&gt;&gt; -1 :: Mod 10
--   (9 `modulo` 10)
--   </pre>
unMod :: Mod m -> Natural

-- | If an argument is <a>coprime</a> with the modulo, return its modular
--   inverse. Otherwise return <a>Nothing</a>.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XDataKinds
--   
--   &gt;&gt;&gt; invertMod 3 :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
--   Just (7 `modulo` 10)
--   
--   &gt;&gt;&gt; invertMod 4 :: Mod 10 -- 4 and 10 are not coprime
--   Nothing
--   </pre>
invertMod :: KnownNat m => Mod m -> Maybe (Mod m)

-- | Drop-in replacement for <a>^</a> with much better performance.
--   Negative powers are allowed, but may throw <a>DivideByZero</a>, if an
--   argument is not <a>coprime</a> with the modulo.
--   
--   Building with <tt>-O</tt> triggers a rewrite rule <a>^</a> =
--   <a>^%</a>.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XDataKinds
--   
--   &gt;&gt;&gt; 3 ^% 4 :: Mod 10    -- 3 ^ 4 = 81 ≡ 1 (mod 10)
--   (1 `modulo` 10)
--   
--   &gt;&gt;&gt; 3 ^% (-1) :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
--   (7 `modulo` 10)
--   
--   &gt;&gt;&gt; 4 ^% (-1) :: Mod 10 -- 4 and 10 are not coprime
--   (*** Exception: divide by zero
--   </pre>
(^%) :: (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.TypeNats.KnownNat m => GHC.Show.Show (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 => GHC.Real.Fractional (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 => 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)


-- | <a>Modular arithmetic</a>, promoting moduli to the type level, with an
--   emphasis on performance. Originally part of <a>arithmoi</a> package.
--   
--   This module supports only moduli, which fit into <a>Word</a>. Use
--   (slower) <a>Data.Mod</a> to handle arbitrary-sized moduli.
module Data.Mod.Word

-- | This data type represents <a>integers modulo m</a>, equipped with
--   useful instances.
--   
--   For example, 3 :: <a>Mod</a> 10 stands for the class of integers
--   congruent to &lt;math&gt;
--   
--   <pre>
--   &gt;&gt;&gt; :set -XDataKinds
--   
--   &gt;&gt;&gt; 3 + 8 :: Mod 10 -- 3 + 8 = 11 ≡ 1 (mod 10)
--   (1 `modulo` 10)
--   </pre>
--   
--   <b>Warning:</b> division by residue, which is not <a>coprime</a> with
--   the modulo, throws <a>DivideByZero</a>. Consider using
--   <a>invertMod</a> for non-prime moduli.
data Mod (m :: Nat)

-- | The canonical representative of the residue class, always between 0
--   and &lt;math&gt; inclusively.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XDataKinds
--   
--   &gt;&gt;&gt; -1 :: Mod 10
--   (9 `modulo` 10)
--   </pre>
unMod :: Mod m -> Word

-- | If an argument is <a>coprime</a> with the modulo, return its modular
--   inverse. Otherwise return <a>Nothing</a>.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XDataKinds
--   
--   &gt;&gt;&gt; invertMod 3 :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
--   Just (7 `modulo` 10)
--   
--   &gt;&gt;&gt; invertMod 4 :: Mod 10 -- 4 and 10 are not coprime
--   Nothing
--   </pre>
invertMod :: KnownNat m => Mod m -> Maybe (Mod m)

-- | Drop-in replacement for <a>^</a> with a bit better performance.
--   Negative powers are allowed, but may throw <a>DivideByZero</a>, if an
--   argument is not <a>coprime</a> with the modulo.
--   
--   Building with <tt>-O</tt> triggers a rewrite rule <a>^</a> =
--   <a>^%</a>.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XDataKinds
--   
--   &gt;&gt;&gt; 3 ^% 4 :: Mod 10    -- 3 ^ 4 = 81 ≡ 1 (mod 10)
--   (1 `modulo` 10)
--   
--   &gt;&gt;&gt; 3 ^% (-1) :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
--   (7 `modulo` 10)
--   
--   &gt;&gt;&gt; 4 ^% (-1) :: Mod 10 -- 4 and 10 are not coprime
--   (*** Exception: divide by zero
--   </pre>
(^%) :: (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.TypeNats.KnownNat m => GHC.Show.Show (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 => GHC.Real.Fractional (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 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)
