{- Copyright (C) 2011 Dr. Alistair Ward This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>. -} {- | [@AUTHOR@] Dr. Alistair Ward [@DESCRIPTION@] * Describes a /Quotient Ring/; <https://en.wikipedia.org/wiki/Quotient_ring>. * This is a /ring/ composed from a residue-class resulting from /modular/ division. -} module Factory.Data.QuotientRing( -- * Type-classes QuotientRing(..), -- * Functions quot', rem', -- ** Predicates areCongruentModulo, isDivisibleBy ) where import Factory.Data.Ring((=-=)) import qualified Factory.Data.Ring as Data.Ring -- | Defines a sub-class of 'Data.Ring.Ring', in which division is implemented. class Data.Ring.Ring q => QuotientRing q where quotRem' :: q -> q -> (q, q) -- ^ Divides the first operand by the second, to yield a pair composed from the /quotient/ and the /remainder/. -- | Returns the /quotient/, after division of the two specified 'QuotientRing's. quot' :: QuotientRing q => q -- ^ Numerator. -> q -- ^ Denominator. -> q quot' :: q -> q -> q quot' q numerator = (q, q) -> q forall a b. (a, b) -> a fst ((q, q) -> q) -> (q -> (q, q)) -> q -> q forall b c a. (b -> c) -> (a -> b) -> a -> c . q -> q -> (q, q) forall q. QuotientRing q => q -> q -> (q, q) quotRem' q numerator -- | Returns the /remainder/, after division of the two specified 'QuotientRing's. rem' :: QuotientRing q => q -- ^ Numerator. -> q -- ^ Denominator. -> q rem' :: q -> q -> q rem' q numerator = (q, q) -> q forall a b. (a, b) -> b snd ((q, q) -> q) -> (q -> (q, q)) -> q -> q forall b c a. (b -> c) -> (a -> b) -> a -> c . q -> q -> (q, q) forall q. QuotientRing q => q -> q -> (q, q) quotRem' q numerator {- | * 'True' if the two specified 'QuotientRing's are /congruent/ in /modulo/-arithmetic, where the /modulus/ is a third 'QuotientRing'. * <http://www.usna.edu/Users/math/wdj/book/node74.html>. -} areCongruentModulo :: (Eq q, QuotientRing q) => q -- ^ LHS. -> q -- ^ RHS. -> q -- ^ Modulus. -> Bool areCongruentModulo :: q -> q -> q -> Bool areCongruentModulo q l q r q modulus | q l q -> q -> Bool forall a. Eq a => a -> a -> Bool == q r = Bool True -- Only required for efficiency. | Bool otherwise = (q l q -> q -> q forall r. Ring r => r -> r -> r =-= q r) q -> q -> Bool forall q. (Eq q, QuotientRing q) => q -> q -> Bool `isDivisibleBy` q modulus -- | True if the second operand /divides/ the first. isDivisibleBy :: (Eq q, QuotientRing q) => q -- ^ Numerator. -> q -- ^ Denominator. -> Bool q numerator isDivisibleBy :: q -> q -> Bool `isDivisibleBy` q denominator = q -> q -> q forall q. QuotientRing q => q -> q -> q rem' q numerator q denominator q -> q -> Bool forall a. Eq a => a -> a -> Bool == q forall r. Ring r => r Data.Ring.additiveIdentity