-- | Finitely generated ideals in commutative rings. module Algebra.Ideal ( Ideal(Id) , zeroIdeal, isPrincipal, fromId , eval, addId, mulId , isSameIdeal, zeroIdealWitnesses ) 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. If \[ x_1, ..., x_n \] \`op\` \[ y_1, ..., y_m \] = \[ z_1, ..., z_l \] Then the witness should give that z_k = a_k1 * x_1 + ... + a_kn * x_n = b_k1 * y_1 + ... + b_km * y_m This is used to check that the intersection computed is correct. -} 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])