constructive-algebra 0.0.0 → 0.1

raw patch · 7 files changed

+238/−4 lines, 7 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• constructive-algebra.cabal +11/−4
• src/Algebra/Ideal.hs +82/−0
• src/Algebra/Structures/CommutativeRing.hs +26/−0
• src/Algebra/Structures/Field.hs +38/−0
• src/Algebra/Structures/IntegralDomain.hs +28/−0
• src/Algebra/Structures/StronglyDiscrete.hs +26/−0
• src/Algebra/Z.hs +27/−0

@@ -7,10 +7,10 @@ -- The package version. See the Haskell package versioning policy -- (http://www.haskell.org/haskellwiki/Package_versioning_policy) for -- standards guiding when and how versions should be incremented.-Version:             0.0.0+Version:             0.1 -Synopsis:            A library for constructive algebra.-Description:         A library for constructive algebra.+Synopsis:            A library of constructive algebra.+Description:         A library of constructive algebra.  License:             BSD3 License-file:        LICENSE@@ -39,7 +39,14 @@  Library   -- Modules exported by the library.-  Exposed-modules:     Algebra.Structures.Ring+  Exposed-modules:     Algebra.Structures.Ring, +                       Algebra.Structures.CommutativeRing,+                       Algebra.Structures.IntegralDomain, +                       Algebra.Structures.Field,+                       Algebra.Structures.StronglyDiscrete,+                       Algebra.Ideal,+                       Algebra.Z+      -- Packages needed in order to build this package.   Build-depends:       base >= 3 && <= 4, QuickCheck >= 2 

@@ -0,0 +1,82 @@+-- | Finitely generated ideals in commutative rings.+module Algebra.Ideal+  ( Ideal(Id)+  , zeroIdeal, isPrincipal, eval, addId, mulId +  ) where++import Data.List (intersperse,nub)+import Test.QuickCheck++import Algebra.Structures.CommutativeRing+++-------------------------------------------------------------------------------+-- | Ideals characterized by their list of generators.++data CommutativeRing a => Ideal a = Id [a]++instance (CommutativeRing a, Show a) => Show (Ideal a) where+  show (Id xs) = "<" ++ concat (intersperse "," (map show xs)) ++ ">"++instance (CommutativeRing a, Arbitrary a, Eq a) => Arbitrary (Ideal a) where+  arbitrary = do xs' <- arbitrary+                 let xs = filter (/= zero) xs'+                 if xs == [] then return (Id [one]) else return (Id (nub xs))++-- | The zero ideal.+zeroIdeal :: CommutativeRing a => Ideal a+zeroIdeal = Id [zero]++-- | Test if an ideal is principal.+isPrincipal :: CommutativeRing a => Ideal a -> Bool+isPrincipal (Id xs) = length xs == 1++fromId :: CommutativeRing a => Ideal a -> [a]+fromId (Id xs) = xs++-- | Evaluate the ideal at a certain point.+eval :: CommutativeRing a => a -> Ideal a -> a+eval x (Id xs) = foldr (<+>) zero (map (<*> x) xs)++-- | Addition of ideals.+addId :: (CommutativeRing a, Eq a) => Ideal a -> Ideal a -> Ideal a+addId (Id xs) (Id ys) = Id (nub (xs ++ ys))++-- |  Multiplication of ideals.+mulId :: (CommutativeRing a, Eq a) => Ideal a -> Ideal a -> Ideal a+mulId (Id xs) (Id ys) = if zs == [] then zeroIdeal else Id zs+  where zs = nub [ f <*> g | f <- xs, g <- ys, f <*> g /= zero ]++{-| Test if an operations compute the correct ideal. +The operation should give a witness that the comuted ideal contains+the same elements.++I `op` J = K+[ x_1, ..., x_n ] `op` [ y_1, ..., y_m ] = [ z_1, ..., z_l ]++z_k = a_k1 * x_1 + ... + a_kn * x_n+    = b_k1 * y_1 + ... + b_km * y_m++-}+isSameIdeal :: (CommutativeRing a, Eq a) +            => (Ideal a -> Ideal a -> (Ideal a, [[a]], [[a]]))+            -> Ideal a +            -> Ideal a +            -> Bool+isSameIdeal op (Id xs) (Id ys) = +  let (Id zs, as, bs) = (Id xs) `op` (Id ys)+  in length as == length zs && length bs == length zs+     &&+     and [ z_k == sumRing (zipWith (<*>) a_k xs) && length a_k == length xs+         | (z_k,a_k) <- zip zs as ]+     &&+     and [ z_k == sumRing (zipWith (<*>) b_k ys) && length b_k == length ys+         | (z_k,b_k) <- zip zs bs ]+++-- | Compute witnesses for two lists for the zero ideal. This is used when +-- computing the intersection of two ideals.+zeroIdealWitnesses :: (CommutativeRing a) => [a] -> [a] -> (Ideal a, [[a]], [[a]])+zeroIdealWitnesses xs ys = ( zeroIdeal+                           , [replicate (length xs) zero]+                           , [replicate (length ys) zero])

@@ -0,0 +1,26 @@+module Algebra.Structures.CommutativeRing+  ( module Algebra.Structures.Ring+  , CommutativeRing(..)+  , propCommutativeRing+  ) where++import Test.QuickCheck++import Algebra.Structures.Ring+++-------------------------------------------------------------------------------+-- | Definition of commutative rings++class Ring a => CommutativeRing a++propMulComm :: (CommutativeRing a, Eq a) => a -> a -> Bool+propMulComm a b = a <*> b == b <*> a+++-- | Specification of commutative rings. Test that multiplication is +-- commutative and that it satisfies the ring axioms.+propCommutativeRing :: (CommutativeRing a, Eq a) => a -> a -> a -> Property+propCommutativeRing a b c = if propMulComm a b +                               then propRing a b c +                               else whenFail (print "propMulComm") False

@@ -0,0 +1,38 @@+module Algebra.Structures.Field+  ( module Algebra.Structures.IntegralDomain+  , Field(inv)+  , propField+  , (</>)+  ) where++import Test.QuickCheck++import Algebra.Structures.Ring+import Algebra.Structures.IntegralDomain+++infixl 7 </>++-------------------------------------------------------------------------------+-- | Definition of fields++class IntegralDomain a => Field a where+  inv :: a -> a++propMulInv :: (Field a, Eq a) => a -> Bool+propMulInv a = a == zero || inv a <*> a == one++-- | Specification of fields. Test that the multiplicative inverses behave as +-- expected and that it satisfies the axioms of integral domains.+propField :: (Field a, Eq a) => a -> a -> a -> Property+propField a b c = if propMulInv a+                     then propIntegralDomain a b c +                     else whenFail (print "propMulInv") False++-------------------------------------------------------------------------------+-- Operations+++-- | Division+(</>) :: Field a => a -> a -> a+x </> y = x <*> inv y

@@ -0,0 +1,28 @@+module Algebra.Structures.IntegralDomain+  ( module Algebra.Structures.CommutativeRing+  , IntegralDomain+  , propIntegralDomain+  ) where++import Test.QuickCheck++import Algebra.Structures.Ring+import Algebra.Structures.CommutativeRing+++-------------------------------------------------------------------------------+-- | Definition of integral domains++class CommutativeRing a => IntegralDomain a++-- An integral domain is a ring in which there are no zero divisors.+propZeroDivisors :: (IntegralDomain a, Eq a) => a -> a -> Bool+propZeroDivisors a b = if a <*> b == zero then a == zero || b == zero else True+++-- | Specification of commutative rings. Test that there are no zero-divisors+-- commutative and that it satisfies the axioms of commutative rings.+propIntegralDomain :: (IntegralDomain a, Eq a) => a -> a -> a -> Property+propIntegralDomain a b c = if propZeroDivisors a b+                              then propCommutativeRing a b c +                              else whenFail (print "propZeroDivisors") False

@@ -0,0 +1,26 @@+module Algebra.Structures.StronglyDiscrete +  ( StronglyDiscrete(member)+  , propStronglyDiscrete+  ) where++import Algebra.Structures.CommutativeRing+import Algebra.Ideal+++-------------------------------------------------------------------------------+-- | Strongly discrete rings+--+-- A ring is called strongly discrete if ideal membership is decidable.+-- Nothing correspond to that x is not in the ideal and Just is the witness.+-- Examples include all euclidean domains and the polynomial ring.+--+class Ring a => StronglyDiscrete a where+  member :: a -> Ideal a -> Maybe [a]++-- | Test that the witness is actually a witness that the element is in the +-- ideal.+propStronglyDiscrete :: (CommutativeRing a, StronglyDiscrete a, Eq a)+                     => a -> Ideal a -> Bool                  +propStronglyDiscrete x id@(Id xs) = case member x id of+  Just as -> x == sumRing (zipWith (<*>) xs as) && length xs == length as+  Nothing -> True

@@ -0,0 +1,27 @@+{-# LANGUAGE TypeSynonymInstances #-}+module Algebra.Z +  ( Z+  , module Algebra.Structures.IntegralDomain+  ) where++import Test.QuickCheck++import Algebra.Structures.IntegralDomain+++-- | Type synonym for integers.+type Z = Integer++instance Ring Z where+  (<*>) = (*)+  (<+>) = (+)+  neg   = negate+  one   = 1+  zero  = 0++instance CommutativeRing Z++instance IntegralDomain Z++propIntegralDomainZ :: Z -> Z -> Z -> Property+propIntegralDomainZ = propIntegralDomain