summaryrefslogtreecommitdiff log msg author committer range
path: root/Algebra/Ring/Ideal.hs
blob: 8fd15dec1c33a7f27b083b94a497f5c59c5563dc (plain)
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 {-# LANGUAGE DataKinds, ExistentialQuantification, FlexibleContexts #-} {-# LANGUAGE FlexibleInstances, GADTs, MultiParamTypeClasses #-} {-# LANGUAGE TypeSynonymInstances, UndecidableInstances #-} {-# OPTIONS_GHC -fno-warn-orphans #-} module Algebra.Ring.Ideal ( Ideal(..), addToIdeal, toIdeal, appendIdeal , generators, filterIdeal, mapIdeal, principalIdeal, isEmptyIdeal) where import Algebra.Internal import AlgebraicPrelude import Control.DeepSeq import qualified Data.Foldable as F import qualified Data.Sized.Builtin as S data Ideal r = forall n. Ideal (Sized n r) isEmptyIdeal :: Ideal t -> Bool isEmptyIdeal (Ideal t) = S.null t instance Eq r => Eq (Ideal r) where (==) = (==) `on` generators instance Ord r => Ord (Ideal r) where compare = comparing generators instance Show r => Show (Ideal r) where showsPrec d = showsPrec d . generators addToIdeal :: (Monoidal r, Eq r) => r -> Ideal r -> Ideal r addToIdeal i (Ideal is) | i == zero = Ideal is | otherwise = Ideal (S.cons i is) infixr `addToIdeal` toIdeal :: (Eq r, Monoidal r) => [r] -> Ideal r toIdeal = foldr addToIdeal (Ideal S.empty) appendIdeal :: Ideal r -> Ideal r -> Ideal r appendIdeal (Ideal is) (Ideal js) = Ideal (is `S.append` js) generators :: Ideal r -> [r] generators (Ideal is) = S.toList is filterIdeal :: (Eq r, Monoidal r) => (r -> Bool) -> Ideal r -> Ideal r filterIdeal p (Ideal i) = F.foldr (\h -> if p h then addToIdeal h else id) (toIdeal []) i principalIdeal :: r -> Ideal r principalIdeal = Ideal . singleton mapIdeal :: (r -> r') -> Ideal r -> Ideal r' mapIdeal fun (Ideal xs) = Ideal \$ S.map fun xs {-# INLINE [1] mapIdeal #-} {-# RULES "mapIdeal/id" [~1] forall x. mapIdeal id x = x #-} instance NFData r => NFData (Ideal r) where rnf (Ideal is) = rnf is