Safe Haskell	Safe-Inferred
Language	GHC2021

Data.RollingHash

Synopsis

newtype RollingHash (b :: Nat) = RollingHash {
- getRollingHash :: Int
}
asRollingHashOf :: RollingHash b -> Proxy b -> RollingHash b
isPrimitiveRootRH :: Int -> Bool
genPrimitiveRootRH :: RandomGen g => g -> Int
withPrimitiveRootRH :: RandomGen g => g -> (forall b. KnownNat b => Proxy b -> a) -> a

Documentation

newtype RollingHash (b :: Nat) Source #

modulo 2^61-1

b should be a primitive root of 2^61-1

Constructors

RollingHash
Fields getRollingHash :: Int

Instances

Instances details

Vector Vector (RollingHash b) Source #
Instance details Defined in Data.RollingHash Methods basicUnsafeFreeze :: Mutable Vector s (RollingHash b) -> ST s (Vector (RollingHash b)) basicUnsafeThaw :: Vector (RollingHash b) -> ST s (Mutable Vector s (RollingHash b)) basicLength :: Vector (RollingHash b) -> Int basicUnsafeSlice :: Int -> Int -> Vector (RollingHash b) -> Vector (RollingHash b) basicUnsafeIndexM :: Vector (RollingHash b) -> Int -> Box (RollingHash b) basicUnsafeCopy :: Mutable Vector s (RollingHash b) -> Vector (RollingHash b) -> ST s () elemseq :: Vector (RollingHash b) -> RollingHash b -> b0 -> b0
MVector MVector (RollingHash b) Source #
Instance details Defined in Data.RollingHash Methods basicLength :: MVector s (RollingHash b) -> Int basicUnsafeSlice :: Int -> Int -> MVector s (RollingHash b) -> MVector s (RollingHash b) basicOverlaps :: MVector s (RollingHash b) -> MVector s (RollingHash b) -> Bool basicUnsafeNew :: Int -> ST s (MVector s (RollingHash b)) basicInitialize :: MVector s (RollingHash b) -> ST s () basicUnsafeReplicate :: Int -> RollingHash b -> ST s (MVector s (RollingHash b)) basicUnsafeRead :: MVector s (RollingHash b) -> Int -> ST s (RollingHash b) basicUnsafeWrite :: MVector s (RollingHash b) -> Int -> RollingHash b -> ST s () basicClear :: MVector s (RollingHash b) -> ST s () basicSet :: MVector s (RollingHash b) -> RollingHash b -> ST s () basicUnsafeCopy :: MVector s (RollingHash b) -> MVector s (RollingHash b) -> ST s () basicUnsafeMove :: MVector s (RollingHash b) -> MVector s (RollingHash b) -> ST s () basicUnsafeGrow :: MVector s (RollingHash b) -> Int -> ST s (MVector s (RollingHash b))
Num (RollingHash b) Source #
Instance details Defined in Data.RollingHash Methods (+) :: RollingHash b -> RollingHash b -> RollingHash b # (-) :: RollingHash b -> RollingHash b -> RollingHash b # (*) :: RollingHash b -> RollingHash b -> RollingHash b # negate :: RollingHash b -> RollingHash b # abs :: RollingHash b -> RollingHash b # signum :: RollingHash b -> RollingHash b # fromInteger :: Integer -> RollingHash b #
Show (RollingHash b) Source #
Instance details Defined in Data.RollingHash Methods showsPrec :: Int -> RollingHash b -> ShowS # show :: RollingHash b -> String # showList :: [RollingHash b] -> ShowS #
Eq (RollingHash b) Source #
Instance details Defined in Data.RollingHash Methods (==) :: RollingHash b -> RollingHash b -> Bool # (/=) :: RollingHash b -> RollingHash b -> Bool #
Ord (RollingHash b) Source #
Instance details Defined in Data.RollingHash Methods compare :: RollingHash b -> RollingHash b -> Ordering # (<) :: RollingHash b -> RollingHash b -> Bool # (<=) :: RollingHash b -> RollingHash b -> Bool # (>) :: RollingHash b -> RollingHash b -> Bool # (>=) :: RollingHash b -> RollingHash b -> Bool # max :: RollingHash b -> RollingHash b -> RollingHash b # min :: RollingHash b -> RollingHash b -> RollingHash b #
Unbox (RollingHash b) Source #
Instance details Defined in Data.RollingHash
newtype MVector s (RollingHash b) Source #
Instance details Defined in Data.RollingHash newtype MVector s (RollingHash b) = MV_RollingHash (MVector s Int)
newtype Vector (RollingHash b) Source #
Instance details Defined in Data.RollingHash newtype Vector (RollingHash b) = V_RollingHash (Vector Int)

asRollingHashOf :: RollingHash b -> Proxy b -> RollingHash b Source #

isPrimitiveRootRH :: Int -> Bool Source #

check if g is a primitive root of 2^61-1.

>>> isPrimitiveRootRH 2047
True
>>> take 10 $ filter isPrimitiveRootRH [2..]
[37,43,55,69,74,86,110,123,133,138]

genPrimitiveRootRH :: RandomGen g => g -> Int Source #

Generate a primitive root of 2^61-1.

>>> genPrimitiveRootRH (mkStdGen 123)
1600615663002506808
>>> isPrimitiveRootRH 1600615663002506808
True

withPrimitiveRootRH :: RandomGen g => g -> (forall b. KnownNat b => Proxy b -> a) -> a Source #

>>> withPrimitiveRootRH (mkStdGen 123) $ \proxy -> getRollingHash $ 456 `asRollingHashOf` proxy
456