modular 0.1.0.7 → 0.1.0.8
raw patch · 2 files changed
+30/−25 lines, 2 files
Files
- modular.cabal +3/−3
- src/Numeric/Modular.hs +27/−22
modular.cabal view
@@ -4,12 +4,12 @@ -- -- see: https://github.com/sol/hpack ----- hash: 804311adb70c067aeb3a5d243c42fc84b25541647151c090b4425f273b520348+-- hash: a2b1bfd41102ff46632bb1c6bb336a8cb209b413b48db135145b63d2a624e76d name: modular-version: 0.1.0.7+version: 0.1.0.8 synopsis: Type-safe modular arithmetic-description: Please the module documentation for Numeric.Modular.+description: Please see the GitHub page at <https://github.com/pgujjula/modular> for installation instructions, and the module documentation for Numeric.Modular for usage instructions. category: Math homepage: https://github.com/pgujjula/modular#readme bug-reports: https://github.com/pgujjula/modular/issues
src/Numeric/Modular.hs view
@@ -5,11 +5,13 @@ Maintainer : preetham.gujjula@gmail.com Stability : experimental - The @'Mod' m@ type represents a Integer modulo m, i.e., a value in ℤ/mℤ, which enables type-safe modular arithmetic.+ The @'Mod' m@ type represents a Integer modulo m, i.e., a value in ℤ/mℤ,+ which enables type-safe modular arithmetic. This library, especially the 'withMod' function, uses ideas from- /Functional Pearl: Implicit Configurations -- or, Type Classes Reflect the Values of Types/ by Oleg Kiselyov and Chung-chieh Shan,- available here: <http://okmij.org/ftp/Haskell/tr-15-04.pdf>+ /Functional Pearl: Implicit Configurations — or, Type Classes Reflect the/+ /Values of Types/ by Oleg Kiselyov and Chung-chieh Shan, available here:+ <http://okmij.org/ftp/Haskell/tr-15-04.pdf>. For example, to perform basic modular computations, @@ -18,22 +20,17 @@ >>> 15 + 3 :: Mod 7 4 - Attempts to perform arithmetic on different modular types result in type errors.-- >>> (10 :: Mod 3) + (15 :: Mod 7)- (...)error:- • Couldn't match type ‘7’ with ‘3’- (...)-- Modular reductions are performed implicitly, so modular exponentiation can be performed efficiently.+ Modular reductions are performed implicitly, so modular exponentiation can+ be performed efficiently. >>> 60803790666453028877 ^ 88100461154844882932 :: Mod 39127526509442054532 33479467020524411041 - Compare this to running @(60803790666453028877 ^ 88100461154844882932) \``mod`\` 39127526509442054532@, which is- much less efficient.+ Compare this to running @(60803790666453028877 ^ 88100461154844882932)+ \``mod`\` 39127526509442054532@, which is much less efficient. - The modulus can also be specified at runtime without losing any type safety or efficiency.+ The modulus can also be specified at runtime without losing any type safety+ or efficiency. >>> x = mkMod 10 >>> y = mkMod 17@@ -48,12 +45,15 @@ 33479467020524411041 -} -{-# LANGUAGE DataKinds, TypeFamilies, TypeOperators, GADTs, Rank2Types, ScopedTypeVariables, CPP #-}+{-# LANGUAGE DataKinds, TypeFamilies, TypeOperators, GADTs, Rank2Types,+ ScopedTypeVariables, CPP #-}+ #ifdef MIN_VERSION_GLASGOW_HASKELL #if MIN_VERSION_GLASGOW_HASKELL(8,6,1,0) {-# LANGUAGE NoStarIsType #-} #endif #endif+ {-# OPTIONS_GHC -fplugin GHC.TypeLits.KnownNat.Solver #-} module Numeric.Modular@@ -87,10 +87,11 @@ withMod :: Integer -> (forall m. (KnownNat m) => Mod m) -> Integer withMod k m = reifyInteger k (withModProxy m) -{- Given a polymorphic modular value and a proxy for the modulus Nat, resolve the modular value- using the given modulus.+{- Given a polymorphic modular value and a proxy for the modulus Nat, resolve+ the modular value using the given modulus. -}-withModProxy :: forall m. KnownNat m => (forall n. (KnownNat n) => Mod n) -> Proxy m -> Integer+withModProxy :: forall m. KnownNat m+ => (forall n. (KnownNat n) => Mod n) -> Proxy m -> Integer withModProxy k modProxy = (getV (k :: Mod m)) `mod` (natVal modProxy) {- Get the modulus m as a integer of a value of type Mod m. -}@@ -101,14 +102,18 @@ getV :: forall m. (KnownNat m) => Mod m -> Integer getV (Mod k) = k -{- The implementation of "reifyIntegral" from the Implicit Configurations paper adapted- to the current context.+{- The implementation of "reifyIntegral" from the Implicit Configurations paper+ adapted to the current context. -} reifyInteger :: Integer -> (forall n. (KnownNat n) => Proxy n -> w) -> w reifyInteger 0 f = f (Proxy :: Proxy 0) reifyInteger n f- | even n = reifyInteger (n `div` 2) (\(Proxy :: Proxy n) -> f (Proxy :: Proxy (n * 2)))- | otherwise = reifyInteger (n - 1) (\(Proxy :: Proxy n) -> f (Proxy :: Proxy (n + 1)))+ | even n = reifyInteger+ (n `div` 2)+ (\(Proxy :: Proxy n) -> f (Proxy :: Proxy (n * 2)))+ | otherwise = reifyInteger+ (n - 1)+ (\(Proxy :: Proxy n) -> f (Proxy :: Proxy (n + 1))) instance Eq (Mod m) where (==) (Mod a) (Mod b) = a == b