modular-arithmetic 1.2.1.0 → 1.2.1.1
raw patch · 5 files changed
+134/−38 lines, 5 filesdep +Globdep +doctestdep ~base
Dependencies added: Glob, doctest
Dependency ranges changed: base
Files
- CHANGELOG.md +7/−0
- README.md +30/−0
- modular-arithmetic.cabal +14/−5
- src/Data/Modular.hs +76/−33
- test-suite/DocTest.hs +7/−0
+ CHANGELOG.md view
@@ -0,0 +1,7 @@+1.2.1.0+---+* changed `Integral` implementation: `quotRem` now uses modular inversion!+* added `inv` for modular inversion+* added `SomeMod` data type for modular number with unknown modulus+* added `modVal` and `someModVal` helpers similar to ones in `GHC.TypeLits`+
+ README.md view
@@ -0,0 +1,30 @@+# Modular Arithmetic++[](http://hackage.haskell.org/package/modular-arithmetic)+[](https://travis-ci.org/TikhonJelvis/modular-arithmetic)++This package provides a type for integers modulo some constant, usually written as ℤ/n. ++Here is a quick example:++```+>>> 10 * 11 :: ℤ/7+5+```++It also works correctly with negative numeric literals:++```+>>> (-10) * 11 :: ℤ/7+2+```++Modular division is an inverse of modular multiplication.+It is defined when divisor is coprime to modulus:++```+>>> 7 `div` 3 :: ℤ/16+13+>>> 3 * 13 :: ℤ/16+7+```
modular-arithmetic.cabal view
@@ -1,20 +1,21 @@--- Initial Mod.cabal generated by cabal init. For further documentation, --- see http://haskell.org/cabal/users-guide/- name: modular-arithmetic-version: 1.2.1.0+version: 1.2.1.1 synopsis: A type for integers modulo some constant. description: A convenient type for working with integers modulo some constant. It saves you from manually wrapping numeric operations all over the place and prevents a range of simple mistakes. @Integer `Mod` 7@ is the type of integers (mod 7) backed by @Integer@. We also have some cute syntax for these types like @ℤ/7@ for integers modulo 7. +homepage: https://github.com/TikhonJelvis/modular-arithmetic+bug-reports: https://github.com/TikhonJelvis/modular-arithmetic/issues license: BSD3 license-file: LICENSE author: Tikhon Jelvis <tikhon@jelv.is>-maintainer: tikhon@jelv.is+maintainer: Tikhon Jelvis <tikhon@jelv.is> category: Math build-type: Simple+extra-source-files: README.md+ , CHANGELOG.md cabal-version: >=1.8 source-repository head@@ -26,3 +27,11 @@ ghc-options: -Wall exposed-modules: Data.Modular build-depends: base >=4.7 && <5++test-suite examples+ hs-source-dirs: test-suite+ main-is: DocTest.hs+ type: exitcode-stdio-1.0+ build-depends: base+ , Glob ==0.7.*+ , doctest ==0.9.*
src/Data/Modular.hs view
@@ -7,46 +7,79 @@ -- | -- Types for working with integers modulo some constant.--- +module Data.Modular (+ -- $doc++ -- * Preliminaries+ -- $setup++ -- * Modular arithmetic+ Mod,+ unMod, toMod, toMod',+ inv, (/)(), ℤ,+ modVal, SomeMod, someModVal+) where++import Control.Arrow (first)++import Data.Proxy (Proxy (..))+import Data.Ratio ((%))++import GHC.TypeLits++-- $setup+--+-- To use type level numeric literals you need to enable+-- the @DataKinds@ extension:+--+-- >>> :set -XDataKinds+--+-- To use infix syntax for @'Mod'@ or the @/@ synonym,+-- enable @TypeOperators@:+--+-- >>> :set -XTypeOperators++-- $doc+-- -- @'Mod'@ and its synonym @/@ let you wrap arbitrary numeric types--- in a modulus. To work with integers (mod 7) backed by @Integer@,--- you could write:+-- in a modulus. To work with integers (mod 7) backed by @'Integer'@,+-- you could use one of the following equivalent types: -- +-- > Mod Integer 7 -- > Integer `Mod` 7 -- > Integer/7 -- > ℤ/7 -- --- (The last is a synonym for @Integer@ provided by this library. In+-- (@'ℤ'@ is a synonym for @'Integer'@ provided by this library. In -- Emacs, you can use the TeX input mode to type it with @\\Bbb{Z}@.) -- -- The usual numeric typeclasses are defined for these types. You can--- always extrac the underlying value with @'unMod'@.+-- always extract the underlying value with @'unMod'@. -- -- Here is a quick example: -- --- > *Data.Modular> (10 :: ℤ/7) * (11 :: ℤ/7)--- > 5+-- >>> 10 * 11 :: ℤ/7+-- 5 -- -- It also works correctly with negative numeric literals: -- --- > *Data.Modular> (-10 :: ℤ/7) * (11 :: ℤ/7)--- > 2+-- >>> (-10) * 11 :: ℤ/7+-- 2 ----- To us type level numeric literals you need to enable the+-- Modular division is an inverse of modular multiplication.+-- It is defined when divisor is coprime to modulus:+--+-- >>> 7 `div` 3 :: ℤ/16+-- 13+-- >>> 3 * 13 :: ℤ/16+-- 7+--+-- To use type level numeric literals you need to enable the -- @DataKinds@ extension and to use infix syntax for @Mod@ or the @/@ -- synonym, you need @TypeOperators@. -module Data.Modular (unMod, toMod, toMod', Mod, inv, (/)(), ℤ, modVal, SomeMod, someModVal) where--import Control.Arrow (first)--import Data.Proxy (Proxy (..))-import Data.Ratio ((%))--import GHC.TypeLits---- | The actual type, wrapping an underlying @Integeral@ type @i@ in a--- newtype annotated with the bound.+-- | Wraps an underlying @Integeral@ type @i@ in a newtype annotated+-- with the bound @n@. newtype i `Mod` (n :: Nat) = Mod i deriving (Eq, Ord) -- | Extract the underlying integral value from a modular type.@@ -65,13 +98,12 @@ _bound :: forall n i. (Integral i, KnownNat n) => i `Mod` n _bound = Mod . fromInteger $ natVal (Proxy :: Proxy n) --- | Wraps the underlying type into the modular type, wrapping as--- appropriate.+-- | Injects a value of the underlying type into the modulus type,+-- wrapping as appropriate. toMod :: forall n i. (Integral i, KnownNat n) => i -> i `Mod` n toMod i = Mod $ i `mod` unMod (_bound :: i `Mod` n) --- | Wraps an integral number to a mod, converting between integral--- types.+-- | Wraps an integral number, converting between integral types. toMod' :: forall n i j. (Integral i, Integral j, KnownNat n) => i -> j `Mod` n toMod' i = toMod . fromIntegral $ i `mod` (fromInteger $ natVal (Proxy :: Proxy n)) @@ -106,15 +138,25 @@ instance (Integral i, KnownNat n) => Real (i `Mod` n) where toRational (Mod i) = toInteger i % 1 --- | Integer division uses modular inverse @'inv'@,--- so it is possible to divide only by numbers coprime to @n@--- and the remainder is always @0@.+-- | Integer division uses modular inverse @'inv'@, so it is possible+-- to divide only by numbers coprime to @n@ and the remainder is+-- always @0@. instance (Integral i, KnownNat n) => Integral (i `Mod` n) where toInteger (Mod i) = toInteger i i₁ `quotRem` i₂ = (i₁ * inv i₂, 0) -- | The modular inverse.--- Note that only numbers coprime to @n@ have an inverse modulo @n@.+--+-- >>> inv 3 :: ℤ/7+-- 5+-- >>> 3 * 5 :: ℤ/7+-- 1+--+-- Note that only numbers coprime to @n@ have an inverse modulo @n@:+--+-- >>> inv 6 :: ℤ/15+-- *** Exception: divide by 6 (mod 15), non-coprime to modulus+-- inv :: forall n i. (KnownNat n, Integral i) => Mod i n -> Mod i n inv k = toMod . snd . inv' (fromInteger (natVal (Proxy :: Proxy n))) . unMod $ k where@@ -130,19 +172,20 @@ (q, r) = n `quotRem` x (q', r') = inv' x r --- | This type represents a modular number with unknown bound.+-- | A modular number with an unknown bound. data SomeMod i where SomeMod :: forall i (n :: Nat). KnownNat n => Mod i n -> SomeMod i instance Show i => Show (SomeMod i) where showsPrec p (SomeMod x) = showsPrec p x --- | Convert an integral number @i@ into a @'Mod'@ value given--- modular bound @n@ at type level.+-- | Convert an integral number @i@ into a @'Mod'@ value given modular+-- bound @n@ at type level. modVal :: forall i proxy n. (Integral i, KnownNat n) => i -> proxy n -> Mod i n modVal i _ = toMod i --- | Convert an integral number @i@ into an unknown @'Mod'@ value.+-- | Convert an integral number @i@ into a @'Mod'@ value with an+-- unknown modulus. someModVal :: Integral i => i -> Integer -> Maybe (SomeMod i) someModVal i n = case someNatVal n of
+ test-suite/DocTest.hs view
@@ -0,0 +1,7 @@+module Main (main) where++import System.FilePath.Glob (glob)+import Test.DocTest (doctest)++main :: IO ()+main = glob "src/**/*.hs" >>= doctest