{-# LANGUAGE DataKinds #-}
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE ExistentialQuantification #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE TypeSynonymInstances #-}
{-# LANGUAGE UndecidableInstances #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}

module Algebra.Ring.Ideal
  ( Ideal (..),
    addToIdeal,
    toIdeal,
    appendIdeal,
    generators,
    filterIdeal,
    mapIdeal,
    principalIdeal,
    isEmptyIdeal,
    someSizedIdeal,
  )
where

import Algebra.Internal ()
import AlgebraicPrelude
import Control.DeepSeq
import qualified Data.Foldable as F
import Data.Sequence ((<|), (><))
import qualified Data.Sequence as Seq
import qualified Data.Sized as S
import qualified Data.Vector as V

newtype Ideal r = Ideal (Seq r)
  deriving
    ( Ideal r -> ()
(Ideal r -> ()) -> NFData (Ideal r)
forall r. NFData r => Ideal r -> ()
forall a. (a -> ()) -> NFData a
rnf :: Ideal r -> ()
$crnf :: forall r. NFData r => Ideal r -> ()
NFData
    , a -> Ideal a -> Bool
Ideal m -> m
Ideal a -> [a]
Ideal a -> Bool
Ideal a -> Int
Ideal a -> a
Ideal a -> a
Ideal a -> a
Ideal a -> a
(a -> m) -> Ideal a -> m
(a -> m) -> Ideal a -> m
(a -> b -> b) -> b -> Ideal a -> b
(a -> b -> b) -> b -> Ideal a -> b
(b -> a -> b) -> b -> Ideal a -> b
(b -> a -> b) -> b -> Ideal a -> b
(a -> a -> a) -> Ideal a -> a
(a -> a -> a) -> Ideal a -> a
(forall m. Monoid m => Ideal m -> m)
-> (forall m a. Monoid m => (a -> m) -> Ideal a -> m)
-> (forall m a. Monoid m => (a -> m) -> Ideal a -> m)
-> (forall a b. (a -> b -> b) -> b -> Ideal a -> b)
-> (forall a b. (a -> b -> b) -> b -> Ideal a -> b)
-> (forall b a. (b -> a -> b) -> b -> Ideal a -> b)
-> (forall b a. (b -> a -> b) -> b -> Ideal a -> b)
-> (forall a. (a -> a -> a) -> Ideal a -> a)
-> (forall a. (a -> a -> a) -> Ideal a -> a)
-> (forall a. Ideal a -> [a])
-> (forall a. Ideal a -> Bool)
-> (forall a. Ideal a -> Int)
-> (forall a. Eq a => a -> Ideal a -> Bool)
-> (forall a. Ord a => Ideal a -> a)
-> (forall a. Ord a => Ideal a -> a)
-> (forall a. Num a => Ideal a -> a)
-> (forall a. Num a => Ideal a -> a)
-> Foldable Ideal
forall a. Eq a => a -> Ideal a -> Bool
forall a. Num a => Ideal a -> a
forall a. Ord a => Ideal a -> a
forall m. Monoid m => Ideal m -> m
forall a. Ideal a -> Bool
forall a. Ideal a -> Int
forall a. Ideal a -> [a]
forall a. (a -> a -> a) -> Ideal a -> a
forall m a. Monoid m => (a -> m) -> Ideal a -> m
forall b a. (b -> a -> b) -> b -> Ideal a -> b
forall a b. (a -> b -> b) -> b -> Ideal a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: Ideal a -> a
$cproduct :: forall a. Num a => Ideal a -> a
sum :: Ideal a -> a
$csum :: forall a. Num a => Ideal a -> a
minimum :: Ideal a -> a
$cminimum :: forall a. Ord a => Ideal a -> a
maximum :: Ideal a -> a
$cmaximum :: forall a. Ord a => Ideal a -> a
elem :: a -> Ideal a -> Bool
$celem :: forall a. Eq a => a -> Ideal a -> Bool
length :: Ideal a -> Int
$clength :: forall a. Ideal a -> Int
null :: Ideal a -> Bool
$cnull :: forall a. Ideal a -> Bool
toList :: Ideal a -> [a]
$ctoList :: forall a. Ideal a -> [a]
foldl1 :: (a -> a -> a) -> Ideal a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Ideal a -> a
foldr1 :: (a -> a -> a) -> Ideal a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> Ideal a -> a
foldl' :: (b -> a -> b) -> b -> Ideal a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Ideal a -> b
foldl :: (b -> a -> b) -> b -> Ideal a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Ideal a -> b
foldr' :: (a -> b -> b) -> b -> Ideal a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Ideal a -> b
foldr :: (a -> b -> b) -> b -> Ideal a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> Ideal a -> b
foldMap' :: (a -> m) -> Ideal a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Ideal a -> m
foldMap :: (a -> m) -> Ideal a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Ideal a -> m
fold :: Ideal m -> m
$cfold :: forall m. Monoid m => Ideal m -> m
Foldable
    , Functor Ideal
Foldable Ideal
Functor Ideal
-> Foldable Ideal
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Ideal a -> f (Ideal b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    Ideal (f a) -> f (Ideal a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Ideal a -> m (Ideal b))
-> (forall (m :: * -> *) a. Monad m => Ideal (m a) -> m (Ideal a))
-> Traversable Ideal
(a -> f b) -> Ideal a -> f (Ideal b)
forall (t :: * -> *).
Functor t
-> Foldable t
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => Ideal (m a) -> m (Ideal a)
forall (f :: * -> *) a. Applicative f => Ideal (f a) -> f (Ideal a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Ideal a -> m (Ideal b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Ideal a -> f (Ideal b)
sequence :: Ideal (m a) -> m (Ideal a)
$csequence :: forall (m :: * -> *) a. Monad m => Ideal (m a) -> m (Ideal a)
mapM :: (a -> m b) -> Ideal a -> m (Ideal b)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Ideal a -> m (Ideal b)
sequenceA :: Ideal (f a) -> f (Ideal a)
$csequenceA :: forall (f :: * -> *) a. Applicative f => Ideal (f a) -> f (Ideal a)
traverse :: (a -> f b) -> Ideal a -> f (Ideal b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Ideal a -> f (Ideal b)
$cp2Traversable :: Foldable Ideal
$cp1Traversable :: Functor Ideal
Traversable
    , a -> Ideal b -> Ideal a
(a -> b) -> Ideal a -> Ideal b
(forall a b. (a -> b) -> Ideal a -> Ideal b)
-> (forall a b. a -> Ideal b -> Ideal a) -> Functor Ideal
forall a b. a -> Ideal b -> Ideal a
forall a b. (a -> b) -> Ideal a -> Ideal b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> Ideal b -> Ideal a
$c<$ :: forall a b. a -> Ideal b -> Ideal a
fmap :: (a -> b) -> Ideal a -> Ideal b
$cfmap :: forall a b. (a -> b) -> Ideal a -> Ideal b
Functor
    )

isEmptyIdeal :: Ideal t -> Bool
isEmptyIdeal :: Ideal t -> Bool
isEmptyIdeal (Ideal Seq t
t) = Seq t -> Bool
forall a. Seq a -> Bool
Seq.null Seq t
t

instance Show r => Show (Ideal r) where
  showsPrec :: Int -> Ideal r -> ShowS
showsPrec Int
d = Int -> [r] -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
d ([r] -> ShowS) -> (Ideal r -> [r]) -> Ideal r -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Ideal r -> [r]
forall a. Ideal a -> [a]
generators

addToIdeal :: (Monoidal r, DecidableZero r) => r -> Ideal r -> Ideal r
addToIdeal :: r -> Ideal r -> Ideal r
addToIdeal r
i (Ideal Seq r
is)
  | r -> Bool
forall r. DecidableZero r => r -> Bool
isZero r
i = Seq r -> Ideal r
forall r. Seq r -> Ideal r
Ideal Seq r
is
  | Bool
otherwise = Seq r -> Ideal r
forall r. Seq r -> Ideal r
Ideal (r
i r -> Seq r -> Seq r
forall a. a -> Seq a -> Seq a
<| Seq r
is)

infixr 9 `addToIdeal`

toIdeal :: (DecidableZero r, Monoidal r) => [r] -> Ideal r
toIdeal :: [r] -> Ideal r
toIdeal = (r -> Ideal r -> Ideal r) -> Ideal r -> [r] -> Ideal r
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr r -> Ideal r -> Ideal r
forall r. (Monoidal r, DecidableZero r) => r -> Ideal r -> Ideal r
addToIdeal (Seq r -> Ideal r
forall r. Seq r -> Ideal r
Ideal Seq r
forall a. Seq a
Seq.empty)

appendIdeal :: Ideal r -> Ideal r -> Ideal r
appendIdeal :: Ideal r -> Ideal r -> Ideal r
appendIdeal (Ideal Seq r
is) (Ideal Seq r
js) = Seq r -> Ideal r
forall r. Seq r -> Ideal r
Ideal (Seq r
is Seq r -> Seq r -> Seq r
forall a. Seq a -> Seq a -> Seq a
>< Seq r
js)

generators :: Ideal r -> [r]
generators :: Ideal r -> [r]
generators (Ideal Seq r
is) = Seq r -> [r]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList Seq r
is

filterIdeal :: (r -> Bool) -> Ideal r -> Ideal r
filterIdeal :: (r -> Bool) -> Ideal r -> Ideal r
filterIdeal r -> Bool
p (Ideal Seq r
i) = Seq r -> Ideal r
forall r. Seq r -> Ideal r
Ideal (Seq r -> Ideal r) -> Seq r -> Ideal r
forall a b. (a -> b) -> a -> b
$ (r -> Bool) -> Seq r -> Seq r
forall a. (a -> Bool) -> Seq a -> Seq a
Seq.filter r -> Bool
p Seq r
i

principalIdeal :: r -> Ideal r
principalIdeal :: r -> Ideal r
principalIdeal = Seq r -> Ideal r
forall r. Seq r -> Ideal r
Ideal (Seq r -> Ideal r) -> (r -> Seq r) -> r -> Ideal r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. r -> Seq r
forall a. a -> Seq a
Seq.singleton

mapIdeal :: (r -> r') -> Ideal r -> Ideal r'
mapIdeal :: (r -> r') -> Ideal r -> Ideal r'
mapIdeal r -> r'
fun (Ideal Seq r
xs) = Seq r' -> Ideal r'
forall r. Seq r -> Ideal r
Ideal (Seq r' -> Ideal r') -> Seq r' -> Ideal r'
forall a b. (a -> b) -> a -> b
$ (r -> r') -> Seq r -> Seq r'
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap r -> r'
fun Seq r
xs
{-# INLINE [1] mapIdeal #-}

someSizedIdeal :: Ideal r -> S.SomeSized Vector r
someSizedIdeal :: Ideal r -> SomeSized Vector r
someSizedIdeal (Ideal Seq r
xs) =
  Vector r -> SomeSized Vector r
forall (f :: * -> *) a.
(Dom f a, CFoldable f) =>
f a -> SomeSized f a
S.toSomeSized (Vector r -> SomeSized Vector r) -> Vector r -> SomeSized Vector r
forall a b. (a -> b) -> a -> b
$ [r] -> Vector r
forall a. [a] -> Vector a
V.fromList ([r] -> Vector r) -> [r] -> Vector r
forall a b. (a -> b) -> a -> b
$ Seq r -> [r]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList Seq r
xs