-- |
-- Module:      Data.Mod
-- Copyright:   (c) 2017-2022 Andrew Lelechenko
-- Licence:     MIT
-- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
--
-- <https://en.wikipedia.org/wiki/Modular_arithmetic Modular arithmetic>,
-- promoting moduli to the type level, with an emphasis on performance.
-- Originally part of the <https://hackage.haskell.org/package/arithmoi arithmoi> package.
--
-- This module supports moduli of arbitrary size.
-- Use "Data.Mod.Word" to achieve better performance,
-- when your moduli fit into 'Word'.

{-# LANGUAGE BangPatterns          #-}
{-# LANGUAGE CPP                   #-}
{-# LANGUAGE DataKinds             #-}
{-# LANGUAGE DeriveGeneric         #-}
{-# LANGUAGE MagicHash             #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables   #-}
{-# LANGUAGE TypeApplications      #-}
{-# LANGUAGE TypeFamilies          #-}
{-# LANGUAGE UnboxedTuples         #-}

module Data.Mod
  ( Mod
  , unMod
  , invertMod
  , (^%)
  ) where

import Control.Exception
import Control.DeepSeq
import Control.Monad
import Data.Bits
import Data.Mod.Compat (timesWord2#, remWord2#)
import Data.Ratio
import Data.Word (Word8)
#ifdef MIN_VERSION_semirings
import Data.Euclidean (GcdDomain(..), Euclidean(..), Field)
import Data.Semiring (Semiring(..), Ring(..))
#endif
#ifdef MIN_VERSION_vector
import Control.Monad.Primitive
import Control.Monad.ST
import qualified Data.Primitive.Types        as P
import qualified Data.Vector.Generic         as G
import qualified Data.Vector.Generic.Mutable as M
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Primitive       as P
import Foreign (copyBytes)
#endif
import Foreign.Storable (Storable(..))
import GHC.Exts hiding (timesWord2#, quotRemWord2#)
import GHC.Generics
import GHC.IO (IO(..))
import GHC.Natural (Natural(..), powModNatural)
import GHC.Num.BigNat
import GHC.Num.Integer
import GHC.TypeNats (Nat, KnownNat, natVal, natVal')
import Text.Read (Read(readPrec))

-- | This data type represents
-- <https://en.wikipedia.org/wiki/Modular_arithmetic#Integers_modulo_n integers modulo m>,
-- equipped with useful instances.
--
-- For example, 3 :: 'Mod' 10 stands for the class of integers
-- congruent to \( 3 \bmod 10 \colon \ldots {−17}, −7, 3, 13, 23 \ldots \)
--
-- >>> :set -XDataKinds
-- >>> 3 + 8 :: Mod 10 -- 3 + 8 = 11 ≡ 1 (mod 10)
-- 1
--
-- __Note:__ 'Mod' 0 has no inhabitants, eventhough \( \mathbb{Z}/0\mathbb{Z} \) is technically isomorphic to \( \mathbb{Z} \).
newtype Mod (m :: Nat) = Mod
  { forall (m :: Natural). Mod m -> Natural
unMod :: Natural
  -- ^ The canonical representative of the residue class,
  -- always between 0 and \( m - 1 \) (inclusively).
  --
  -- >>> :set -XDataKinds
  -- >>> -1 :: Mod 10
  -- 9
  }
  deriving (Mod m -> Mod m -> Bool
forall (m :: Natural). Mod m -> Mod m -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Mod m -> Mod m -> Bool
$c/= :: forall (m :: Natural). Mod m -> Mod m -> Bool
== :: Mod m -> Mod m -> Bool
$c== :: forall (m :: Natural). Mod m -> Mod m -> Bool
Eq, Mod m -> Mod m -> Bool
Mod m -> Mod m -> Ordering
Mod m -> Mod m -> Mod m
forall (m :: Natural). Eq (Mod m)
forall (m :: Natural). Mod m -> Mod m -> Bool
forall (m :: Natural). Mod m -> Mod m -> Ordering
forall (m :: Natural). Mod m -> Mod m -> Mod m
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: Mod m -> Mod m -> Mod m
$cmin :: forall (m :: Natural). Mod m -> Mod m -> Mod m
max :: Mod m -> Mod m -> Mod m
$cmax :: forall (m :: Natural). Mod m -> Mod m -> Mod m
>= :: Mod m -> Mod m -> Bool
$c>= :: forall (m :: Natural). Mod m -> Mod m -> Bool
> :: Mod m -> Mod m -> Bool
$c> :: forall (m :: Natural). Mod m -> Mod m -> Bool
<= :: Mod m -> Mod m -> Bool
$c<= :: forall (m :: Natural). Mod m -> Mod m -> Bool
< :: Mod m -> Mod m -> Bool
$c< :: forall (m :: Natural). Mod m -> Mod m -> Bool
compare :: Mod m -> Mod m -> Ordering
$ccompare :: forall (m :: Natural). Mod m -> Mod m -> Ordering
Ord, forall (m :: Natural) x. Rep (Mod m) x -> Mod m
forall (m :: Natural) x. Mod m -> Rep (Mod m) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cto :: forall (m :: Natural) x. Rep (Mod m) x -> Mod m
$cfrom :: forall (m :: Natural) x. Mod m -> Rep (Mod m) x
Generic)

instance NFData (Mod m)

instance Show (Mod m) where
  show :: Mod m -> String
show (Mod Natural
x) = forall a. Show a => a -> String
show Natural
x

-- | Wrapping behaviour, similar to
-- the existing @instance@ 'Read' 'Int'.
instance KnownNat m => Read (Mod m) where
  readPrec :: ReadPrec (Mod m)
readPrec = forall a. Num a => Integer -> a
fromInteger forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. Read a => ReadPrec a
readPrec

instance KnownNat m => Real (Mod m) where
  toRational :: Mod m -> Rational
toRational (Mod Natural
x) = forall a. Real a => a -> Rational
toRational Natural
x

instance KnownNat m => Enum (Mod m) where
  succ :: Mod m -> Mod m
succ Mod m
x = if Mod m
x forall a. Eq a => a -> a -> Bool
== forall a. Bounded a => a
maxBound then forall a e. Exception e => e -> a
throw ArithException
Overflow  else coerce :: forall a b. Coercible a b => a -> b
coerce (forall a. Enum a => a -> a
succ @Natural) Mod m
x
  pred :: Mod m -> Mod m
pred Mod m
x = if Mod m
x forall a. Eq a => a -> a -> Bool
== forall a. Bounded a => a
minBound then forall a e. Exception e => e -> a
throw ArithException
Underflow else coerce :: forall a b. Coercible a b => a -> b
coerce (forall a. Enum a => a -> a
pred @Natural) Mod m
x

  toEnum :: Int -> Mod m
toEnum   = forall a b. (Integral a, Num b) => a -> b
fromIntegral :: Int -> Mod m
  fromEnum :: Mod m -> Int
fromEnum = (forall a b. (Integral a, Num b) => a -> b
fromIntegral :: Natural -> Int) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (m :: Natural). Mod m -> Natural
unMod

  enumFrom :: Mod m -> [Mod m]
enumFrom Mod m
x       = forall a. Enum a => a -> a -> [a]
enumFromTo Mod m
x forall a. Bounded a => a
maxBound
  enumFromThen :: Mod m -> Mod m -> [Mod m]
enumFromThen Mod m
x Mod m
y = forall a. Enum a => a -> a -> a -> [a]
enumFromThenTo Mod m
x Mod m
y (if Mod m
y forall a. Ord a => a -> a -> Bool
>= Mod m
x then forall a. Bounded a => a
maxBound else forall a. Bounded a => a
minBound)

  enumFromTo :: Mod m -> Mod m -> [Mod m]
enumFromTo     = coerce :: forall a b. Coercible a b => a -> b
coerce (forall a. Enum a => a -> a -> [a]
enumFromTo     @Natural)
  enumFromThenTo :: Mod m -> Mod m -> Mod m -> [Mod m]
enumFromThenTo = coerce :: forall a b. Coercible a b => a -> b
coerce (forall a. Enum a => a -> a -> a -> [a]
enumFromThenTo @Natural)

instance KnownNat m => Bounded (Mod m) where
  minBound :: Mod m
minBound = Mod m
mx
    where
      mx :: Mod m
mx = if forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx forall a. Ord a => a -> a -> Bool
> Natural
0 then forall (m :: Natural). Natural -> Mod m
Mod Natural
0 else forall a e. Exception e => e -> a
throw ArithException
DivideByZero
  maxBound :: Mod m
maxBound = Mod m
mx
    where
      mx :: Mod m
mx = if Natural
m forall a. Ord a => a -> a -> Bool
> Natural
0 then forall (m :: Natural). Natural -> Mod m
Mod (Natural
m forall a. Num a => a -> a -> a
- Natural
1) else forall a e. Exception e => e -> a
throw ArithException
DivideByZero
      m :: Natural
m = forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx

bigNatToNat :: BigNat# -> Natural
bigNatToNat :: BigNat# -> Natural
bigNatToNat BigNat#
r# =
  if Int# -> Bool
isTrue# (BigNat# -> Int#
bigNatSize# BigNat#
r# Int# -> Int# -> Int#
<=# Int#
1#) then Word# -> Natural
NatS# (BigNat# -> Word#
bigNatToWord# BigNat#
r#) else BigNat -> Natural
NatJ# (BigNat# -> BigNat
BN# BigNat#
r#)

subIfGe :: BigNat# -> BigNat# -> Natural
subIfGe :: BigNat# -> BigNat# -> Natural
subIfGe BigNat#
z# BigNat#
m# = case BigNat#
z# BigNat# -> BigNat# -> (# (# #) | BigNat# #)
`bigNatSub` BigNat#
m# of
  (# (# #) | #) -> BigNat -> Natural
NatJ# (BigNat# -> BigNat
BN# BigNat#
z#)
  (# | BigNat#
zm# #)   -> BigNat# -> Natural
bigNatToNat BigNat#
zm#

addMod :: Natural -> Natural -> Natural -> Natural
addMod :: Natural -> Natural -> Natural -> Natural
addMod (NatS# Word#
m#) (NatS# Word#
x#) (NatS# Word#
y#) =
  if Int# -> Bool
isTrue# Int#
c# Bool -> Bool -> Bool
|| Int# -> Bool
isTrue# (Word#
z# Word# -> Word# -> Int#
`geWord#` Word#
m#) then Word# -> Natural
NatS# (Word#
z# Word# -> Word# -> Word#
`minusWord#` Word#
m#) else Word# -> Natural
NatS# Word#
z#
  where
    !(# Word#
z#, Int#
c# #) = Word#
x# Word# -> Word# -> (# Word#, Int# #)
`addWordC#` Word#
y#
addMod NatS#{} Natural
_ Natural
_ = forall a. a
brokenInvariant
addMod (NatJ# (BN# BigNat#
m#)) (NatS# Word#
x#) (NatS# Word#
y#) =
  if Int# -> Bool
isTrue# Int#
c# then BigNat# -> BigNat# -> Natural
subIfGe (Word# -> Word# -> BigNat#
bigNatFromWord2# Word#
1## Word#
z#) BigNat#
m# else Word# -> Natural
NatS# Word#
z#
  where
    !(# Word#
z#, Int#
c# #) = Word#
x# Word# -> Word# -> (# Word#, Int# #)
`addWordC#` Word#
y#
addMod (NatJ# (BN# BigNat#
m#)) (NatS# Word#
x#) (NatJ# (BN# BigNat#
y#)) = BigNat# -> BigNat# -> Natural
subIfGe (BigNat#
y# BigNat# -> Word# -> BigNat#
`bigNatAddWord#` Word#
x#) BigNat#
m#
addMod (NatJ# (BN# BigNat#
m#)) (NatJ# (BN# BigNat#
x#)) (NatS# Word#
y#) = BigNat# -> BigNat# -> Natural
subIfGe (BigNat#
x# BigNat# -> Word# -> BigNat#
`bigNatAddWord#` Word#
y#) BigNat#
m#
addMod (NatJ# (BN# BigNat#
m#)) (NatJ# (BN# BigNat#
x#)) (NatJ# (BN# BigNat#
y#)) = BigNat# -> BigNat# -> Natural
subIfGe (BigNat#
x# BigNat# -> BigNat# -> BigNat#
`bigNatAdd` BigNat#
y#) BigNat#
m#

subMod :: Natural -> Natural -> Natural -> Natural
subMod :: Natural -> Natural -> Natural -> Natural
subMod (NatS# Word#
m#) (NatS# Word#
x#) (NatS# Word#
y#) =
  if Int# -> Bool
isTrue# (Word#
x# Word# -> Word# -> Int#
`geWord#` Word#
y#) then Word# -> Natural
NatS# Word#
z# else Word# -> Natural
NatS# (Word#
z# Word# -> Word# -> Word#
`plusWord#` Word#
m#)
  where
    z# :: Word#
z# = Word#
x# Word# -> Word# -> Word#
`minusWord#` Word#
y#
subMod NatS#{} Natural
_ Natural
_ = forall a. a
brokenInvariant
subMod (NatJ# (BN# BigNat#
m#)) (NatS# Word#
x#) (NatS# Word#
y#) =
  if Int# -> Bool
isTrue# (Word#
x# Word# -> Word# -> Int#
`geWord#` Word#
y#)
    then Word# -> Natural
NatS# (Word#
x# Word# -> Word# -> Word#
`minusWord#` Word#
y#)
    else BigNat# -> Natural
bigNatToNat (BigNat#
m# BigNat# -> Word# -> BigNat#
`bigNatSubWordUnsafe#` (Word#
y# Word# -> Word# -> Word#
`minusWord#` Word#
x#))
subMod (NatJ# (BN# BigNat#
m#)) (NatS# Word#
x#) (NatJ# (BN# BigNat#
y#)) =
  BigNat# -> Natural
bigNatToNat (BigNat#
m# BigNat# -> BigNat# -> BigNat#
`bigNatSubUnsafe` BigNat#
y# BigNat# -> Word# -> BigNat#
`bigNatAddWord#` Word#
x#)
subMod NatJ#{} (NatJ# (BN# BigNat#
x#)) (NatS# Word#
y#) =
  BigNat# -> Natural
bigNatToNat (BigNat#
x# BigNat# -> Word# -> BigNat#
`bigNatSubWordUnsafe#` Word#
y#)
subMod (NatJ# (BN# BigNat#
m#)) (NatJ# (BN# BigNat#
x#)) (NatJ# (BN# BigNat#
y#)) =
  case BigNat#
x# BigNat# -> BigNat# -> (# (# #) | BigNat# #)
`bigNatSub` BigNat#
y# of
    (# (# #) | #) -> BigNat# -> Natural
bigNatToNat (BigNat#
m# BigNat# -> BigNat# -> BigNat#
`bigNatSubUnsafe` BigNat#
y# BigNat# -> BigNat# -> BigNat#
`bigNatAdd` BigNat#
x#)
    (# | BigNat#
xy# #) -> BigNat# -> Natural
bigNatToNat BigNat#
xy#

negateMod :: Natural -> Natural -> Natural
negateMod :: Natural -> Natural -> Natural
negateMod Natural
_ (NatS# Word#
0##) = Word# -> Natural
NatS# Word#
0##
negateMod (NatS# Word#
m#) (NatS# Word#
x#) = Word# -> Natural
NatS# (Word#
m# Word# -> Word# -> Word#
`minusWord#` Word#
x#)
negateMod NatS#{} Natural
_ = forall a. a
brokenInvariant
negateMod (NatJ# (BN# BigNat#
m#)) (NatS# Word#
x#) = BigNat# -> Natural
bigNatToNat (BigNat#
m# BigNat# -> Word# -> BigNat#
`bigNatSubWordUnsafe#` Word#
x#)
negateMod (NatJ# (BN# BigNat#
m#)) (NatJ# (BN# BigNat#
x#)) = BigNat# -> Natural
bigNatToNat (BigNat#
m# BigNat# -> BigNat# -> BigNat#
`bigNatSubUnsafe` BigNat#
x#)

halfWord :: Word
halfWord :: Word
halfWord = Word
1 forall a. Bits a => a -> Int -> a
`shiftL` (forall b. FiniteBits b => b -> Int
finiteBitSize (Word
0 :: Word) forall a. Bits a => a -> Int -> a
`shiftR` Int
1)

mulMod :: Natural -> Natural -> Natural -> Natural
mulMod :: Natural -> Natural -> Natural -> Natural
mulMod (NatS# Word#
m#) (NatS# Word#
x#) (NatS# Word#
y#)
  | Word# -> Word
W# Word#
m# forall a. Ord a => a -> a -> Bool
<= Word
halfWord = Word# -> Natural
NatS# (Word# -> Word# -> Word#
timesWord# Word#
x# Word#
y# Word# -> Word# -> Word#
`remWord#` Word#
m#)
  | Bool
otherwise = Word# -> Natural
NatS# Word#
r#
  where
    !(# Word#
hi#, Word#
lo# #) = Word# -> Word# -> (# Word#, Word# #)
timesWord2# Word#
x# Word#
y#
    !r# :: Word#
r# = Word# -> Word# -> Word# -> Word#
remWord2# Word#
lo# Word#
hi# Word#
m#
mulMod NatS#{} Natural
_ Natural
_ = forall a. a
brokenInvariant
mulMod (NatJ# (BN# BigNat#
m#)) (NatS# Word#
x#) (NatS# Word#
y#) =
  BigNat# -> Natural
bigNatToNat (Word# -> Word# -> BigNat#
bigNatFromWord2# Word#
z1# Word#
z2# BigNat# -> BigNat# -> BigNat#
`bigNatRem` BigNat#
m#)
  where
    !(# Word#
z1#, Word#
z2# #) = Word# -> Word# -> (# Word#, Word# #)
timesWord2# Word#
x# Word#
y#
mulMod (NatJ# (BN# BigNat#
m#)) (NatS# Word#
x#) (NatJ# (BN# BigNat#
y#)) =
  BigNat# -> Natural
bigNatToNat ((BigNat#
y# BigNat# -> Word# -> BigNat#
`bigNatMulWord#` Word#
x#) BigNat# -> BigNat# -> BigNat#
`bigNatRem` BigNat#
m#)
mulMod (NatJ# (BN# BigNat#
m#)) (NatJ# (BN# BigNat#
x#)) (NatS# Word#
y#) =
  BigNat# -> Natural
bigNatToNat ((BigNat#
x# BigNat# -> Word# -> BigNat#
`bigNatMulWord#` Word#
y#) BigNat# -> BigNat# -> BigNat#
`bigNatRem` BigNat#
m#)
mulMod (NatJ# (BN# BigNat#
m#)) (NatJ# (BN# BigNat#
x#)) (NatJ# (BN# BigNat#
y#)) =
  BigNat# -> Natural
bigNatToNat ((BigNat#
x# BigNat# -> BigNat# -> BigNat#
`bigNatMul` BigNat#
y#) BigNat# -> BigNat# -> BigNat#
`bigNatRem` BigNat#
m#)

brokenInvariant :: a
brokenInvariant :: forall a. a
brokenInvariant = forall a. HasCallStack => String -> a
error String
"argument is larger than modulus"

instance KnownNat m => Num (Mod m) where
  mx :: Mod m
mx@(Mod !Natural
x) + :: Mod m -> Mod m -> Mod m
+ (Mod !Natural
y) = forall (m :: Natural). Natural -> Mod m
Mod forall a b. (a -> b) -> a -> b
$ Natural -> Natural -> Natural -> Natural
addMod (forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx) Natural
x Natural
y
  {-# INLINE (+) #-}
  mx :: Mod m
mx@(Mod !Natural
x) - :: Mod m -> Mod m -> Mod m
- (Mod !Natural
y) = forall (m :: Natural). Natural -> Mod m
Mod forall a b. (a -> b) -> a -> b
$ Natural -> Natural -> Natural -> Natural
subMod (forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx) Natural
x Natural
y
  {-# INLINE (-) #-}
  negate :: Mod m -> Mod m
negate mx :: Mod m
mx@(Mod !Natural
x) = forall (m :: Natural). Natural -> Mod m
Mod forall a b. (a -> b) -> a -> b
$ Natural -> Natural -> Natural
negateMod (forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx) Natural
x
  {-# INLINE negate #-}
  mx :: Mod m
mx@(Mod !Natural
x) * :: Mod m -> Mod m -> Mod m
* (Mod !Natural
y) = forall (m :: Natural). Natural -> Mod m
Mod forall a b. (a -> b) -> a -> b
$ Natural -> Natural -> Natural -> Natural
mulMod (forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx) Natural
x Natural
y
  {-# INLINE (*) #-}
  abs :: Mod m -> Mod m
abs = forall a. a -> a
id
  {-# INLINE abs #-}
  signum :: Mod m -> Mod m
signum = forall a b. a -> b -> a
const Mod m
x
    where
      x :: Mod m
x = if forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
x forall a. Ord a => a -> a -> Bool
> Natural
1 then forall (m :: Natural). Natural -> Mod m
Mod Natural
1 else forall (m :: Natural). Natural -> Mod m
Mod Natural
0
  {-# INLINE signum #-}
  fromInteger :: Integer -> Mod m
fromInteger Integer
x = Mod m
mx
    where
      mx :: Mod m
mx = forall (m :: Natural). Natural -> Mod m
Mod forall a b. (a -> b) -> a -> b
$ forall a. Num a => Integer -> a
fromInteger forall a b. (a -> b) -> a -> b
$ Integer
x forall a. Integral a => a -> a -> a
`mod` forall a. Integral a => a -> Integer
toInteger (forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx)
  {-# INLINE fromInteger #-}

#ifdef MIN_VERSION_semirings

instance KnownNat m => Semiring (Mod m) where
  plus :: Mod m -> Mod m -> Mod m
plus  = forall a. Num a => a -> a -> a
(+)
  {-# INLINE plus #-}
  times :: Mod m -> Mod m -> Mod m
times = forall a. Num a => a -> a -> a
(*)
  {-# INLINE times #-}
  zero :: Mod m
zero  = Mod m
mx
    where
      mx :: Mod m
mx = if forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx forall a. Ord a => a -> a -> Bool
> Natural
0 then forall (m :: Natural). Natural -> Mod m
Mod Natural
0 else forall a e. Exception e => e -> a
throw ArithException
DivideByZero
  {-# INLINE zero #-}
  one :: Mod m
one   = Mod m
mx
    where
      mx :: Mod m
mx = case Natural
m forall a. Ord a => a -> a -> Ordering
`compare` Natural
1 of
        Ordering
LT -> forall a e. Exception e => e -> a
throw ArithException
DivideByZero
        Ordering
EQ -> forall (m :: Natural). Natural -> Mod m
Mod Natural
0
        Ordering
GT -> forall (m :: Natural). Natural -> Mod m
Mod Natural
1
      m :: Natural
m = forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx
  {-# INLINE one #-}
  fromNatural :: Natural -> Mod m
fromNatural Natural
x = Mod m
mx
    where
      mx :: Mod m
mx = forall (m :: Natural). Natural -> Mod m
Mod forall a b. (a -> b) -> a -> b
$ Natural
x forall a. Integral a => a -> a -> a
`mod` forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx
  {-# INLINE fromNatural #-}

instance KnownNat m => Ring (Mod m) where
  negate :: Mod m -> Mod m
negate = forall a. Num a => a -> a
Prelude.negate
  {-# INLINE negate #-}

-- | 'Mod' @m@ is not even an
-- <https://en.wikipedia.org/wiki/Integral_domain integral domain> for
-- <https://en.wikipedia.org/wiki/Composite_number composite> @m@,
-- much less a <https://en.wikipedia.org/wiki/GCD_domain GCD domain>.
-- However, 'Data.Euclidean.gcd' and 'Data.Euclidean.lcm' are still meaningful
-- even for composite @m@, corresponding to a sum and an intersection of
-- <https://en.wikipedia.org/wiki/Ideal_(ring_theory) ideals>.
--
-- The instance is lawful only for
-- <https://en.wikipedia.org/wiki/Prime_number prime> @m@, otherwise
-- @'Data.Euclidean.divide' x y@ tries to return any @Just z@ such that @x == y * z@.
--
instance KnownNat m => GcdDomain (Mod m) where
  divide :: Mod m -> Mod m -> Maybe (Mod m)
divide (Mod Natural
0) Mod m
_ = forall a. a -> Maybe a
Just (forall (m :: Natural). Natural -> Mod m
Mod Natural
0)
  divide Mod m
_ (Mod Natural
0) = forall a. Maybe a
Nothing
  divide mx :: Mod m
mx@(Mod Natural
x) (Mod Natural
y) = case Maybe Natural
mry of
    Just Natural
ry -> if Natural
xr forall a. Eq a => a -> a -> Bool
== Natural
0 then forall a. a -> Maybe a
Just (forall (m :: Natural). Natural -> Mod m
Mod Natural
xq forall a. Num a => a -> a -> a
* forall (m :: Natural). Natural -> Mod m
Mod Natural
ry) else forall a. Maybe a
Nothing
    Maybe Natural
Nothing -> forall a. Maybe a
Nothing
    where
      m :: Natural
m = forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx
      gmy :: Natural
gmy = forall a. Integral a => a -> a -> a
Prelude.gcd Natural
m Natural
y
      (Natural
xq, Natural
xr) = forall a. Integral a => a -> a -> (a, a)
Prelude.quotRem Natural
x Natural
gmy
      mry :: Maybe Natural
mry = Natural -> Natural -> Maybe Natural
invertModInternal (Natural
y forall a. Integral a => a -> a -> a
`Prelude.quot` Natural
gmy)  (Natural
m forall a. Integral a => a -> a -> a
`Prelude.quot` Natural
gmy)

  gcd :: Mod m -> Mod m -> Mod m
gcd (Mod Natural
x) (Mod Natural
y) = Mod m
g
    where
      m :: Natural
m = forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
g
      g :: Mod m
g = forall (m :: Natural). Natural -> Mod m
Mod forall a b. (a -> b) -> a -> b
$ if Natural
m forall a. Ord a => a -> a -> Bool
> Natural
1 then forall a. Integral a => a -> a -> a
Prelude.gcd (forall a. Integral a => a -> a -> a
Prelude.gcd Natural
m Natural
x) Natural
y else Natural
0
  lcm :: Mod m -> Mod m -> Mod m
lcm (Mod Natural
x) (Mod Natural
y) = Mod m
l
    where
      m :: Natural
m = forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
l
      l :: Mod m
l = forall (m :: Natural). Natural -> Mod m
Mod forall a b. (a -> b) -> a -> b
$ if Natural
m forall a. Ord a => a -> a -> Bool
> Natural
1 then forall a. Integral a => a -> a -> a
Prelude.lcm (forall a. Integral a => a -> a -> a
Prelude.gcd Natural
m Natural
x) (forall a. Integral a => a -> a -> a
Prelude.gcd Natural
m Natural
y) else Natural
0
  coprime :: Mod m -> Mod m -> Bool
coprime Mod m
x Mod m
y = forall a. GcdDomain a => a -> a -> a
Data.Euclidean.gcd Mod m
x Mod m
y forall a. Eq a => a -> a -> Bool
== forall a. Semiring a => a
one

-- | 'Mod' @m@ is not even an
-- <https://en.wikipedia.org/wiki/Integral_domain integral domain> for
-- <https://en.wikipedia.org/wiki/Composite_number composite> @m@,
-- much less a <https://en.wikipedia.org/wiki/Euclidean_domain Euclidean domain>.
--
-- The instance is lawful only for
-- <https://en.wikipedia.org/wiki/Prime_number prime> @m@, otherwise
-- we try to do our best:
-- @'Data.Euclidean.quot' x y@ returns any @z@ such that @x == y * z@,
-- 'Data.Euclidean.rem' is not always 0, and both can throw 'DivideByZero'.
--
instance KnownNat m => Euclidean (Mod m) where
  degree :: Mod m -> Natural
degree = forall (m :: Natural). Mod m -> Natural
unMod
  {-# INLINABLE degree #-}

  quotRem :: Mod m -> Mod m -> (Mod m, Mod m)
quotRem (Mod Natural
0) Mod m
_ = (forall (m :: Natural). Natural -> Mod m
Mod Natural
0, forall (m :: Natural). Natural -> Mod m
Mod Natural
0)
  quotRem Mod m
_ (Mod Natural
0) = forall a e. Exception e => e -> a
throw ArithException
DivideByZero
  quotRem mx :: Mod m
mx@(Mod Natural
x) (Mod Natural
y) = case Maybe Natural
mry of
    Just Natural
ry -> (forall (m :: Natural). Natural -> Mod m
Mod Natural
xq forall a. Num a => a -> a -> a
* forall (m :: Natural). Natural -> Mod m
Mod Natural
ry, forall (m :: Natural). Natural -> Mod m
Mod Natural
xr)
    Maybe Natural
Nothing -> forall a e. Exception e => e -> a
throw ArithException
DivideByZero
    where
      m :: Natural
m = forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx
      gmy :: Natural
gmy = forall a. Integral a => a -> a -> a
Prelude.gcd Natural
m Natural
y
      (Natural
xq, Natural
xr) = forall a. Integral a => a -> a -> (a, a)
Prelude.quotRem Natural
x Natural
gmy
      mry :: Maybe Natural
mry = Natural -> Natural -> Maybe Natural
invertModInternal (Natural
y forall a. Integral a => a -> a -> a
`Prelude.quot` Natural
gmy)  (Natural
m forall a. Integral a => a -> a -> a
`Prelude.quot` Natural
gmy)

-- | 'Mod' @m@ is not even an
-- <https://en.wikipedia.org/wiki/Integral_domain integral domain> for
-- <https://en.wikipedia.org/wiki/Composite_number composite> @m@,
-- much less a <https://en.wikipedia.org/wiki/Field_(mathematics) field>.
--
-- The instance is lawful only for
-- <https://en.wikipedia.org/wiki/Prime_number prime> @m@, otherwise
-- division by a residue, which is not
-- <https://en.wikipedia.org/wiki/Coprime_integers coprime>
-- with the modulus, throws 'DivideByZero'.
-- Consider using 'invertMod' for non-prime moduli.
--
instance KnownNat m => Field (Mod m)

#endif

-- | Division by a residue, which is not
-- <https://en.wikipedia.org/wiki/Coprime_integers coprime>
-- with the modulus, throws 'DivideByZero'.
-- Consider using 'invertMod' for non-prime moduli.
--
instance KnownNat m => Fractional (Mod m) where
  fromRational :: Rational -> Mod m
fromRational Rational
r = case forall a. Ratio a -> a
denominator Rational
r of
    Integer
1   -> Mod m
num
    Integer
den -> Mod m
num forall a. Fractional a => a -> a -> a
/ forall a. Num a => Integer -> a
fromInteger Integer
den
    where
      num :: Mod m
num = forall a. Num a => Integer -> a
fromInteger (forall a. Ratio a -> a
numerator Rational
r)
  {-# INLINE fromRational #-}
  recip :: Mod m -> Mod m
recip Mod m
mx = case forall (m :: Natural). KnownNat m => Mod m -> Maybe (Mod m)
invertMod Mod m
mx of
    Maybe (Mod m)
Nothing -> forall a e. Exception e => e -> a
throw ArithException
DivideByZero
    Just Mod m
y  -> Mod m
y
  {-# INLINE recip #-}

-- | If an argument is
-- <https://en.wikipedia.org/wiki/Coprime_integers 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)
invertMod :: forall (m :: Natural). KnownNat m => Mod m -> Maybe (Mod m)
invertMod Mod m
x = forall (m :: Natural). Natural -> Mod m
Mod forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Natural -> Natural -> Maybe Natural
invertModInternal (forall (m :: Natural). Mod m -> Natural
unMod Mod m
x) (forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
x)
{-# INLINABLE invertMod #-}

invertModInternal
  :: Natural -- Value
  -> Natural -- Modulo
  -> Maybe Natural
invertModInternal :: Natural -> Natural -> Maybe Natural
invertModInternal Natural
x Natural
m = case Integer -> Natural -> (# Natural | () #)
integerRecipMod# (forall a. Integral a => a -> Integer
toInteger Natural
x) Natural
m of
  (# | () #) -> forall a. Maybe a
Nothing
  (# Natural
y | #)  -> forall a. a -> Maybe a
Just Natural
y
{-# INLINABLE invertModInternal #-}

-- | Drop-in replacement for 'Prelude.^' with much better performance.
-- Negative powers are allowed, but may throw 'DivideByZero', if an argument
-- is not <https://en.wikipedia.org/wiki/Coprime_integers 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
Mod m
mx ^% :: forall (m :: Natural) a.
(KnownNat m, Integral a) =>
Mod m -> a -> Mod m
^% a
a
  | a
a forall a. Ord a => a -> a -> Bool
< a
0     = case forall (m :: Natural). KnownNat m => Mod m -> Maybe (Mod m)
invertMod Mod m
mx of
    Maybe (Mod m)
Nothing ->  forall a e. Exception e => e -> a
throw ArithException
DivideByZero
    Just Mod m
my ->  forall (m :: Natural). Natural -> Mod m
Mod forall a b. (a -> b) -> a -> b
$ Natural -> Natural -> Natural -> Natural
powModNatural (forall (m :: Natural). Mod m -> Natural
unMod Mod m
my) (a -> Natural
fromIntegral' (-a
a)) (forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx)
  | Bool
otherwise = forall (m :: Natural). Natural -> Mod m
Mod forall a b. (a -> b) -> a -> b
$ Natural -> Natural -> Natural -> Natural
powModNatural (forall (m :: Natural). Mod m -> Natural
unMod Mod m
mx) (a -> Natural
fromIntegral' a
a)    (forall (n :: Natural) (proxy :: Natural -> *).
KnownNat n =>
proxy n -> Natural
natVal Mod m
mx)
  where
#if __GLASGOW_HASKELL__ == 900 && __GLASGOW_HASKELL_PATCHLEVEL1__ == 1
    -- Cannot use fromIntegral because of https://gitlab.haskell.org/ghc/ghc/-/issues/19411
    fromIntegral' = fromInteger . toInteger
#else
    fromIntegral' :: a -> Natural
fromIntegral' = forall a b. (Integral a, Num b) => a -> b
fromIntegral
#endif
{-# INLINABLE [1] (^%) #-}

{-# SPECIALISE [1] (^%) ::
  KnownNat m => Mod m -> Integer -> Mod m,
  KnownNat m => Mod m -> Natural -> Mod m,
  KnownNat m => Mod m -> Int     -> Mod m,
  KnownNat m => Mod m -> Word    -> Mod m #-}

{-# RULES
"powMod/2/Integer"     forall x. x ^% (2 :: Integer) = let u = x in u*u
"powMod/3/Integer"     forall x. x ^% (3 :: Integer) = let u = x in u*u*u
"powMod/2/Int"         forall x. x ^% (2 :: Int)     = let u = x in u*u
"powMod/3/Int"         forall x. x ^% (3 :: Int)     = let u = x in u*u*u
"powMod/2/Word"        forall x. x ^% (2 :: Word)    = let u = x in u*u
"powMod/3/Word"        forall x. x ^% (3 :: Word)    = let u = x in u*u*u #-}

infixr 8 ^%

wordSize :: Int
wordSize :: Int
wordSize = forall b. FiniteBits b => b -> Int
finiteBitSize (Word
0 :: Word)

lgWordSize :: Int
lgWordSize :: Int
lgWordSize = case Int
wordSize of
  Int
32 -> Int
2 -- 2^2 bytes in word
  Int
64 -> Int
3 -- 2^3 bytes in word
  Int
_  -> forall a. HasCallStack => String -> a
error String
"lgWordSize: unknown architecture"

-- | No validation checks are performed;
-- reading untrusted data may corrupt internal invariants.
instance KnownNat m => Storable (Mod m) where
  sizeOf :: Mod m -> Int
sizeOf Mod m
_ = case forall (n :: Natural). KnownNat n => Proxy# n -> Natural
natVal' (forall {k} (a :: k). Proxy# a
proxy# :: Proxy# m) of
    NatS#{}  -> forall a. Storable a => a -> Int
sizeOf (Word
0 :: Word)
    NatJ# (BN# BigNat#
m#) -> Int# -> Int
I# (BigNat# -> Int#
bigNatSize# BigNat#
m#) forall a. Bits a => a -> Int -> a
`shiftL` Int
lgWordSize
  {-# INLINE sizeOf #-}

  alignment :: Mod m -> Int
alignment Mod m
_ = forall a. Storable a => a -> Int
alignment (Word
0 :: Word)
  {-# INLINE alignment #-}

  peek :: Ptr (Mod m) -> IO (Mod m)
peek (Ptr Addr#
addr#) = case forall (n :: Natural). KnownNat n => Proxy# n -> Natural
natVal' (forall {k} (a :: k). Proxy# a
proxy# :: Proxy# m) of
    NatS#{} -> do
      W# Word#
w# <- forall a. Storable a => Ptr a -> IO a
peek (forall a. Addr# -> Ptr a
Ptr Addr#
addr#)
      forall (f :: * -> *) a. Applicative f => a -> f a
pure forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (m :: Natural). Natural -> Mod m
Mod forall a b. (a -> b) -> a -> b
$! Word# -> Natural
NatS# Word#
w#
    NatJ# (BN# BigNat#
m#) -> do
      let !(I# Int#
lgWordSize#) = Int
lgWordSize
          sz# :: Int#
sz# = BigNat# -> Int#
bigNatSize# BigNat#
m# Int# -> Int# -> Int#
`iShiftL#` Int#
lgWordSize#
      BN# BigNat#
bn <- forall a. (State# RealWorld -> (# State# RealWorld, a #)) -> IO a
IO (\State# RealWorld
token -> case forall s. Word# -> Addr# -> State# s -> (# State# s, BigNat# #)
bigNatFromAddrLE# (Int# -> Word#
int2Word# Int#
sz#) Addr#
addr# State# RealWorld
token of (# State# RealWorld
newToken, BigNat#
bn# #) -> (# State# RealWorld
newToken, BigNat# -> BigNat
BN# BigNat#
bn# #))
      forall (f :: * -> *) a. Applicative f => a -> f a
pure forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (m :: Natural). Natural -> Mod m
Mod forall a b. (a -> b) -> a -> b
$! BigNat# -> Natural
bigNatToNat BigNat#
bn
  {-# INLINE peek #-}

  poke :: Ptr (Mod m) -> Mod m -> IO ()
poke (Ptr Addr#
addr#) (Mod Natural
x) = case forall (n :: Natural). KnownNat n => Proxy# n -> Natural
natVal' (forall {k} (a :: k). Proxy# a
proxy# :: Proxy# m) of
    NatS#{} -> case Natural
x of
      NatS# Word#
x# -> forall a. Storable a => Ptr a -> a -> IO ()
poke (forall a. Addr# -> Ptr a
Ptr Addr#
addr#) (Word# -> Word
W# Word#
x#)
      Natural
_        -> forall a. a
brokenInvariant
    NatJ# (BN# BigNat#
m#) -> case Natural
x of
      NatS# Word#
x# -> do
        forall a. Storable a => Ptr a -> a -> IO ()
poke (forall a. Addr# -> Ptr a
Ptr Addr#
addr#) (Word# -> Word
W# Word#
x#)
        forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ [Int
1 .. Int
sz forall a. Num a => a -> a -> a
- Int
1] forall a b. (a -> b) -> a -> b
$ \Int
off ->
          forall a. Storable a => Ptr a -> Int -> a -> IO ()
pokeElemOff (forall a. Addr# -> Ptr a
Ptr Addr#
addr#) Int
off (Word
0 :: Word)
      NatJ# (BN# BigNat#
bn) -> do
        Word
l <- forall a. (State# RealWorld -> (# State# RealWorld, a #)) -> IO a
IO (\State# RealWorld
token -> case forall s. BigNat# -> Addr# -> State# s -> (# State# s, Word# #)
bigNatToAddrLE# BigNat#
bn Addr#
addr# State# RealWorld
token of (# State# RealWorld
newToken, Word#
l# #) -> (# State# RealWorld
newToken, Word# -> Word
W# Word#
l# #))
        forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ [(forall a b. (Integral a, Num b) => a -> b
fromIntegral :: Word -> Int) Word
l .. (Int
sz forall a. Bits a => a -> Int -> a
`shiftL` Int
lgWordSize) forall a. Num a => a -> a -> a
- Int
1] forall a b. (a -> b) -> a -> b
$ \Int
off ->
          forall a. Storable a => Ptr a -> Int -> a -> IO ()
pokeElemOff (forall a. Addr# -> Ptr a
Ptr Addr#
addr#) Int
off (Word8
0 :: Word8)
      where
        sz :: Int
sz = Int# -> Int
I# (BigNat# -> Int#
bigNatSize# BigNat#
m#)
  {-# INLINE poke #-}

#ifdef MIN_VERSION_vector

-- | No validation checks are performed;
-- reading untrusted data may corrupt internal invariants.
instance KnownNat m => P.Prim (Mod m) where
  sizeOf# :: Mod m -> Int#
sizeOf# Mod m
x    = let !(I# Int#
sz#) = forall a. Storable a => a -> Int
sizeOf Mod m
x    in Int#
sz#
  {-# INLINE sizeOf# #-}

  alignment# :: Mod m -> Int#
alignment# Mod m
x = let !(I# Int#
a#)  = forall a. Storable a => a -> Int
alignment Mod m
x in Int#
a#
  {-# INLINE alignment# #-}

  indexByteArray# :: BigNat# -> Int# -> Mod m
indexByteArray# BigNat#
arr# Int#
i' = case forall (n :: Natural). KnownNat n => Proxy# n -> Natural
natVal' (forall {k} (a :: k). Proxy# a
proxy# :: Proxy# m) of
    NatS#{} -> forall (m :: Natural). Natural -> Mod m
Mod (Word# -> Natural
NatS# Word#
w#)
      where
        !(W# Word#
w#) = forall a. Prim a => BigNat# -> Int# -> a
P.indexByteArray# BigNat#
arr# Int#
i'
    NatJ# (BN# BigNat#
m#) -> forall (m :: Natural). Natural -> Mod m
Mod forall a b. (a -> b) -> a -> b
$ BigNat# -> Natural
bigNatToNat (forall o. (State# RealWorld -> o) -> o
runRW# (\State# RealWorld
token -> case forall s.
Word# -> BigNat# -> Word# -> State# s -> (# State# s, BigNat# #)
bigNatFromByteArrayLE# (Int# -> Word#
int2Word# Int#
sz#) BigNat#
arr# (Int# -> Word#
int2Word# Int#
i#) State# RealWorld
token of (# State# RealWorld
_, BigNat#
bn# #) -> BigNat#
bn#))
      where
        !(I# Int#
lgWordSize#) = Int
lgWordSize
        sz# :: Int#
sz# = BigNat# -> Int#
bigNatSize# BigNat#
m# Int# -> Int# -> Int#
`iShiftL#` Int#
lgWordSize#
        i# :: Int#
i# = Int#
i' Int# -> Int# -> Int#
*# Int#
sz#
  {-# INLINE indexByteArray# #-}

  indexOffAddr# :: Addr# -> Int# -> Mod m
indexOffAddr# Addr#
arr# Int#
i' = case forall (n :: Natural). KnownNat n => Proxy# n -> Natural
natVal' (forall {k} (a :: k). Proxy# a
proxy# :: Proxy# m) of
    NatS#{} -> forall (m :: Natural). Natural -> Mod m
Mod (Word# -> Natural
NatS# Word#
w#)
      where
        !(W# Word#
w#) = forall a. Prim a => Addr# -> Int# -> a
P.indexOffAddr# Addr#
arr# Int#
i'
    NatJ# (BN# BigNat#
m#) -> forall (m :: Natural). Natural -> Mod m
Mod forall a b. (a -> b) -> a -> b
$ BigNat# -> Natural
bigNatToNat (forall o. (State# RealWorld -> o) -> o
runRW# (\State# RealWorld
token -> case forall s. Word# -> Addr# -> State# s -> (# State# s, BigNat# #)
bigNatFromAddrLE# (Int# -> Word#
int2Word# Int#
sz#) (Addr#
arr# Addr# -> Int# -> Addr#
`plusAddr#` Int#
i#) State# RealWorld
token of (# State# RealWorld
_, BigNat#
bn# #) -> BigNat#
bn#))
      where
        !(I# Int#
lgWordSize#) = Int
lgWordSize
        sz# :: Int#
sz# = BigNat# -> Int#
bigNatSize# BigNat#
m# Int# -> Int# -> Int#
`iShiftL#` Int#
lgWordSize#
        i# :: Int#
i# = Int#
i' Int# -> Int# -> Int#
*# Int#
sz#
  {-# INLINE indexOffAddr# #-}

  readByteArray# :: forall s.
MutableByteArray# s -> Int# -> State# s -> (# State# s, Mod m #)
readByteArray# MutableByteArray# s
marr !Int#
i' State# s
token = case forall (n :: Natural). KnownNat n => Proxy# n -> Natural
natVal' (forall {k} (a :: k). Proxy# a
proxy# :: Proxy# m) of
    NatS#{} -> case forall a s.
Prim a =>
MutableByteArray# s -> Int# -> State# s -> (# State# s, a #)
P.readByteArray# MutableByteArray# s
marr Int#
i' State# s
token of
      (# State# s
newToken, W# Word#
w# #) -> (# State# s
newToken, forall (m :: Natural). Natural -> Mod m
Mod (Word# -> Natural
NatS# Word#
w#) #)
    NatJ# (BN# BigNat#
m#) -> case forall d.
MutableByteArray# d -> State# d -> (# State# d, BigNat# #)
unsafeFreezeByteArray# MutableByteArray# s
marr State# s
token of
      (# State# s
newToken, BigNat#
arr #) -> case forall s.
Word# -> BigNat# -> Word# -> State# s -> (# State# s, BigNat# #)
bigNatFromByteArrayLE# (Int# -> Word#
int2Word# Int#
sz#) BigNat#
arr (Int# -> Word#
int2Word# Int#
i#) State# s
newToken of
        (# State# s
veryNewToken, BigNat#
bn# #) -> (# State# s
veryNewToken,forall (m :: Natural). Natural -> Mod m
Mod (BigNat# -> Natural
bigNatToNat BigNat#
bn#) #)
      where
        !(I# Int#
lgWordSize#) = Int
lgWordSize
        sz# :: Int#
sz# = BigNat# -> Int#
bigNatSize# BigNat#
m# Int# -> Int# -> Int#
`iShiftL#` Int#
lgWordSize#
        i# :: Int#
i# = Int#
i' Int# -> Int# -> Int#
*# Int#
sz#
  {-# INLINE readByteArray# #-}

  readOffAddr# :: forall s. Addr# -> Int# -> State# s -> (# State# s, Mod m #)
readOffAddr# Addr#
marr !Int#
i' State# s
token = case forall (n :: Natural). KnownNat n => Proxy# n -> Natural
natVal' (forall {k} (a :: k). Proxy# a
proxy# :: Proxy# m) of
    NatS#{} -> case forall a s.
Prim a =>
Addr# -> Int# -> State# s -> (# State# s, a #)
P.readOffAddr# Addr#
marr Int#
i' State# s
token of
      (# State# s
newToken, W# Word#
w# #) -> (# State# s
newToken, forall (m :: Natural). Natural -> Mod m
Mod (Word# -> Natural
NatS# Word#
w#) #)
    NatJ# (BN# BigNat#
m#) -> case forall s. Word# -> Addr# -> State# s -> (# State# s, BigNat# #)
bigNatFromAddrLE# (Int# -> Word#
int2Word# Int#
sz#) (Addr#
marr Addr# -> Int# -> Addr#
`plusAddr#` Int#
i#) State# s
token of
      (# State# s
newToken, BigNat#
bn #) -> (# State# s
newToken, forall (m :: Natural). Natural -> Mod m
Mod (BigNat# -> Natural
bigNatToNat BigNat#
bn) #)
      where
        !(I# Int#
lgWordSize#) = Int
lgWordSize
        sz# :: Int#
sz# = BigNat# -> Int#
bigNatSize# BigNat#
m# Int# -> Int# -> Int#
`iShiftL#` Int#
lgWordSize#
        i# :: Int#
i# = Int#
i' Int# -> Int# -> Int#
*# Int#
sz#
  {-# INLINE readOffAddr# #-}

  writeByteArray# :: forall s.
MutableByteArray# s -> Int# -> Mod m -> State# s -> State# s
writeByteArray# MutableByteArray# s
marr !Int#
i' !(Mod Natural
x) State# s
token = case forall (n :: Natural). KnownNat n => Proxy# n -> Natural
natVal' (forall {k} (a :: k). Proxy# a
proxy# :: Proxy# m) of
    NatS#{} -> case Natural
x of
      NatS# Word#
x# -> forall a s.
Prim a =>
MutableByteArray# s -> Int# -> a -> State# s -> State# s
P.writeByteArray# MutableByteArray# s
marr Int#
i' (Word# -> Word
W# Word#
x#) State# s
token
      Natural
_        -> forall a. HasCallStack => String -> a
error String
"argument is larger than modulus"
    NatJ# (BN# BigNat#
m#) -> case Natural
x of
      NatS# Word#
x# -> case forall a s.
Prim a =>
MutableByteArray# s -> Int# -> a -> State# s -> State# s
P.writeByteArray# MutableByteArray# s
marr Int#
i# (Word# -> Word
W# Word#
x#) State# s
token of
        State# s
newToken -> forall a s.
Prim a =>
MutableByteArray# s -> Int# -> Int# -> a -> State# s -> State# s
P.setByteArray# MutableByteArray# s
marr (Int#
i# Int# -> Int# -> Int#
+# Int#
1#) (Int#
sz# Int# -> Int# -> Int#
-# Int#
1#) (Word
0 :: Word) State# s
newToken
      NatJ# (BN# BigNat#
bn) -> case forall s.
BigNat#
-> MutableByteArray# s
-> Word#
-> State# s
-> (# State# s, Word# #)
bigNatToMutableByteArrayLE# BigNat#
bn (unsafeCoerce# :: forall a b. a -> b
unsafeCoerce# MutableByteArray# s
marr) (Int# -> Word#
int2Word# (Int#
i# Int# -> Int# -> Int#
`iShiftL#` Int#
lgWordSize#)) State# s
token of
        (# State# s
newToken, Word#
l# #) -> forall a s.
Prim a =>
MutableByteArray# s -> Int# -> Int# -> a -> State# s -> State# s
P.setByteArray# MutableByteArray# s
marr (Int#
i# Int# -> Int# -> Int#
`iShiftL#` Int#
lgWordSize# Int# -> Int# -> Int#
+# Word# -> Int#
word2Int# Word#
l#) (Int#
sz# Int# -> Int# -> Int#
`iShiftL#` Int#
lgWordSize# Int# -> Int# -> Int#
-# Word# -> Int#
word2Int# Word#
l#) (Word8
0 :: Word8) State# s
newToken
      where
        !(I# Int#
lgWordSize#) = Int
lgWordSize
        !sz :: Int
sz@(I# Int#
sz#) = Int# -> Int
I# (BigNat# -> Int#
bigNatSize# BigNat#
m#)
        !(I# Int#
i#)     = Int# -> Int
I# Int#
i' forall a. Num a => a -> a -> a
* Int
sz
  {-# INLINE writeByteArray# #-}

  writeOffAddr# :: forall s. Addr# -> Int# -> Mod m -> State# s -> State# s
writeOffAddr# Addr#
marr !Int#
i' !(Mod Natural
x) State# s
token = case forall (n :: Natural). KnownNat n => Proxy# n -> Natural
natVal' (forall {k} (a :: k). Proxy# a
proxy# :: Proxy# m) of
    NatS#{} -> case Natural
x of
      NatS# Word#
x# -> forall a s. Prim a => Addr# -> Int# -> a -> State# s -> State# s
P.writeOffAddr# Addr#
marr Int#
i' (Word# -> Word
W# Word#
x#) State# s
token
      Natural
_        -> forall a. HasCallStack => String -> a
error String
"argument is larger than modulus"
    NatJ# (BN# BigNat#
m#) -> case Natural
x of
      NatS# Word#
x# -> case forall a s. Prim a => Addr# -> Int# -> a -> State# s -> State# s
P.writeOffAddr# Addr#
marr Int#
i# (Word# -> Word
W# Word#
x#) State# s
token of
        State# s
newToken -> forall a s.
Prim a =>
Addr# -> Int# -> Int# -> a -> State# s -> State# s
P.setOffAddr# Addr#
marr (Int#
i# Int# -> Int# -> Int#
+# Int#
1#) (Int#
sz# Int# -> Int# -> Int#
-# Int#
1#) (Word
0 :: Word) State# s
newToken
      NatJ# (BN# BigNat#
bn) -> case forall s. BigNat# -> Addr# -> State# s -> (# State# s, Word# #)
bigNatToAddrLE# BigNat#
bn (Addr#
marr Addr# -> Int# -> Addr#
`plusAddr#` (Int#
i# Int# -> Int# -> Int#
`iShiftL#` Int#
lgWordSize#)) State# s
token of
        (# State# s
newToken, Word#
l# #) -> forall a s.
Prim a =>
Addr# -> Int# -> Int# -> a -> State# s -> State# s
P.setOffAddr# Addr#
marr (Int#
i# Int# -> Int# -> Int#
`iShiftL#` Int#
lgWordSize# Int# -> Int# -> Int#
+# Word# -> Int#
word2Int# Word#
l#) (Int#
sz# Int# -> Int# -> Int#
`iShiftL#` Int#
lgWordSize# Int# -> Int# -> Int#
-# Word# -> Int#
word2Int# Word#
l#) (Word8
0 :: Word8) State# s
newToken
      where
        !(I# Int#
lgWordSize#) = Int
lgWordSize
        !sz :: Int
sz@(I# Int#
sz#) = Int# -> Int
I# (BigNat# -> Int#
bigNatSize# BigNat#
m#)
        !(I# Int#
i#)   = Int# -> Int
I# Int#
i' forall a. Num a => a -> a -> a
* Int
sz
  {-# INLINE writeOffAddr# #-}

  setByteArray# :: forall s.
MutableByteArray# s
-> Int# -> Int# -> Mod m -> State# s -> State# s
setByteArray# !MutableByteArray# s
_ !Int#
_ Int#
0# !Mod m
_ State# s
token = State# s
token
  setByteArray# MutableByteArray# s
marr Int#
off Int#
len mx :: Mod m
mx@(Mod Natural
x) State# s
token = case forall (n :: Natural). KnownNat n => Proxy# n -> Natural
natVal' (forall {k} (a :: k). Proxy# a
proxy# :: Proxy# m) of
    NatS#{} -> case Natural
x of
      NatS# Word#
x# -> forall a s.
Prim a =>
MutableByteArray# s -> Int# -> Int# -> a -> State# s -> State# s
P.setByteArray# MutableByteArray# s
marr Int#
off Int#
len (Word# -> Word
W# Word#
x#) State# s
token
      Natural
_        -> forall a. HasCallStack => String -> a
error String
"argument is larger than modulus"
    NatJ# (BN# BigNat#
m#) -> case forall a s.
Prim a =>
MutableByteArray# s -> Int# -> a -> State# s -> State# s
P.writeByteArray# MutableByteArray# s
marr Int#
off Mod m
mx State# s
token of
      State# s
newToken -> Int# -> State# s -> State# s
doSet (Int#
sz Int# -> Int# -> Int#
`iShiftL#` Int#
lgWordSize#) State# s
newToken
      where
        !(I# Int#
lgWordSize#) = Int
lgWordSize
        sz :: Int#
sz = BigNat# -> Int#
bigNatSize# BigNat#
m#
        off' :: Int#
off' = (Int#
off Int# -> Int# -> Int#
*# Int#
sz) Int# -> Int# -> Int#
`iShiftL#` Int#
lgWordSize#
        len' :: Int#
len' = (Int#
len Int# -> Int# -> Int#
*# Int#
sz) Int# -> Int# -> Int#
`iShiftL#` Int#
lgWordSize#
        doSet :: Int# -> State# s -> State# s
doSet Int#
i State# s
tkn
          | Int# -> Bool
isTrue# (Int#
2# Int# -> Int# -> Int#
*# Int#
i Int# -> Int# -> Int#
<# Int#
len') = case forall d.
MutableByteArray# d
-> Int#
-> MutableByteArray# d
-> Int#
-> Int#
-> State# d
-> State# d
copyMutableByteArray# MutableByteArray# s
marr Int#
off' MutableByteArray# s
marr (Int#
off' Int# -> Int# -> Int#
+# Int#
i) Int#
i State# s
tkn of
            State# s
tkn' -> Int# -> State# s -> State# s
doSet (Int#
2# Int# -> Int# -> Int#
*# Int#
i) State# s
tkn'
          | Bool
otherwise    = forall d.
MutableByteArray# d
-> Int#
-> MutableByteArray# d
-> Int#
-> Int#
-> State# d
-> State# d
copyMutableByteArray# MutableByteArray# s
marr Int#
off' MutableByteArray# s
marr (Int#
off' Int# -> Int# -> Int#
+# Int#
i) (Int#
len' Int# -> Int# -> Int#
-# Int#
i) State# s
tkn
  {-# INLINE setByteArray# #-}

  setOffAddr# :: forall s. Addr# -> Int# -> Int# -> Mod m -> State# s -> State# s
setOffAddr# !Addr#
_ !Int#
_ Int#
0# !Mod m
_ State# s
token = State# s
token
  setOffAddr# Addr#
marr Int#
off Int#
len mx :: Mod m
mx@(Mod Natural
x) State# s
token = case forall (n :: Natural). KnownNat n => Proxy# n -> Natural
natVal' (forall {k} (a :: k). Proxy# a
proxy# :: Proxy# m) of
    NatS#{} -> case Natural
x of
      NatS# Word#
x# -> forall a s.
Prim a =>
Addr# -> Int# -> Int# -> a -> State# s -> State# s
P.setOffAddr# Addr#
marr Int#
off Int#
len (Word# -> Word
W# Word#
x#) State# s
token
      Natural
_        -> forall a. HasCallStack => String -> a
error String
"argument is larger than modulus"
    NatJ# (BN# BigNat#
m#) -> case forall a s. Prim a => Addr# -> Int# -> a -> State# s -> State# s
P.writeOffAddr# Addr#
marr Int#
off Mod m
mx State# s
token of
      State# s
newToken -> Int# -> State# s -> State# s
doSet (Int#
sz Int# -> Int# -> Int#
`iShiftL#` Int#
lgWordSize#) State# s
newToken
      where
        !(I# Int#
lgWordSize#) = Int
lgWordSize
        sz :: Int#
sz = BigNat# -> Int#
bigNatSize# BigNat#
m#
        off' :: Int#
off' = (Int#
off Int# -> Int# -> Int#
*# Int#
sz) Int# -> Int# -> Int#
`iShiftL#` Int#
lgWordSize#
        len' :: Int#
len' = (Int#
len Int# -> Int# -> Int#
*# Int#
sz) Int# -> Int# -> Int#
`iShiftL#` Int#
lgWordSize#
        doSet :: Int# -> State# s -> State# s
doSet Int#
i State# s
tkn -- = tkn
          | Int# -> Bool
isTrue# (Int#
2# Int# -> Int# -> Int#
*# Int#
i Int# -> Int# -> Int#
<# Int#
len') = case forall (m :: * -> *) a.
PrimBase m =>
m a -> State# (PrimState m) -> (# State# (PrimState m), a #)
internal (forall (m :: * -> *) a. PrimMonad m => IO a -> m a
unsafeIOToPrim (forall a. Ptr a -> Ptr a -> Int -> IO ()
copyBytes (forall a. Addr# -> Ptr a
Ptr (Addr#
marr Addr# -> Int# -> Addr#
`plusAddr#` (Int#
off' Int# -> Int# -> Int#
+# Int#
i))) (forall a. Addr# -> Ptr a
Ptr (Addr#
marr Addr# -> Int# -> Addr#
`plusAddr#` Int#
off')) (Int# -> Int
I# Int#
i)) :: ST s ()) State# s
tkn of
            (# State# (PrimState (ST s))
tkn', () #) -> Int# -> State# s -> State# s
doSet (Int#
2# Int# -> Int# -> Int#
*# Int#
i) State# (PrimState (ST s))
tkn'
          | Bool
otherwise    = case forall (m :: * -> *) a.
PrimBase m =>
m a -> State# (PrimState m) -> (# State# (PrimState m), a #)
internal (forall (m :: * -> *) a. PrimMonad m => IO a -> m a
unsafeIOToPrim (forall a. Ptr a -> Ptr a -> Int -> IO ()
copyBytes (forall a. Addr# -> Ptr a
Ptr (Addr#
marr Addr# -> Int# -> Addr#
`plusAddr#` (Int#
off' Int# -> Int# -> Int#
+# Int#
i))) (forall a. Addr# -> Ptr a
Ptr (Addr#
marr Addr# -> Int# -> Addr#
`plusAddr#` Int#
off')) (Int# -> Int
I# (Int#
len' Int# -> Int# -> Int#
-# Int#
i))) :: ST s ()) State# s
tkn of
            (# State# (PrimState (ST s))
tkn', () #) -> State# (PrimState (ST s))
tkn'
  {-# INLINE setOffAddr# #-}

-- | Unboxed vectors of 'Mod' cause more nursery allocations
-- than boxed ones, but reduce pressure on the garbage collector,
-- especially for large vectors.
newtype instance U.MVector s (Mod m) = ModMVec (P.MVector s (Mod m))

-- | Unboxed vectors of 'Mod' cause more nursery allocations
-- than boxed ones, but reduce pressure on the garbage collector,
-- especially for large vectors.
newtype instance U.Vector    (Mod m) = ModVec  (P.Vector (Mod m))

-- | No validation checks are performed;
-- reading untrusted data may corrupt internal invariants.
instance KnownNat m => U.Unbox (Mod m)

-- | No validation checks are performed;
-- reading untrusted data may corrupt internal invariants.
instance KnownNat m => M.MVector U.MVector (Mod m) where
  {-# INLINE basicLength #-}
  {-# INLINE basicUnsafeSlice #-}
  {-# INLINE basicOverlaps #-}
  {-# INLINE basicUnsafeNew #-}
  {-# INLINE basicInitialize #-}
  {-# INLINE basicUnsafeReplicate #-}
  {-# INLINE basicUnsafeRead #-}
  {-# INLINE basicUnsafeWrite #-}
  {-# INLINE basicClear #-}
  {-# INLINE basicSet #-}
  {-# INLINE basicUnsafeCopy #-}
  {-# INLINE basicUnsafeGrow #-}
  basicLength :: forall s. MVector s (Mod m) -> Int
basicLength (ModMVec MVector s (Mod m)
v) = forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
M.basicLength MVector s (Mod m)
v
  basicUnsafeSlice :: forall s. Int -> Int -> MVector s (Mod m) -> MVector s (Mod m)
basicUnsafeSlice Int
i Int
n (ModMVec MVector s (Mod m)
v) = forall s (m :: Natural). MVector s (Mod m) -> MVector s (Mod m)
ModMVec forall a b. (a -> b) -> a -> b
$ forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
M.basicUnsafeSlice Int
i Int
n MVector s (Mod m)
v
  basicOverlaps :: forall s. MVector s (Mod m) -> MVector s (Mod m) -> Bool
basicOverlaps (ModMVec MVector s (Mod m)
v1) (ModMVec MVector s (Mod m)
v2) = forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> v s a -> Bool
M.basicOverlaps MVector s (Mod m)
v1 MVector s (Mod m)
v2
  basicUnsafeNew :: forall s. Int -> ST s (MVector s (Mod m))
basicUnsafeNew Int
n = forall s (m :: Natural). MVector s (Mod m) -> MVector s (Mod m)
ModMVec forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
`liftM` forall (v :: * -> * -> *) a s. MVector v a => Int -> ST s (v s a)
M.basicUnsafeNew Int
n
  basicInitialize :: forall s. MVector s (Mod m) -> ST s ()
basicInitialize (ModMVec MVector s (Mod m)
v) = forall (v :: * -> * -> *) a s. MVector v a => v s a -> ST s ()
M.basicInitialize MVector s (Mod m)
v
  basicUnsafeReplicate :: forall s. Int -> Mod m -> ST s (MVector s (Mod m))
basicUnsafeReplicate Int
n Mod m
x = forall s (m :: Natural). MVector s (Mod m) -> MVector s (Mod m)
ModMVec forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
`liftM` forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> a -> ST s (v s a)
M.basicUnsafeReplicate Int
n Mod m
x
  basicUnsafeRead :: forall s. MVector s (Mod m) -> Int -> ST s (Mod m)
basicUnsafeRead (ModMVec MVector s (Mod m)
v) Int
i = forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> Int -> ST s a
M.basicUnsafeRead MVector s (Mod m)
v Int
i
  basicUnsafeWrite :: forall s. MVector s (Mod m) -> Int -> Mod m -> ST s ()
basicUnsafeWrite (ModMVec MVector s (Mod m)
v) Int
i Mod m
x = forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> Int -> a -> ST s ()
M.basicUnsafeWrite MVector s (Mod m)
v Int
i Mod m
x
  basicClear :: forall s. MVector s (Mod m) -> ST s ()
basicClear (ModMVec MVector s (Mod m)
v) = forall (v :: * -> * -> *) a s. MVector v a => v s a -> ST s ()
M.basicClear MVector s (Mod m)
v
  basicSet :: forall s. MVector s (Mod m) -> Mod m -> ST s ()
basicSet (ModMVec MVector s (Mod m)
v) Mod m
x = forall (v :: * -> * -> *) a s. MVector v a => v s a -> a -> ST s ()
M.basicSet MVector s (Mod m)
v Mod m
x
  basicUnsafeCopy :: forall s. MVector s (Mod m) -> MVector s (Mod m) -> ST s ()
basicUnsafeCopy (ModMVec MVector s (Mod m)
v1) (ModMVec MVector s (Mod m)
v2) = forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> v s a -> ST s ()
M.basicUnsafeCopy MVector s (Mod m)
v1 MVector s (Mod m)
v2
  basicUnsafeMove :: forall s. MVector s (Mod m) -> MVector s (Mod m) -> ST s ()
basicUnsafeMove (ModMVec MVector s (Mod m)
v1) (ModMVec MVector s (Mod m)
v2) = forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> v s a -> ST s ()
M.basicUnsafeMove MVector s (Mod m)
v1 MVector s (Mod m)
v2
  basicUnsafeGrow :: forall s. MVector s (Mod m) -> Int -> ST s (MVector s (Mod m))
basicUnsafeGrow (ModMVec MVector s (Mod m)
v) Int
n = forall s (m :: Natural). MVector s (Mod m) -> MVector s (Mod m)
ModMVec forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
`liftM` forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> Int -> ST s (v s a)
M.basicUnsafeGrow MVector s (Mod m)
v Int
n

-- | No validation checks are performed;
-- reading untrusted data may corrupt internal invariants.
instance KnownNat m => G.Vector U.Vector (Mod m) where
  {-# INLINE basicUnsafeFreeze #-}
  {-# INLINE basicUnsafeThaw #-}
  {-# INLINE basicLength #-}
  {-# INLINE basicUnsafeSlice #-}
  {-# INLINE basicUnsafeIndexM #-}
  {-# INLINE elemseq #-}
  basicUnsafeFreeze :: forall s. Mutable Vector s (Mod m) -> ST s (Vector (Mod m))
basicUnsafeFreeze (ModMVec MVector s (Mod m)
v) = forall (m :: Natural). Vector (Mod m) -> Vector (Mod m)
ModVec forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
`liftM` forall (v :: * -> *) a s. Vector v a => Mutable v s a -> ST s (v a)
G.basicUnsafeFreeze MVector s (Mod m)
v
  basicUnsafeThaw :: forall s. Vector (Mod m) -> ST s (Mutable Vector s (Mod m))
basicUnsafeThaw (ModVec Vector (Mod m)
v) = forall s (m :: Natural). MVector s (Mod m) -> MVector s (Mod m)
ModMVec forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
`liftM` forall (v :: * -> *) a s. Vector v a => v a -> ST s (Mutable v s a)
G.basicUnsafeThaw Vector (Mod m)
v
  basicLength :: Vector (Mod m) -> Int
basicLength (ModVec Vector (Mod m)
v) = forall (v :: * -> *) a. Vector v a => v a -> Int
G.basicLength Vector (Mod m)
v
  basicUnsafeSlice :: Int -> Int -> Vector (Mod m) -> Vector (Mod m)
basicUnsafeSlice Int
i Int
n (ModVec Vector (Mod m)
v) = forall (m :: Natural). Vector (Mod m) -> Vector (Mod m)
ModVec forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a. Vector v a => Int -> Int -> v a -> v a
G.basicUnsafeSlice Int
i Int
n Vector (Mod m)
v
  basicUnsafeIndexM :: Vector (Mod m) -> Int -> Box (Mod m)
basicUnsafeIndexM (ModVec Vector (Mod m)
v) Int
i = forall (v :: * -> *) a. Vector v a => v a -> Int -> Box a
G.basicUnsafeIndexM Vector (Mod m)
v Int
i
  basicUnsafeCopy :: forall s. Mutable Vector s (Mod m) -> Vector (Mod m) -> ST s ()
basicUnsafeCopy (ModMVec MVector s (Mod m)
mv) (ModVec Vector (Mod m)
v) = forall (v :: * -> *) a s.
Vector v a =>
Mutable v s a -> v a -> ST s ()
G.basicUnsafeCopy MVector s (Mod m)
mv Vector (Mod m)
v
  elemseq :: forall b. Vector (Mod m) -> Mod m -> b -> b
elemseq Vector (Mod m)
_ = seq :: forall a b. a -> b -> b
seq

#endif