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
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))
zeroIdeal :: CommutativeRing a => Ideal a
zeroIdeal = Id [zero]
isPrincipal :: CommutativeRing a => Ideal a -> Bool
isPrincipal (Id xs) = length xs == 1
fromId :: CommutativeRing a => Ideal a -> [a]
fromId (Id xs) = xs
eval :: CommutativeRing a => a -> Ideal a -> a
eval x (Id xs) = foldr (<+>) zero (map (<*> x) xs)
addId :: (CommutativeRing a, Eq a) => Ideal a -> Ideal a -> Ideal a
addId (Id xs) (Id ys) = Id (nub (xs ++ ys))
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 ]
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 ]
zeroIdealWitnesses :: (CommutativeRing a) => [a] -> [a] -> (Ideal a, [[a]], [[a]])
zeroIdealWitnesses xs ys = ( zeroIdeal
, [replicate (length xs) zero]
, [replicate (length ys) zero])