semirings 0.4.2 → 0.5
raw patch · 6 files changed
+217/−35 lines, 6 filesdep ~containers
Dependency ranges changed: containers
Files
- CHANGELOG.md +11/−2
- Data/Euclidean.hs +108/−8
- Data/Field.hs +49/−0
- Data/Semiring.hs +40/−21
- LICENSE +2/−1
- semirings.cabal +7/−3
CHANGELOG.md view
@@ -1,8 +1,17 @@+TBA+---+* Add `Field` typeclass, instances, and functions.+* Add `Euclidean` and `GcdDomain` instances for `()`, `CDouble`, `CFloat`,+ and `Complex`.+* Add `Ring` and `Bits` instances for `WrappedFractional` and `WrappedIntegral`.+* Add `fromInteger` and `fromIntegral` functions for `Ring`.+ 0.4.2: [2019.06.06]------------* Add `Euclidean` typeclass.+-------------------+* Add `GcdDomain` and `Euclidean` typeclasses. * Add `Mod2`, the integers modulo 2, along with its Semiring/Ring/Star instances.+ 0.4.1: [2019.05.04] ------------------- * Remove unlawful and useless `Ring` instance for `GHC.Natural.Natural`.
Data/Euclidean.hs view
@@ -1,3 +1,10 @@+-- |+-- Module: Data.Euclidean+-- Copyright: (c) 2019 Andrew Lelechenko+-- Licence: BSD3+-- Maintainer: Andrew Lelechenko <andrew.lelechenko@gmail.com>+--+ {-# LANGUAGE CPP #-} {-# LANGUAGE DefaultSignatures #-} {-# LANGUAGE GeneralizedNewtypeDeriving #-}@@ -5,20 +12,29 @@ module Data.Euclidean ( Euclidean(..)+ , Field , GcdDomain(..) , WrappedIntegral(..) , WrappedFractional(..) ) where -import Prelude hiding (quotRem, quot, rem, divMod, div, mod, gcd, lcm, (*))+import Prelude hiding (quotRem, quot, rem, divMod, div, mod, gcd, lcm, negate, (*)) import qualified Prelude as P+import Data.Bits+import Data.Complex import Data.Maybe import Data.Ratio import Data.Semiring+import Foreign.C.Types import GHC.Exts import GHC.Integer.GMP.Internals+ import Numeric.Natural +---------------------------------------------------------------------+-- Classes+---------------------------------------------------------------------+ -- | 'GcdDomain' represents a -- <https://en.wikipedia.org/wiki/GCD_domain GCD domain>. -- This is a domain, where GCD can be defined,@@ -128,25 +144,51 @@ coprimeIntegral :: Integral a => a -> a -> Bool coprimeIntegral x y = (odd x || odd y) && P.gcd x y == 1 +-- | A 'Field' represents a+-- <https://en.wikipedia.org/wiki/Field_(mathematics) field>,+-- a ring with a multiplicative inverse for any non-zero element.+class (Euclidean a, Ring a) => Field a++---------------------------------------------------------------------+-- Instances+---------------------------------------------------------------------++instance GcdDomain () where+ divide = const $ const (Just ())+ gcd = const $ const ()+ lcm = const $ const ()+ coprime = const $ const True++instance Euclidean () where+ degree = const 0+ quotRem = const $ const ((), ())+ quot = const $ const ()+ rem = const $ const ()++instance Field ()+ -- | Wrapper around 'Integral' with 'GcdDomain' -- and 'Euclidean' instances. newtype WrappedIntegral a = WrapIntegral { unwrapIntegral :: a }- deriving (Eq, Ord, Show, Num, Integral, Real, Enum)+ deriving (Eq, Ord, Show, Num, Integral, Real, Enum, Bits) instance Num a => Semiring (WrappedIntegral a) where plus = (P.+) zero = 0 times = (P.*) one = 1- fromNatural = fromIntegral+ fromNatural = P.fromIntegral +instance Num a => Ring (WrappedIntegral a) where+ negate = P.negate+ instance Integral a => GcdDomain (WrappedIntegral a) where gcd = P.gcd lcm = P.lcm coprime = coprimeIntegral instance Integral a => Euclidean (WrappedIntegral a) where- degree = fromIntegral . abs . unwrapIntegral+ degree = P.fromIntegral . abs . unwrapIntegral quotRem = P.quotRem quot = P.quot rem = P.rem@@ -161,7 +203,7 @@ coprime = coprimeIntegral instance Euclidean Int where- degree = fromIntegral . abs+ degree = P.fromIntegral . abs quotRem = P.quotRem quot = P.quot rem = P.rem@@ -176,7 +218,7 @@ coprime = coprimeIntegral instance Euclidean Word where- degree = fromIntegral+ degree = P.fromIntegral quotRem = P.quotRem quot = P.quot rem = P.rem@@ -187,7 +229,7 @@ coprime = coprimeIntegral instance Euclidean Integer where- degree = fromInteger . abs+ degree = P.fromInteger . abs quotRem = P.quotRem quot = P.quot rem = P.rem@@ -214,8 +256,11 @@ zero = 0 times = (P.*) one = 1- fromNatural = fromIntegral+ fromNatural = P.fromIntegral +instance Fractional a => Ring (WrappedFractional a) where+ negate = P.negate+ instance (Eq a, Fractional a) => GcdDomain (WrappedFractional a) where divide x y = Just (x / y) gcd = const $ const 1@@ -228,6 +273,8 @@ quot = (/) rem = const $ const 0 +instance (Eq a, Fractional a) => Field (WrappedFractional a)+ instance Integral a => GcdDomain (Ratio a) where divide x y = Just (x / y) gcd = const $ const 1@@ -240,6 +287,8 @@ quot = (/) rem = const $ const 0 +instance Integral a => Field (Ratio a)+ instance GcdDomain Float where divide x y = Just (x / y) gcd = const $ const 1@@ -252,6 +301,8 @@ quot = (/) rem = const $ const 0 +instance Field Float+ instance GcdDomain Double where divide x y = Just (x / y) gcd = const $ const 1@@ -263,3 +314,52 @@ quotRem x y = (x / y, 0) quot = (/) rem = const $ const 0++instance Field Double++instance GcdDomain CFloat where+ divide x y = Just (x / y)+ gcd = const $ const 1+ lcm = const $ const 1+ coprime = const $ const True++instance Euclidean CFloat where+ degree = const 0+ quotRem x y = (x / y, 0)+ quot = (/)+ rem = const $ const 0++instance Field CFloat++instance GcdDomain CDouble where+ divide x y = Just (x / y)+ gcd = const $ const 1+ lcm = const $ const 1+ coprime = const $ const True++instance Euclidean CDouble where+ degree = const 0+ quotRem x y = (x / y, 0)+ quot = (/)+ rem = const $ const 0++instance Field CDouble++conjQuotAbs :: Field a => Complex a -> Complex a+conjQuotAbs (x :+ y) = x `quot` norm :+ (negate y) `quot` norm+ where+ norm = (x `times` x) `plus` (y `times` y)++instance Field a => GcdDomain (Complex a) where+ divide x y = Just (x `times` conjQuotAbs y)+ gcd = const $ const one+ lcm = const $ const one+ coprime = const $ const True++instance Field a => Euclidean (Complex a) where+ degree = const 0+ quotRem x y = (quot x y, zero)+ quot x y = x `times` conjQuotAbs y+ rem = const $ const zero++instance Field a => Field (Complex a)
+ Data/Field.hs view
@@ -0,0 +1,49 @@+-- | A 'Field' is a 'Ring' in which all nonzero elements+-- have a multiplicative inverse.+module Data.Field+ ( -- * Field typeclass+ Field+ , divide+ , fromRational+ , recip+ , (/)+ ) where++import Prelude hiding (fromInteger, fromRational, negate, quot, recip, (/))+import Data.Euclidean (Field, quot)+import Data.Ratio (denominator, numerator)+import Data.Semiring (fromInteger, one)++---------------------------------------------------------------------+-- Functions+---------------------------------------------------------------------++-- | Divide two elements of a 'Field'.+-- For any 'Prelude.Fractional' type, this is the same as '(Prelude./)'.+--+-- @x `divide` y = x `times` 'recip' y@+divide :: Field a => a -> a -> a+divide = quot+{-# INLINE divide #-}++infixl 7 `divide`++-- | Invert an element of a 'Field'.+-- For any 'Prelude.Fractional' type, this is the same as 'Prelude.recip'.+--+-- @'recip' x `times` x = 'one'@+recip :: Field a => a -> a+recip = quot one+{-# INLINE recip #-}++-- | Infix shorthand for 'divide'.+(/) :: Field a => a -> a -> a+(/) = quot+{-# INLINE (/) #-}++infixl 7 /++-- | Convert from rational to field.+fromRational :: Field a => Rational -> a+fromRational x = quot (fromInteger (numerator x)) (fromInteger (denominator x))+{-# INLINE fromRational #-}
Data/Semiring.hs view
@@ -48,11 +48,14 @@ -- * Ring typeclass , Ring(..)- , (-)+ , fromInteger+ , fromIntegral , minus+ , (-) ) where import Control.Applicative (Applicative(..), Const(..), liftA2)+import Data.Bits (Bits) import Data.Bool (Bool(..), (||), (&&), otherwise) #if MIN_VERSION_base(4,7,0) import Data.Coerce (Coercible, coerce)@@ -94,7 +97,7 @@ import qualified Data.Map as Map #endif import Data.Monoid (Monoid(..), Dual(..))-import Data.Ord (Ord((<)))+import Data.Ord (Ord((<)), (>=)) #if MIN_VERSION_base(4,6,0) import Data.Ord (Down(..)) #endif@@ -127,7 +130,8 @@ import GHC.Integer (Integer) import qualified GHC.Num as Num import GHC.Read (Read)-import GHC.Real (Integral, Fractional, Real, RealFrac, fromIntegral)+import GHC.Real (Integral, Fractional, Real, RealFrac)+import qualified GHC.Real as Real import GHC.Show (Show) import Numeric.Natural (Natural) @@ -309,7 +313,7 @@ instance Semiring a => Semigroup (Add a) where Add a <> Add b = Add (a + b)- stimes n (Add a) = Add (fromNatural (fromIntegral n) * a)+ stimes n (Add a) = Add (fromNatural (Real.fromIntegral n) * a) {-# INLINE (<>) #-} instance Semiring a => Monoid (Add a) where@@ -382,6 +386,7 @@ , Storable , Traversable , Typeable+ , Bits ) instance Num.Num a => Semiring (WrappedNum a) where@@ -389,7 +394,7 @@ zero = 0 times = (Num.*) one = 1- fromNatural = fromIntegral+ fromNatural = Real.fromIntegral instance Num.Num a => Ring (WrappedNum a) where negate = Num.negate@@ -499,14 +504,28 @@ minus x y = x + negate y {-# INLINE minus #-} +-- | Convert from integer to ring.+fromInteger :: Ring a => Integer -> a+fromInteger x+ | x >= 0 = fromNatural (Num.fromInteger x)+ | otherwise = negate (fromNatural (Num.fromInteger (Num.negate x)))+{-# INLINE fromInteger #-}++-- | Convert from integral to ring.+fromIntegral :: (Integral a, Ring b) => a -> b+fromIntegral x+ | x >= 0 = fromNatural (Real.fromIntegral x)+ | otherwise = negate (fromNatural (Real.fromIntegral (Num.negate x)))+{-# INLINE fromIntegral #-}+ {-------------------------------------------------------------------- Instances (base) --------------------------------------------------------------------} instance Semiring b => Semiring (a -> b) where- plus f g x = f x `plus` g x+ plus f g = \x -> f x `plus` g x zero = const zero- times f g x = f x `times` g x+ times f g = \x -> f x `times` g x one = const one fromNatural = const . fromNatural {-# INLINE plus #-}@@ -673,18 +692,18 @@ deriving instance Ring a => Ring (Op a b) #endif -#define deriveSemiring(ty) \-instance Semiring (ty) where { \- zero = 0 \-; one = 1 \-; plus x y = (Num.+) x y \-; times x y = (Num.*) x y \-; fromNatural = fromIntegral \-; {-# INLINE zero #-} \-; {-# INLINE one #-} \-; {-# INLINE plus #-} \-; {-# INLINE times #-} \-; {-# INLINE fromNatural #-} \+#define deriveSemiring(ty) \+instance Semiring (ty) where { \+ zero = 0 \+; one = 1 \+; plus x y = (Num.+) x y \+; times x y = (Num.*) x y \+; fromNatural = Real.fromIntegral \+; {-# INLINE zero #-} \+; {-# INLINE one #-} \+; {-# INLINE plus #-} \+; {-# INLINE times #-} \+; {-# INLINE fromNatural #-} \ } deriveSemiring(Int)@@ -753,7 +772,7 @@ one = 1 % 1 plus = (Num.+) times = (Num.*)- fromNatural n = fromIntegral n % 1+ fromNatural n = Real.fromIntegral n % 1 {-# INLINE zero #-} {-# INLINE one #-} {-# INLINE plus #-}@@ -768,7 +787,7 @@ one = 1 plus = (Num.+) times = (Num.*)- fromNatural = fromIntegral+ fromNatural = Real.fromIntegral {-# INLINE zero #-} {-# INLINE one #-} {-# INLINE plus #-}
LICENSE view
@@ -1,4 +1,5 @@-Copyright 2018 chessai+Copyright 2019 chessai+Copyright 2019 Andrew Lelechenko Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
semirings.cabal view
@@ -1,6 +1,6 @@ name: semirings category: Algebra, Data, Data Structures, Math, Maths, Mathematics-version: 0.4.2+version: 0.5 license: BSD3 cabal-version: >= 1.10 license-file: LICENSE@@ -97,7 +97,7 @@ , transformers if impl(ghc < 8.0)- build-depends: semigroups+ build-depends: semigroups >= 0.17 if impl(ghc < 7.8) build-depends: tagged@@ -105,6 +105,7 @@ if impl(ghc >= 7.2) exposed-modules: Data.Euclidean+ Data.Field Data.Semiring Data.Star Data.Semiring.Tropical@@ -115,8 +116,11 @@ if flag(containers) build-depends: containers >= 0.5.4 && < 0.6.1.0 - if flag(hashable)+ if flag(hashable) && impl(ghc < 7.8) build-depends: hashable >= 1.1 && < 1.3++ if flag(hashable) && impl(ghc >= 7.8)+ build-depends: hashable >= 1.1 && < 1.4 if flag(hashable) && flag(unordered-containers) build-depends: unordered-containers >= 0.2 && < 0.3