-- | Free modules over some generator set.  
--
-- This module should be imported qualified.

{-# LANGUAGE 
      BangPatterns, FlexibleContexts, FlexibleInstances, TypeSynonymInstances, TypeFamilies,
      ConstraintKinds, KindSignatures
  #-}
module Math.Algebra.Polynomial.FreeModule where

--------------------------------------------------------------------------------

import Prelude   hiding ( sum , product )
import Data.List hiding ( sum , product )

import Data.Monoid
import Data.Ratio
import Data.Maybe

import Data.Typeable
import Data.Proxy

import Control.Monad ( foldM )

import qualified Data.Map.Strict as Map
import Data.Map.Strict (Map)

import Data.Set (Set)

--------------------------------------------------------------------------------
-- * Partial monoids

class PartialMonoid a where
  pmUnit :: a
  pmAdd  :: a -> a -> Maybe a
  pmSum  :: [a] -> Maybe a

  pmSum [a]
xs  = case [a]
xs of { [] -> a -> Maybe a
forall a. a -> Maybe a
Just a
forall a. PartialMonoid a => a
pmUnit ; (a
y:[a]
ys) -> (a -> a -> Maybe a) -> a -> [a] -> Maybe a
forall (t :: * -> *) (m :: * -> *) b a.
(Foldable t, Monad m) =>
(b -> a -> m b) -> b -> t a -> m b
foldM a -> a -> Maybe a
forall a. PartialMonoid a => a -> a -> Maybe a
pmAdd a
y [a]
ys }
  pmAdd a
x a
y = [a] -> Maybe a
forall a. PartialMonoid a => [a] -> Maybe a
pmSum [a
x,a
y]

{- undecidable instance
instance Monoid a => PartialMonoid a where
  pmUnit    = mempty
  pmAdd x y = Just $ mappend x y
  pmSum xs  = Just $ mconcat xs
-}

--------------------------------------------------------------------------------
-- * A type class

-- | The reason for this type class is to make using newtype wrappers more convenient
class (Ord (BaseF a)) => FreeModule a where
  type BaseF  a :: *
  type CoeffF a :: *
  toFreeModule   :: a -> FreeMod (CoeffF a) (BaseF a)
  fromFreeModule :: FreeMod (CoeffF a) (BaseF a) -> a
  
instance Ord b => FreeModule (FreeMod c b) where
  type BaseF  (FreeMod c b) = b
  type CoeffF (FreeMod c b) = c
  toFreeModule :: FreeMod c b -> FreeMod (CoeffF (FreeMod c b)) (BaseF (FreeMod c b))
toFreeModule   = FreeMod c b -> FreeMod (CoeffF (FreeMod c b)) (BaseF (FreeMod c b))
forall a. a -> a
id
  fromFreeModule :: FreeMod (CoeffF (FreeMod c b)) (BaseF (FreeMod c b)) -> FreeMod c b
fromFreeModule = FreeMod (CoeffF (FreeMod c b)) (BaseF (FreeMod c b)) -> FreeMod c b
forall a. a -> a
id

--------------------------------------------------------------------------------
-- * Free modules

-- | Free module over a coefficient ring with the given base. Internally a map
-- storing the coefficients. We maintain the invariant that the coefficients
-- are never zero.
newtype FreeMod coeff base = FreeMod { FreeMod coeff base -> Map base coeff
unFreeMod :: Map base coeff } deriving (FreeMod coeff base -> FreeMod coeff base -> Bool
(FreeMod coeff base -> FreeMod coeff base -> Bool)
-> (FreeMod coeff base -> FreeMod coeff base -> Bool)
-> Eq (FreeMod coeff base)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall coeff base.
(Eq base, Eq coeff) =>
FreeMod coeff base -> FreeMod coeff base -> Bool
/= :: FreeMod coeff base -> FreeMod coeff base -> Bool
$c/= :: forall coeff base.
(Eq base, Eq coeff) =>
FreeMod coeff base -> FreeMod coeff base -> Bool
== :: FreeMod coeff base -> FreeMod coeff base -> Bool
$c== :: forall coeff base.
(Eq base, Eq coeff) =>
FreeMod coeff base -> FreeMod coeff base -> Bool
Eq,Eq (FreeMod coeff base)
Eq (FreeMod coeff base)
-> (FreeMod coeff base -> FreeMod coeff base -> Ordering)
-> (FreeMod coeff base -> FreeMod coeff base -> Bool)
-> (FreeMod coeff base -> FreeMod coeff base -> Bool)
-> (FreeMod coeff base -> FreeMod coeff base -> Bool)
-> (FreeMod coeff base -> FreeMod coeff base -> Bool)
-> (FreeMod coeff base -> FreeMod coeff base -> FreeMod coeff base)
-> (FreeMod coeff base -> FreeMod coeff base -> FreeMod coeff base)
-> Ord (FreeMod coeff base)
FreeMod coeff base -> FreeMod coeff base -> Bool
FreeMod coeff base -> FreeMod coeff base -> Ordering
FreeMod coeff base -> FreeMod coeff base -> FreeMod coeff base
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall coeff base. (Ord base, Ord coeff) => Eq (FreeMod coeff base)
forall coeff base.
(Ord base, Ord coeff) =>
FreeMod coeff base -> FreeMod coeff base -> Bool
forall coeff base.
(Ord base, Ord coeff) =>
FreeMod coeff base -> FreeMod coeff base -> Ordering
forall coeff base.
(Ord base, Ord coeff) =>
FreeMod coeff base -> FreeMod coeff base -> FreeMod coeff base
min :: FreeMod coeff base -> FreeMod coeff base -> FreeMod coeff base
$cmin :: forall coeff base.
(Ord base, Ord coeff) =>
FreeMod coeff base -> FreeMod coeff base -> FreeMod coeff base
max :: FreeMod coeff base -> FreeMod coeff base -> FreeMod coeff base
$cmax :: forall coeff base.
(Ord base, Ord coeff) =>
FreeMod coeff base -> FreeMod coeff base -> FreeMod coeff base
>= :: FreeMod coeff base -> FreeMod coeff base -> Bool
$c>= :: forall coeff base.
(Ord base, Ord coeff) =>
FreeMod coeff base -> FreeMod coeff base -> Bool
> :: FreeMod coeff base -> FreeMod coeff base -> Bool
$c> :: forall coeff base.
(Ord base, Ord coeff) =>
FreeMod coeff base -> FreeMod coeff base -> Bool
<= :: FreeMod coeff base -> FreeMod coeff base -> Bool
$c<= :: forall coeff base.
(Ord base, Ord coeff) =>
FreeMod coeff base -> FreeMod coeff base -> Bool
< :: FreeMod coeff base -> FreeMod coeff base -> Bool
$c< :: forall coeff base.
(Ord base, Ord coeff) =>
FreeMod coeff base -> FreeMod coeff base -> Bool
compare :: FreeMod coeff base -> FreeMod coeff base -> Ordering
$ccompare :: forall coeff base.
(Ord base, Ord coeff) =>
FreeMod coeff base -> FreeMod coeff base -> Ordering
$cp1Ord :: forall coeff base. (Ord base, Ord coeff) => Eq (FreeMod coeff base)
Ord,Int -> FreeMod coeff base -> ShowS
[FreeMod coeff base] -> ShowS
FreeMod coeff base -> String
(Int -> FreeMod coeff base -> ShowS)
-> (FreeMod coeff base -> String)
-> ([FreeMod coeff base] -> ShowS)
-> Show (FreeMod coeff base)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall coeff base.
(Show base, Show coeff) =>
Int -> FreeMod coeff base -> ShowS
forall coeff base.
(Show base, Show coeff) =>
[FreeMod coeff base] -> ShowS
forall coeff base.
(Show base, Show coeff) =>
FreeMod coeff base -> String
showList :: [FreeMod coeff base] -> ShowS
$cshowList :: forall coeff base.
(Show base, Show coeff) =>
[FreeMod coeff base] -> ShowS
show :: FreeMod coeff base -> String
$cshow :: forall coeff base.
(Show base, Show coeff) =>
FreeMod coeff base -> String
showsPrec :: Int -> FreeMod coeff base -> ShowS
$cshowsPrec :: forall coeff base.
(Show base, Show coeff) =>
Int -> FreeMod coeff base -> ShowS
Show)

-- | Free module with integer coefficients
type ZMod base = FreeMod Integer base

-- | Free module with rational coefficients
type QMod base = FreeMod Rational base

--------------------------------------------------------------------------------
-- * Support

-- | Number of terms
size :: FreeMod c b -> Int
size :: FreeMod c b -> Int
size (FreeMod Map b c
table) = Map b c -> Int
forall k a. Map k a -> Int
Map.size Map b c
table

-- | The support as a list
supportList :: Ord b => FreeMod c b -> [b] 
supportList :: FreeMod c b -> [b]
supportList (FreeMod Map b c
table) = Map b c -> [b]
forall k a. Map k a -> [k]
Map.keys Map b c
table

-- | The support as a set
supportSet :: Ord b => FreeMod c b -> Set b 
supportSet :: FreeMod c b -> Set b
supportSet (FreeMod Map b c
table) = Map b c -> Set b
forall k a. Map k a -> Set k
Map.keysSet Map b c
table

--------------------------------------------------------------------------------

instance (Monoid b, Ord b, Eq c, Num c) => Num (FreeMod c b) where
  + :: FreeMod c b -> FreeMod c b -> FreeMod c b
(+)    = FreeMod c b -> FreeMod c b -> FreeMod c b
forall b c.
(Ord b, Eq c, Num c) =>
FreeMod c b -> FreeMod c b -> FreeMod c b
add
  (-)    = FreeMod c b -> FreeMod c b -> FreeMod c b
forall b c.
(Ord b, Eq c, Num c) =>
FreeMod c b -> FreeMod c b -> FreeMod c b
sub
  negate :: FreeMod c b -> FreeMod c b
negate = FreeMod c b -> FreeMod c b
forall c b. Num c => FreeMod c b -> FreeMod c b
neg
  * :: FreeMod c b -> FreeMod c b -> FreeMod c b
(*)    = FreeMod c b -> FreeMod c b -> FreeMod c b
forall b c.
(Ord b, Monoid b, Eq c, Num c) =>
FreeMod c b -> FreeMod c b -> FreeMod c b
mul
  fromInteger :: Integer -> FreeMod c b
fromInteger = c -> FreeMod c b
forall b c. (Monoid b, Eq c, Num c) => c -> FreeMod c b
konst (c -> FreeMod c b) -> (Integer -> c) -> Integer -> FreeMod c b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> c
forall a. Num a => Integer -> a
fromInteger
  abs :: FreeMod c b -> FreeMod c b
abs      = FreeMod c b -> FreeMod c b
forall a. a -> a
id       -- error "FreeMod/abs"
  signum :: FreeMod c b -> FreeMod c b
signum FreeMod c b
_ = c -> FreeMod c b
forall b c. (Monoid b, Eq c, Num c) => c -> FreeMod c b
konst c
1  -- error "FreeMod/signum"

--------------------------------------------------------------------------------
-- * Sanity checking

-- | Should be the identity function
normalize :: (Ord b, Eq c, Num c) => FreeMod c b -> FreeMod c b
normalize :: FreeMod c b -> FreeMod c b
normalize = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod (Map b c -> FreeMod c b)
-> (FreeMod c b -> Map b c) -> FreeMod c b -> FreeMod c b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (c -> Bool) -> Map b c -> Map b c
forall a k. (a -> Bool) -> Map k a -> Map k a
Map.filter (c -> c -> Bool
forall a. Eq a => a -> a -> Bool
/=c
0) (Map b c -> Map b c)
-> (FreeMod c b -> Map b c) -> FreeMod c b -> Map b c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FreeMod c b -> Map b c
forall coeff base. FreeMod coeff base -> Map base coeff
unFreeMod

-- | Safe equality testing (should be identical to @==@)
safeEq :: (Ord b, Eq b, Eq c, Num c) => FreeMod c b -> FreeMod c b -> Bool
safeEq :: FreeMod c b -> FreeMod c b -> Bool
safeEq FreeMod c b
x FreeMod c b
y = FreeMod c b -> FreeMod c b
forall b c. (Ord b, Eq c, Num c) => FreeMod c b -> FreeMod c b
normalize FreeMod c b
x FreeMod c b -> FreeMod c b -> Bool
forall a. Eq a => a -> a -> Bool
== FreeMod c b -> FreeMod c b
forall b c. (Ord b, Eq c, Num c) => FreeMod c b -> FreeMod c b
normalize FreeMod c b
y

--------------------------------------------------------------------------------
-- * Constructing and deconstructing

-- | The additive unit
zero :: FreeMod c b
zero :: FreeMod c b
zero = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod (Map b c -> FreeMod c b) -> Map b c -> FreeMod c b
forall a b. (a -> b) -> a -> b
$ Map b c
forall k a. Map k a
Map.empty

-- | Testing for equality with zero 
-- (WARNING: this assumes that the invariant of never having zero coefficients actually holds!)
isZero :: Ord b => FreeMod c b -> Bool
isZero :: FreeMod c b -> Bool
isZero (FreeMod Map b c
mp) = Map b c -> Bool
forall k a. Map k a -> Bool
Map.null Map b c
mp

-- | A module generator
generator :: Num c => b -> FreeMod c b 
generator :: b -> FreeMod c b
generator b
x = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod (Map b c -> FreeMod c b) -> Map b c -> FreeMod c b
forall a b. (a -> b) -> a -> b
$ b -> c -> Map b c
forall k a. k -> a -> Map k a
Map.singleton b
x c
1

-- | A single generator with a coefficient
singleton :: (Ord b, Num c, Eq c) => b -> c -> FreeMod c b
singleton :: b -> c -> FreeMod c b
singleton b
b c
c = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod (Map b c -> FreeMod c b) -> Map b c -> FreeMod c b
forall a b. (a -> b) -> a -> b
$ if c
cc -> c -> Bool
forall a. Eq a => a -> a -> Bool
/=c
0
  then b -> c -> Map b c
forall k a. k -> a -> Map k a
Map.singleton b
b c
c
  else Map b c
forall k a. Map k a
Map.empty

-- | Conversion from list. 
-- This should handle repeated generators correctly (adding their coefficients).
fromList :: (Eq c, Num c, Ord b) => [(b,c)] -> FreeMod c b
fromList :: [(b, c)] -> FreeMod c b
fromList = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod (Map b c -> FreeMod c b)
-> ([(b, c)] -> Map b c) -> [(b, c)] -> FreeMod c b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (c -> Bool) -> Map b c -> Map b c
forall a k. (a -> Bool) -> Map k a -> Map k a
Map.filter c -> Bool
forall a. (Eq a, Num a) => a -> Bool
cond (Map b c -> Map b c)
-> ([(b, c)] -> Map b c) -> [(b, c)] -> Map b c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (c -> c -> c) -> [(b, c)] -> Map b c
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Map.fromListWith c -> c -> c
forall a. Num a => a -> a -> a
(+) where
  cond :: a -> Bool
cond a
x = (a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
0)

fromMap :: (Eq c, Num c, Ord b) => Map b c -> FreeMod c b
fromMap :: Map b c -> FreeMod c b
fromMap = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod (Map b c -> FreeMod c b)
-> (Map b c -> Map b c) -> Map b c -> FreeMod c b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (c -> Bool) -> Map b c -> Map b c
forall a k. (a -> Bool) -> Map k a -> Map k a
Map.filter (c -> c -> Bool
forall a. Eq a => a -> a -> Bool
/=c
0) 

-- | Returns the sum of the given generator elements
fromGeneratorSet :: (Ord b, Num c) => Set b -> FreeMod c b
fromGeneratorSet :: Set b -> FreeMod c b
fromGeneratorSet = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod (Map b c -> FreeMod c b)
-> (Set b -> Map b c) -> Set b -> FreeMod c b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (b -> c) -> Set b -> Map b c
forall k a. (k -> a) -> Set k -> Map k a
Map.fromSet (c -> b -> c
forall a b. a -> b -> a
const c
1)

-- | Returns the sum of the given generator elements 
fromGeneratorList :: (Ord b, Eq c, Num c) => [b] -> FreeMod c b
fromGeneratorList :: [b] -> FreeMod c b
fromGeneratorList [b]
bs = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod (Map b c -> FreeMod c b) -> Map b c -> FreeMod c b
forall a b. (a -> b) -> a -> b
$ (Map b c -> b -> Map b c) -> Map b c -> [b] -> Map b c
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' Map b c -> b -> Map b c
forall k a. (Ord k, Num a, Eq a) => Map k a -> k -> Map k a
f Map b c
forall k a. Map k a
Map.empty [b]
bs where
  f :: Map k a -> k -> Map k a
f !Map k a
old !k
b = (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
Map.alter Maybe a -> Maybe a
forall a. (Num a, Eq a) => Maybe a -> Maybe a
g k
b Map k a
old
  g :: Maybe a -> Maybe a
g !Maybe a
mb     = case Maybe a
mb of
    Maybe a
Nothing   -> a -> Maybe a
forall a. a -> Maybe a
Just a
1
    Just a
k    -> let k' :: a
k' = a
ka -> a -> a
forall a. Num a => a -> a -> a
+a
1                                  -- when for example working in a finite field
                 in  if a
k' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
0 then a -> Maybe a
forall a. a -> Maybe a
Just a
k' else Maybe a
forall a. Maybe a
Nothing      -- repeated adding of 1 can result in zero...

-- | Conversion to list 
toList :: FreeMod c b -> [(b,c)]
toList :: FreeMod c b -> [(b, c)]
toList = Map b c -> [(b, c)]
forall k a. Map k a -> [(k, a)]
Map.toList (Map b c -> [(b, c)])
-> (FreeMod c b -> Map b c) -> FreeMod c b -> [(b, c)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FreeMod c b -> Map b c
forall coeff base. FreeMod coeff base -> Map base coeff
unFreeMod

-- | Extract the coefficient of a generator
coeffOf :: (Ord b, Num c) => b -> FreeMod c b -> c
coeffOf :: b -> FreeMod c b -> c
coeffOf b
b (FreeMod Map b c
x) = case b -> Map b c -> Maybe c
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup b
b Map b c
x of
  Just c
c  -> c
c
  Maybe c
Nothing -> c
0

-- | Finds the term with the largest generator (in the natural ordering of the generators)
findMaxTerm :: (Ord b) => FreeMod c b -> Maybe (b,c)
findMaxTerm :: FreeMod c b -> Maybe (b, c)
findMaxTerm (FreeMod Map b c
m) = if Map b c -> Bool
forall k a. Map k a -> Bool
Map.null Map b c
m
  then Maybe (b, c)
forall a. Maybe a
Nothing
  else (b, c) -> Maybe (b, c)
forall a. a -> Maybe a
Just (Map b c -> (b, c)
forall k a. Map k a -> (k, a)
Map.findMax Map b c
m)

-- | Finds the term with the smallest generator (in the natural ordering of the generators)
findMinTerm :: (Ord b) => FreeMod c b -> Maybe (b,c)
findMinTerm :: FreeMod c b -> Maybe (b, c)
findMinTerm (FreeMod Map b c
m) = if Map b c -> Bool
forall k a. Map k a -> Bool
Map.null Map b c
m
  then Maybe (b, c)
forall a. Maybe a
Nothing
  else (b, c) -> Maybe (b, c)
forall a. a -> Maybe a
Just (Map b c -> (b, c)
forall k a. Map k a -> (k, a)
Map.findMin Map b c
m)

--------------------------------------------------------------------------------
-- * Basic operations

-- | Negation
neg :: Num c => FreeMod c b -> FreeMod c b 
neg :: FreeMod c b -> FreeMod c b
neg (FreeMod Map b c
m) = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod ((c -> c) -> Map b c -> Map b c
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map c -> c
forall a. Num a => a -> a
negate Map b c
m)

-- | Additions
add :: (Ord b, Eq c, Num c) => FreeMod c b -> FreeMod c b -> FreeMod c b
add :: FreeMod c b -> FreeMod c b -> FreeMod c b
add (FreeMod Map b c
m1) (FreeMod Map b c
m2) = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod ((b -> c -> c -> Maybe c)
-> (Map b c -> Map b c)
-> (Map b c -> Map b c)
-> Map b c
-> Map b c
-> Map b c
forall k a b c.
Ord k =>
(k -> a -> b -> Maybe c)
-> (Map k a -> Map k c)
-> (Map k b -> Map k c)
-> Map k a
-> Map k b
-> Map k c
Map.mergeWithKey b -> c -> c -> Maybe c
forall a p. (Num a, Eq a) => p -> a -> a -> Maybe a
f Map b c -> Map b c
forall a. a -> a
id Map b c -> Map b c
forall a. a -> a
id Map b c
m1 Map b c
m2) where
  f :: p -> a -> a -> Maybe a
f p
_ a
x a
y = case a
xa -> a -> a
forall a. Num a => a -> a -> a
+a
y of { a
0 -> Maybe a
forall a. Maybe a
Nothing ; a
z -> a -> Maybe a
forall a. a -> Maybe a
Just a
z }

-- | Subtraction
sub :: (Ord b, Eq c, Num c) => FreeMod c b -> FreeMod c b -> FreeMod c b
sub :: FreeMod c b -> FreeMod c b -> FreeMod c b
sub (FreeMod Map b c
m1) (FreeMod Map b c
m2) = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod ((b -> c -> c -> Maybe c)
-> (Map b c -> Map b c)
-> (Map b c -> Map b c)
-> Map b c
-> Map b c
-> Map b c
forall k a b c.
Ord k =>
(k -> a -> b -> Maybe c)
-> (Map k a -> Map k c)
-> (Map k b -> Map k c)
-> Map k a
-> Map k b
-> Map k c
Map.mergeWithKey b -> c -> c -> Maybe c
forall a p. (Num a, Eq a) => p -> a -> a -> Maybe a
f Map b c -> Map b c
forall a. a -> a
id ((c -> c) -> Map b c -> Map b c
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map c -> c
forall a. Num a => a -> a
negate) Map b c
m1 Map b c
m2) where
  f :: p -> a -> a -> Maybe a
f p
_ a
x a
y = case a
xa -> a -> a
forall a. Num a => a -> a -> a
-a
y of { a
0 -> Maybe a
forall a. Maybe a
Nothing ; a
z -> a -> Maybe a
forall a. a -> Maybe a
Just a
z }

-- | Scaling by a number
scale :: (Ord b, Eq c, Num c) => c -> FreeMod c b -> FreeMod c b
scale :: c -> FreeMod c b -> FreeMod c b
scale c
0 FreeMod c b
_           = FreeMod c b
forall c b. FreeMod c b
zero
scale c
x (FreeMod Map b c
m) = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod ((c -> Maybe c) -> Map b c -> Map b c
forall a b k. (a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybe c -> Maybe c
f Map b c
m) where
  f :: c -> Maybe c
f c
y = case c
xc -> c -> c
forall a. Num a => a -> a -> a
*c
y of { c
0 -> Maybe c
forall a. Maybe a
Nothing ; c
z -> c -> Maybe c
forall a. a -> Maybe a
Just c
z }

-- | Dividing by a number (assuming that the coefficient ring is integral, and each coefficient
-- is divisible by the given number)
divideByConst :: (Ord b, Eq c, Integral c, Show c) => c -> FreeMod c b -> FreeMod c b
divideByConst :: c -> FreeMod c b -> FreeMod c b
divideByConst c
d (FreeMod Map b c
m) = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod ((c -> Maybe c) -> Map b c -> Map b c
forall a b k. (a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybe c -> Maybe c
f Map b c
m) where
  f :: c -> Maybe c
f c
a = case c -> c -> (c, c)
forall a. Integral a => a -> a -> (a, a)
divMod c
a c
d of
    (c
b,c
0) -> case c
b of { c
0 -> Maybe c
forall a. Maybe a
Nothing ; c
z -> c -> Maybe c
forall a. a -> Maybe a
Just c
z }
    (c, c)
_     -> String -> Maybe c
forall a. HasCallStack => String -> a
error (String -> Maybe c) -> String -> Maybe c
forall a b. (a -> b) -> a -> b
$ String
"FreeMod/divideByConst: not divisible by " String -> ShowS
forall a. [a] -> [a] -> [a]
++ c -> String
forall a. Show a => a -> String
show c
d

-- | Addition after scaling: @A + c*B@. 
addScale :: (Ord b, Eq c, Num c) => FreeMod c b -> c -> FreeMod c b -> FreeMod c b
addScale :: FreeMod c b -> c -> FreeMod c b -> FreeMod c b
addScale (FreeMod Map b c
m1) c
cf (FreeMod Map b c
m2) = 
  if c
cf c -> c -> Bool
forall a. Eq a => a -> a -> Bool
== c
0 
    then Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod Map b c
m1 
    else Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod ((b -> c -> c -> Maybe c)
-> (Map b c -> Map b c)
-> (Map b c -> Map b c)
-> Map b c
-> Map b c
-> Map b c
forall k a b c.
Ord k =>
(k -> a -> b -> Maybe c)
-> (Map k a -> Map k c)
-> (Map k b -> Map k c)
-> Map k a
-> Map k b
-> Map k c
Map.mergeWithKey b -> c -> c -> Maybe c
f Map b c -> Map b c
forall a. a -> a
id ((c -> Maybe c) -> Map b c -> Map b c
forall a b k. (a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybe c -> Maybe c
g) Map b c
m1 Map b c
m2) 
  where
    g :: c -> Maybe c
g     c
y = case     c
cfc -> c -> c
forall a. Num a => a -> a -> a
*c
y of { c
0 -> Maybe c
forall a. Maybe a
Nothing ; c
z -> c -> Maybe c
forall a. a -> Maybe a
Just c
z }
    f :: b -> c -> c -> Maybe c
f b
_ c
x c
y = case c
x c -> c -> c
forall a. Num a => a -> a -> a
+ c
cfc -> c -> c
forall a. Num a => a -> a -> a
*c
y of { c
0 -> Maybe c
forall a. Maybe a
Nothing ; c
z -> c -> Maybe c
forall a. a -> Maybe a
Just c
z }

-- | Subtraction after scaling: @A - c*B@. This is a handy optimization for conversion algorithms.
subScale :: (Ord b, Eq c, Num c) => FreeMod c b -> c -> FreeMod c b -> FreeMod c b
subScale :: FreeMod c b -> c -> FreeMod c b -> FreeMod c b
subScale (FreeMod Map b c
m1) c
cf (FreeMod Map b c
m2) = 
  if c
cf c -> c -> Bool
forall a. Eq a => a -> a -> Bool
== c
0 
    then Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod Map b c
m1 
    else Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod ((b -> c -> c -> Maybe c)
-> (Map b c -> Map b c)
-> (Map b c -> Map b c)
-> Map b c
-> Map b c
-> Map b c
forall k a b c.
Ord k =>
(k -> a -> b -> Maybe c)
-> (Map k a -> Map k c)
-> (Map k b -> Map k c)
-> Map k a
-> Map k b
-> Map k c
Map.mergeWithKey b -> c -> c -> Maybe c
f Map b c -> Map b c
forall a. a -> a
id ((c -> Maybe c) -> Map b c -> Map b c
forall a b k. (a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybe c -> Maybe c
g) Map b c
m1 Map b c
m2) 
  where
    g :: c -> Maybe c
g     c
y = case   - c
cfc -> c -> c
forall a. Num a => a -> a -> a
*c
y of { c
0 -> Maybe c
forall a. Maybe a
Nothing ; c
z -> c -> Maybe c
forall a. a -> Maybe a
Just c
z }
    f :: b -> c -> c -> Maybe c
f b
_ c
x c
y = case c
x c -> c -> c
forall a. Num a => a -> a -> a
- c
cfc -> c -> c
forall a. Num a => a -> a -> a
*c
y of { c
0 -> Maybe c
forall a. Maybe a
Nothing ; c
z -> c -> Maybe c
forall a. a -> Maybe a
Just c
z }

--------------------------------------------------------------------------------

-- | Summation
sum :: (Ord b, Eq c, Num c) => [FreeMod c b] -> FreeMod c b
sum :: [FreeMod c b] -> FreeMod c b
sum []  = FreeMod c b
forall c b. FreeMod c b
zero
sum [FreeMod c b]
zms = ((FreeMod c b -> FreeMod c b -> FreeMod c b)
-> [FreeMod c b] -> FreeMod c b
forall a. (a -> a -> a) -> [a] -> a
foldl1' FreeMod c b -> FreeMod c b -> FreeMod c b
forall b c.
(Ord b, Eq c, Num c) =>
FreeMod c b -> FreeMod c b -> FreeMod c b
add) [FreeMod c b]
zms

-- | Linear combination
linComb :: (Ord b, Eq c, Num c) => [(c, FreeMod c b)] -> FreeMod c b
linComb :: [(c, FreeMod c b)] -> FreeMod c b
linComb = [(c, FreeMod c b)] -> FreeMod c b
forall b c.
(Ord b, Eq c, Num c) =>
[(c, FreeMod c b)] -> FreeMod c b
sumWith where

   sumWith :: (Ord b, Eq c, Num c) => [(c, FreeMod c b)] -> FreeMod c b
   sumWith :: [(c, FreeMod c b)] -> FreeMod c b
sumWith []  = FreeMod c b
forall c b. FreeMod c b
zero
   sumWith [(c, FreeMod c b)]
zms = [FreeMod c b] -> FreeMod c b
forall b c. (Ord b, Eq c, Num c) => [FreeMod c b] -> FreeMod c b
sum [ c -> FreeMod c b -> FreeMod c b
forall b c. (Ord b, Eq c, Num c) => c -> FreeMod c b -> FreeMod c b
scale c
c FreeMod c b
zm | (c
c,FreeMod c b
zm) <- [(c, FreeMod c b)]
zms ]

-- | Expand each generator into a term in another module and then sum the results
flatMap :: (Ord b1, Ord b2, Eq c, Num c) => (b1 -> FreeMod c b2) -> FreeMod c b1 -> FreeMod c b2
flatMap :: (b1 -> FreeMod c b2) -> FreeMod c b1 -> FreeMod c b2
flatMap b1 -> FreeMod c b2
f = [FreeMod c b2] -> FreeMod c b2
forall b c. (Ord b, Eq c, Num c) => [FreeMod c b] -> FreeMod c b
sum ([FreeMod c b2] -> FreeMod c b2)
-> (FreeMod c b1 -> [FreeMod c b2]) -> FreeMod c b1 -> FreeMod c b2
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((b1, c) -> FreeMod c b2) -> [(b1, c)] -> [FreeMod c b2]
forall a b. (a -> b) -> [a] -> [b]
map (b1, c) -> FreeMod c b2
g ([(b1, c)] -> [FreeMod c b2])
-> (FreeMod c b1 -> [(b1, c)]) -> FreeMod c b1 -> [FreeMod c b2]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map b1 c -> [(b1, c)]
forall k a. Map k a -> [(k, a)]
Map.assocs (Map b1 c -> [(b1, c)])
-> (FreeMod c b1 -> Map b1 c) -> FreeMod c b1 -> [(b1, c)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FreeMod c b1 -> Map b1 c
forall coeff base. FreeMod coeff base -> Map base coeff
unFreeMod where
  g :: (b1, c) -> FreeMod c b2
g (b1
x,c
c) = c -> FreeMod c b2 -> FreeMod c b2
forall b c. (Ord b, Eq c, Num c) => c -> FreeMod c b -> FreeMod c b
scale c
c (b1 -> FreeMod c b2
f b1
x)

flatMap' :: (Ord b1, Ord b2, Eq c2, Num c2) => (c1 -> c2) -> (b1 -> FreeMod c2 b2) -> FreeMod c1 b1 -> FreeMod c2 b2
flatMap' :: (c1 -> c2)
-> (b1 -> FreeMod c2 b2) -> FreeMod c1 b1 -> FreeMod c2 b2
flatMap' c1 -> c2
embed b1 -> FreeMod c2 b2
f = [FreeMod c2 b2] -> FreeMod c2 b2
forall b c. (Ord b, Eq c, Num c) => [FreeMod c b] -> FreeMod c b
sum ([FreeMod c2 b2] -> FreeMod c2 b2)
-> (FreeMod c1 b1 -> [FreeMod c2 b2])
-> FreeMod c1 b1
-> FreeMod c2 b2
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((b1, c1) -> FreeMod c2 b2) -> [(b1, c1)] -> [FreeMod c2 b2]
forall a b. (a -> b) -> [a] -> [b]
map (b1, c1) -> FreeMod c2 b2
g ([(b1, c1)] -> [FreeMod c2 b2])
-> (FreeMod c1 b1 -> [(b1, c1)])
-> FreeMod c1 b1
-> [FreeMod c2 b2]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map b1 c1 -> [(b1, c1)]
forall k a. Map k a -> [(k, a)]
Map.assocs (Map b1 c1 -> [(b1, c1)])
-> (FreeMod c1 b1 -> Map b1 c1) -> FreeMod c1 b1 -> [(b1, c1)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FreeMod c1 b1 -> Map b1 c1
forall coeff base. FreeMod coeff base -> Map base coeff
unFreeMod where
  g :: (b1, c1) -> FreeMod c2 b2
g (b1
x,c1
c) = c2 -> FreeMod c2 b2 -> FreeMod c2 b2
forall b c. (Ord b, Eq c, Num c) => c -> FreeMod c b -> FreeMod c b
scale (c1 -> c2
embed c1
c) (b1 -> FreeMod c2 b2
f b1
x)

-- | The histogram of a multiset of generators is naturally an element of the given Z-module.
{-# SPECIALIZE histogram :: Ord b => [b] -> ZMod b #-} 
histogram :: (Ord b, Num c) => [b] -> FreeMod c b
histogram :: [b] -> FreeMod c b
histogram [b]
xs = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod (Map b c -> FreeMod c b) -> Map b c -> FreeMod c b
forall a b. (a -> b) -> a -> b
$ (Map b c -> b -> Map b c) -> Map b c -> [b] -> Map b c
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' Map b c -> b -> Map b c
forall k a. (Ord k, Num a) => Map k a -> k -> Map k a
f Map b c
forall k a. Map k a
Map.empty [b]
xs where
  f :: Map k a -> k -> Map k a
f Map k a
old k
x = (a -> a -> a) -> k -> a -> Map k a -> Map k a
forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
Map.insertWith a -> a -> a
forall a. Num a => a -> a -> a
(+) k
x a
1 Map k a
old
  
--------------------------------------------------------------------------------
-- * Rings (at least some simple ones, where the basis form a partial monoid)

-- | The multiplicative unit
one :: (Monoid b, Num c) => FreeMod c b
one :: FreeMod c b
one = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod (b -> c -> Map b c
forall k a. k -> a -> Map k a
Map.singleton b
forall a. Monoid a => a
mempty c
1)

-- | A constant
konst :: (Monoid b, Eq c, Num c) => c -> FreeMod c b
konst :: c -> FreeMod c b
konst c
c = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod (Map b c -> FreeMod c b) -> Map b c -> FreeMod c b
forall a b. (a -> b) -> a -> b
$ if c
cc -> c -> Bool
forall a. Eq a => a -> a -> Bool
/=c
0 
  then b -> c -> Map b c
forall k a. k -> a -> Map k a
Map.singleton b
forall a. Monoid a => a
mempty c
c
  else Map b c
forall k a. Map k a
Map.empty

-- | Multiplying two ring elements
mul :: (Ord b, Monoid b, Eq c, Num c) => FreeMod c b -> FreeMod c b -> FreeMod c b
mul :: FreeMod c b -> FreeMod c b -> FreeMod c b
mul = (b -> b -> b) -> FreeMod c b -> FreeMod c b -> FreeMod c b
forall b c.
(Ord b, Eq c, Num c) =>
(b -> b -> b) -> FreeMod c b -> FreeMod c b -> FreeMod c b
mulWith b -> b -> b
forall a. Semigroup a => a -> a -> a
(<>)

-- | Multiplying two ring elements, when the base forms a partial monoid
mul' :: (Ord b, PartialMonoid b, Eq c, Num c) => FreeMod c b -> FreeMod c b -> FreeMod c b
mul' :: FreeMod c b -> FreeMod c b -> FreeMod c b
mul' = (b -> b -> Maybe b) -> FreeMod c b -> FreeMod c b -> FreeMod c b
forall b c.
(Ord b, Eq c, Num c) =>
(b -> b -> Maybe b) -> FreeMod c b -> FreeMod c b -> FreeMod c b
mulWith' (b -> b -> Maybe b
forall a. PartialMonoid a => a -> a -> Maybe a
pmAdd)

-- | Product
product :: (Ord b, Monoid b, Eq c, Num c) => [FreeMod c b] -> FreeMod c b
product :: [FreeMod c b] -> FreeMod c b
product []  = b -> FreeMod c b
forall c b. Num c => b -> FreeMod c b
generator b
forall a. Monoid a => a
mempty
product [FreeMod c b]
xs  = (FreeMod c b -> FreeMod c b -> FreeMod c b)
-> [FreeMod c b] -> FreeMod c b
forall a. (a -> a -> a) -> [a] -> a
foldl1' FreeMod c b -> FreeMod c b -> FreeMod c b
forall b c.
(Ord b, Monoid b, Eq c, Num c) =>
FreeMod c b -> FreeMod c b -> FreeMod c b
mul [FreeMod c b]
xs

-- | Product, when the base forms a partial monoid
product' :: (Ord b, PartialMonoid b, Eq c, Num c) => [FreeMod c b] -> FreeMod c b
product' :: [FreeMod c b] -> FreeMod c b
product' []  = b -> FreeMod c b
forall c b. Num c => b -> FreeMod c b
generator b
forall a. PartialMonoid a => a
pmUnit
product' [FreeMod c b]
xs  = (FreeMod c b -> FreeMod c b -> FreeMod c b)
-> [FreeMod c b] -> FreeMod c b
forall a. (a -> a -> a) -> [a] -> a
foldl1' FreeMod c b -> FreeMod c b -> FreeMod c b
forall b c.
(Ord b, PartialMonoid b, Eq c, Num c) =>
FreeMod c b -> FreeMod c b -> FreeMod c b
mul' [FreeMod c b]
xs

-- | Multiplying two ring elements, using the given monoid operation on base
mulWith :: (Ord b, Eq c, Num c) => (b -> b -> b) -> FreeMod c b -> FreeMod c b -> FreeMod c b
mulWith :: (b -> b -> b) -> FreeMod c b -> FreeMod c b -> FreeMod c b
mulWith b -> b -> b
op FreeMod c b
xx FreeMod c b
yy = FreeMod c b -> FreeMod c b
forall b c. (Ord b, Eq c, Num c) => FreeMod c b -> FreeMod c b
normalize (FreeMod c b -> FreeMod c b) -> FreeMod c b -> FreeMod c b
forall a b. (a -> b) -> a -> b
$ [FreeMod c b] -> FreeMod c b
forall b c. (Ord b, Eq c, Num c) => [FreeMod c b] -> FreeMod c b
sum [ (b -> c -> FreeMod c b
f b
x c
c) | (b
x,c
c) <- FreeMod c b -> [(b, c)]
forall c b. FreeMod c b -> [(b, c)]
toList FreeMod c b
xx ] where
  -- fromListWith can result in zero coefficients... 
  -- and if the sum is one term only, then it won't rmeove them :(
  f :: b -> c -> FreeMod c b
f !b
x !c
c = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod (Map b c -> FreeMod c b) -> Map b c -> FreeMod c b
forall a b. (a -> b) -> a -> b
$ (c -> c -> c) -> [(b, c)] -> Map b c
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Map.fromListWith c -> c -> c
forall a. Num a => a -> a -> a
(+) [ (b -> b -> b
op b
x b
y, c
cd) | (b
y,c
d) <- [(b, c)]
ylist , let cd :: c
cd = c
cc -> c -> c
forall a. Num a => a -> a -> a
*c
d , c
cd c -> c -> Bool
forall a. Eq a => a -> a -> Bool
/= c
0 ]
  ylist :: [(b, c)]
ylist = FreeMod c b -> [(b, c)]
forall c b. FreeMod c b -> [(b, c)]
toList FreeMod c b
yy

-- | Multiplication using a \"truncated\" operation on the base
mulWith' :: (Ord b, Eq c, Num c) => (b -> b -> Maybe b) -> FreeMod c b -> FreeMod c b -> FreeMod c b
mulWith' :: (b -> b -> Maybe b) -> FreeMod c b -> FreeMod c b -> FreeMod c b
mulWith' b -> b -> Maybe b
op FreeMod c b
xx FreeMod c b
yy = FreeMod c b -> FreeMod c b
forall b c. (Ord b, Eq c, Num c) => FreeMod c b -> FreeMod c b
normalize (FreeMod c b -> FreeMod c b) -> FreeMod c b -> FreeMod c b
forall a b. (a -> b) -> a -> b
$ [FreeMod c b] -> FreeMod c b
forall b c. (Ord b, Eq c, Num c) => [FreeMod c b] -> FreeMod c b
sum [ (b -> c -> FreeMod c b
f b
x c
c) | (b
x,c
c) <- FreeMod c b -> [(b, c)]
forall c b. FreeMod c b -> [(b, c)]
toList FreeMod c b
xx ] where
  f :: b -> c -> FreeMod c b
f !b
x !c
c = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod (Map b c -> FreeMod c b) -> Map b c -> FreeMod c b
forall a b. (a -> b) -> a -> b
$ (c -> c -> c) -> [(b, c)] -> Map b c
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Map.fromListWith c -> c -> c
forall a. Num a => a -> a -> a
(+) [ (b
z, c
cd) | (b
y,c
d) <- [(b, c)]
ylist , Just b
z <- [b -> b -> Maybe b
op b
x b
y] , let cd :: c
cd = c
cc -> c -> c
forall a. Num a => a -> a -> a
*c
d , c
cd c -> c -> Bool
forall a. Eq a => a -> a -> Bool
/= c
0 ]
  ylist :: [(b, c)]
ylist = FreeMod c b -> [(b, c)]
forall c b. FreeMod c b -> [(b, c)]
toList FreeMod c b
yy

mulWith'' :: (Ord b, Eq c, Num c) => (b -> b -> Maybe (b,c)) -> FreeMod c b -> FreeMod c b -> FreeMod c b
mulWith'' :: (b -> b -> Maybe (b, c))
-> FreeMod c b -> FreeMod c b -> FreeMod c b
mulWith'' b -> b -> Maybe (b, c)
op FreeMod c b
xx FreeMod c b
yy = FreeMod c b -> FreeMod c b
forall b c. (Ord b, Eq c, Num c) => FreeMod c b -> FreeMod c b
normalize (FreeMod c b -> FreeMod c b) -> FreeMod c b -> FreeMod c b
forall a b. (a -> b) -> a -> b
$ [FreeMod c b] -> FreeMod c b
forall b c. (Ord b, Eq c, Num c) => [FreeMod c b] -> FreeMod c b
sum [ (b -> c -> FreeMod c b
f b
x c
c) | (b
x,c
c) <- FreeMod c b -> [(b, c)]
forall c b. FreeMod c b -> [(b, c)]
toList FreeMod c b
xx ] where
  f :: b -> c -> FreeMod c b
f !b
x !c
c = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod (Map b c -> FreeMod c b) -> Map b c -> FreeMod c b
forall a b. (a -> b) -> a -> b
$ (c -> c -> c) -> [(b, c)] -> Map b c
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Map.fromListWith c -> c -> c
forall a. Num a => a -> a -> a
(+) [ (b
z, c
cde) | (b
y,c
d) <- [(b, c)]
ylist , Just (b
z,c
e) <- [b -> b -> Maybe (b, c)
op b
x b
y] , let cde :: c
cde = c
cc -> c -> c
forall a. Num a => a -> a -> a
*c
dc -> c -> c
forall a. Num a => a -> a -> a
*c
e , c
cde c -> c -> Bool
forall a. Eq a => a -> a -> Bool
/= c
0 ]
  ylist :: [(b, c)]
ylist = FreeMod c b -> [(b, c)]
forall c b. FreeMod c b -> [(b, c)]
toList FreeMod c b
yy

-- | Product, using the given Monoid empty and operation. 
--
-- Implementation note: we only use the user-supported 
-- empty value in case of an empty product.
productWith :: (Ord b, Eq c, Num c) => b -> (b -> b -> b) -> [FreeMod c b] -> FreeMod c b
productWith :: b -> (b -> b -> b) -> [FreeMod c b] -> FreeMod c b
productWith b
empty b -> b -> b
op []  = b -> FreeMod c b
forall c b. Num c => b -> FreeMod c b
generator b
empty
productWith b
empty b -> b -> b
op [FreeMod c b]
xs  = (FreeMod c b -> FreeMod c b -> FreeMod c b)
-> [FreeMod c b] -> FreeMod c b
forall a. (a -> a -> a) -> [a] -> a
foldl1' ((b -> b -> b) -> FreeMod c b -> FreeMod c b -> FreeMod c b
forall b c.
(Ord b, Eq c, Num c) =>
(b -> b -> b) -> FreeMod c b -> FreeMod c b -> FreeMod c b
mulWith b -> b -> b
op) [FreeMod c b]
xs

productWith' :: (Ord b, Eq c, Num c) => b -> (b -> b -> Maybe b) -> [FreeMod c b] -> FreeMod c b
productWith' :: b -> (b -> b -> Maybe b) -> [FreeMod c b] -> FreeMod c b
productWith' b
empty b -> b -> Maybe b
op []  = b -> FreeMod c b
forall c b. Num c => b -> FreeMod c b
generator b
empty
productWith' b
empty b -> b -> Maybe b
op [FreeMod c b]
xs  = (FreeMod c b -> FreeMod c b -> FreeMod c b)
-> [FreeMod c b] -> FreeMod c b
forall a. (a -> a -> a) -> [a] -> a
foldl1' ((b -> b -> Maybe b) -> FreeMod c b -> FreeMod c b -> FreeMod c b
forall b c.
(Ord b, Eq c, Num c) =>
(b -> b -> Maybe b) -> FreeMod c b -> FreeMod c b -> FreeMod c b
mulWith' b -> b -> Maybe b
op) [FreeMod c b]
xs

productWith'' :: (Ord b, Eq c, Num c) => b -> (b -> b -> Maybe (b,c)) -> [FreeMod c b] -> FreeMod c b
productWith'' :: b -> (b -> b -> Maybe (b, c)) -> [FreeMod c b] -> FreeMod c b
productWith'' b
empty b -> b -> Maybe (b, c)
op []  = b -> FreeMod c b
forall c b. Num c => b -> FreeMod c b
generator b
empty
productWith'' b
empty b -> b -> Maybe (b, c)
op [FreeMod c b]
xs  = (FreeMod c b -> FreeMod c b -> FreeMod c b)
-> [FreeMod c b] -> FreeMod c b
forall a. (a -> a -> a) -> [a] -> a
foldl1' ((b -> b -> Maybe (b, c))
-> FreeMod c b -> FreeMod c b -> FreeMod c b
forall b c.
(Ord b, Eq c, Num c) =>
(b -> b -> Maybe (b, c))
-> FreeMod c b -> FreeMod c b -> FreeMod c b
mulWith'' b -> b -> Maybe (b, c)
op) [FreeMod c b]
xs

-- | Multiplies by a monomial
mulByMonom :: (Eq c, Num c, Ord b, Monoid b) => b -> FreeMod c b -> FreeMod c b
mulByMonom :: b -> FreeMod c b -> FreeMod c b
mulByMonom b
monom = (b -> b) -> FreeMod c b -> FreeMod c b
forall a b c.
(Ord a, Ord b, Eq c, Num c) =>
(a -> b) -> FreeMod c a -> FreeMod c b
mapBase (b -> b -> b
forall a. Monoid a => a -> a -> a
mappend b
monom) 

-- | Multiplies by a monomial (NOTE: we assume that this is an injective operation!!!)
unsafeMulByMonom :: (Ord b, Monoid b) => b -> FreeMod c b -> FreeMod c b
unsafeMulByMonom :: b -> FreeMod c b -> FreeMod c b
unsafeMulByMonom b
monom = (b -> b) -> FreeMod c b -> FreeMod c b
forall a b c.
(Ord a, Ord b) =>
(a -> b) -> FreeMod c a -> FreeMod c b
unsafeMapBase (b -> b -> b
forall a. Monoid a => a -> a -> a
mappend b
monom)

-- | Multiplies by a partial monomial 
mulByMonom' :: (Eq c, Num c, Ord b, PartialMonoid b) => b -> FreeMod c b -> FreeMod c b
mulByMonom' :: b -> FreeMod c b -> FreeMod c b
mulByMonom' b
monom = (b -> Maybe b) -> FreeMod c b -> FreeMod c b
forall a b c.
(Ord a, Ord b, Eq c, Num c) =>
(a -> Maybe b) -> FreeMod c a -> FreeMod c b
mapMaybeBase (b -> b -> Maybe b
forall a. PartialMonoid a => a -> a -> Maybe a
pmAdd b
monom) 

unsafeMulByMonom' :: (Ord b, PartialMonoid b) => b -> FreeMod c b -> FreeMod c b
unsafeMulByMonom' :: b -> FreeMod c b -> FreeMod c b
unsafeMulByMonom' b
monom = (b -> Maybe b) -> FreeMod c b -> FreeMod c b
forall a b c.
(Ord a, Ord b) =>
(a -> Maybe b) -> FreeMod c a -> FreeMod c b
unsafeMapMaybeBase (b -> b -> Maybe b
forall a. PartialMonoid a => a -> a -> Maybe a
pmAdd b
monom) 

--------------------------------------------------------------------------------
-- * Integer \/ Rational conversions

freeModCoeffProxy :: FreeMod c b -> Proxy c
freeModCoeffProxy :: FreeMod c b -> Proxy c
freeModCoeffProxy FreeMod c b
_ = Proxy c
forall k (t :: k). Proxy t
Proxy

{-
typeRepZ, typeRepQ :: TypeRep
typeRepZ = typeOf (0 :: Integer ) 
typeRepQ = typeOf (0 :: Rational)
-}

-- | This is an optimized coefficient ring change function. It detects runtime whether the output 
-- coefficient ring is also the integers, and does nothing in that case. 
fromZMod :: (Num c, Typeable c, Eq c, Num c, Ord b, Typeable b) => ZMod b -> FreeMod c b
fromZMod :: ZMod b -> FreeMod c b
fromZMod = (Integer -> c) -> ZMod b -> FreeMod c b
forall c1 c2 b.
(Typeable c1, Typeable c2, Eq c2, Num c2, Ord b, Typeable b) =>
(c1 -> c2) -> FreeMod c1 b -> FreeMod c2 b
unsafeCoeffChange Integer -> c
forall a. Num a => Integer -> a
fromInteger

-- | This is an optimized coefficient ring change function. It detects runtime whether the output 
-- coefficient ring is also the rational, and does nothing in that case. 
fromQMod :: (Fractional c, Typeable c, Eq c, Num c, Ord b, Typeable b) => QMod b -> FreeMod c b
fromQMod :: QMod b -> FreeMod c b
fromQMod = (Rational -> c) -> QMod b -> FreeMod c b
forall c1 c2 b.
(Typeable c1, Typeable c2, Eq c2, Num c2, Ord b, Typeable b) =>
(c1 -> c2) -> FreeMod c1 b -> FreeMod c2 b
unsafeCoeffChange Rational -> c
forall a. Fractional a => Rational -> a
fromRational

-- | This is an optimized coefficient ring change function. It detects runtime whether the output 
-- coefficient ring is the same as the input, and does nothing in that case. 
--
-- For this to be valid, it is required that the supported function is identity in
-- the case @c1 ~ c2@ !!!
unsafeCoeffChange :: (Typeable c1, Typeable c2, Eq c2, Num c2, Ord b, Typeable b) => (c1 -> c2) -> FreeMod c1 b -> FreeMod c2 b
unsafeCoeffChange :: (c1 -> c2) -> FreeMod c1 b -> FreeMod c2 b
unsafeCoeffChange c1 -> c2
f FreeMod c1 b
input = case FreeMod c1 b -> Maybe (FreeMod c2 b)
forall a b. (Typeable a, Typeable b) => a -> Maybe b
cast FreeMod c1 b
input of
  Just FreeMod c2 b
out -> {- trace "*** no cast" $ -} FreeMod c2 b
out
  Maybe (FreeMod c2 b)
Nothing  -> {- trace "!!! cast"    $ -} (c1 -> c2) -> FreeMod c1 b -> FreeMod c2 b
forall b c2 c1.
(Ord b, Eq c2, Num c2) =>
(c1 -> c2) -> FreeMod c1 b -> FreeMod c2 b
mapCoeff c1 -> c2
f FreeMod c1 b
input

-- | Given a polynomial with formally rational coefficients, but whose coeffiecients
-- are actually integers, we return the corresponding polynomial with integer coefficients
unsafeZModFromQMod :: Ord b => QMod b -> ZMod b
unsafeZModFromQMod :: QMod b -> ZMod b
unsafeZModFromQMod = (Rational -> Integer) -> QMod b -> ZMod b
forall b c2 c1.
(Ord b, Eq c2, Num c2) =>
(c1 -> c2) -> FreeMod c1 b -> FreeMod c2 b
mapCoeff Rational -> Integer
f where
  f :: Rational -> Integer
  f :: Rational -> Integer
f Rational
q = if Rational -> Integer
forall a. Ratio a -> a
denominator Rational
q Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 then Rational -> Integer
forall a. Ratio a -> a
numerator Rational
q else String -> Integer
forall a. HasCallStack => String -> a
error String
"unsafeZModFromQMod: coefficient is not integral"

--------------------------------------------------------------------------------
-- * Misc

-- | Changing the base set
mapBase :: (Ord a, Ord b, Eq c, Num c) => (a -> b) -> FreeMod c a -> FreeMod c b
mapBase :: (a -> b) -> FreeMod c a -> FreeMod c b
mapBase a -> b
f 
  = FreeMod c b -> FreeMod c b
forall b c. (Ord b, Eq c, Num c) => FreeMod c b -> FreeMod c b
normalize                            -- it can happen that we merge a (-1) and (+1) for example ...
  (FreeMod c b -> FreeMod c b)
-> (FreeMod c a -> FreeMod c b) -> FreeMod c a -> FreeMod c b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map a c -> Map b c) -> FreeMod c a -> FreeMod c b
forall a b c.
(Ord a, Ord b) =>
(Map a c -> Map b c) -> FreeMod c a -> FreeMod c b
onFreeMod ((c -> c -> c) -> (a -> b) -> Map a c -> Map b c
forall k2 a k1.
Ord k2 =>
(a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeysWith c -> c -> c
forall a. Num a => a -> a -> a
(+) a -> b
f)

-- | Changing the base set (the user must guarantee that the map is injective!!)
unsafeMapBase :: (Ord a, Ord b) => (a -> b) -> FreeMod c a -> FreeMod c b
unsafeMapBase :: (a -> b) -> FreeMod c a -> FreeMod c b
unsafeMapBase a -> b
f = (Map a c -> Map b c) -> FreeMod c a -> FreeMod c b
forall a b c.
(Ord a, Ord b) =>
(Map a c -> Map b c) -> FreeMod c a -> FreeMod c b
onFreeMod ((a -> b) -> Map a c -> Map b c
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeys a -> b
f)

-- | Changing the coefficient ring
mapCoeff :: (Ord b, Eq c2, Num c2) => (c1 -> c2) -> FreeMod c1 b -> FreeMod c2 b
mapCoeff :: (c1 -> c2) -> FreeMod c1 b -> FreeMod c2 b
mapCoeff c1 -> c2
f = (Map b c1 -> Map b c2) -> FreeMod c1 b -> FreeMod c2 b
forall a b c d.
(Ord a, Ord b) =>
(Map a c -> Map b d) -> FreeMod c a -> FreeMod d b
onFreeMod' ((c1 -> Maybe c2) -> Map b c1 -> Map b c2
forall a b k. (a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybe c1 -> Maybe c2
mbf) where
  mbf :: c1 -> Maybe c2
mbf c1
x = case c1 -> c2
f c1
x of { c2
0 -> Maybe c2
forall a. Maybe a
Nothing ; c2
y -> c2 -> Maybe c2
forall a. a -> Maybe a
Just c2
y }

mapCoeffWithKey :: (Ord b, Eq c2, Num c2) => (b -> c1 -> c2) -> FreeMod c1 b -> FreeMod c2 b
mapCoeffWithKey :: (b -> c1 -> c2) -> FreeMod c1 b -> FreeMod c2 b
mapCoeffWithKey b -> c1 -> c2
f = (Map b c1 -> Map b c2) -> FreeMod c1 b -> FreeMod c2 b
forall a b c d.
(Ord a, Ord b) =>
(Map a c -> Map b d) -> FreeMod c a -> FreeMod d b
onFreeMod' ((b -> c1 -> Maybe c2) -> Map b c1 -> Map b c2
forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybeWithKey b -> c1 -> Maybe c2
mbf) where
  mbf :: b -> c1 -> Maybe c2
mbf b
k c1
x = case b -> c1 -> c2
f b
k c1
x of { c2
0 -> Maybe c2
forall a. Maybe a
Nothing ; c2
y -> c2 -> Maybe c2
forall a. a -> Maybe a
Just c2
y }

-- | Extract a subset of terms
filterBase :: (Ord b) => (b -> Bool) -> FreeMod c b -> FreeMod c b
filterBase :: (b -> Bool) -> FreeMod c b -> FreeMod c b
filterBase b -> Bool
f = (Map b c -> Map b c) -> FreeMod c b -> FreeMod c b
forall a b c.
(Ord a, Ord b) =>
(Map a c -> Map b c) -> FreeMod c a -> FreeMod c b
onFreeMod ((b -> c -> Bool) -> Map b c -> Map b c
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
Map.filterWithKey b -> c -> Bool
g) where g :: b -> c -> Bool
g b
k c
_ = b -> Bool
f b
k 

-- | Map and extract a subset of terms 
mapMaybeBase :: (Ord a, Ord b, Eq c, Num c) => (a -> Maybe b) -> FreeMod c a -> FreeMod c b
mapMaybeBase :: (a -> Maybe b) -> FreeMod c a -> FreeMod c b
mapMaybeBase a -> Maybe b
f 
  = FreeMod c b -> FreeMod c b
forall b c. (Ord b, Eq c, Num c) => FreeMod c b -> FreeMod c b
normalize      -- it can happen that we merge a (-1) and (+1) for example ...
  (FreeMod c b -> FreeMod c b)
-> (FreeMod c a -> FreeMod c b) -> FreeMod c a -> FreeMod c b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map a c -> Map b c) -> FreeMod c a -> FreeMod c b
forall a b c.
(Ord a, Ord b) =>
(Map a c -> Map b c) -> FreeMod c a -> FreeMod c b
onFreeMod ((c -> c -> c) -> [(b, c)] -> Map b c
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Map.fromListWith c -> c -> c
forall a. Num a => a -> a -> a
(+) ([(b, c)] -> Map b c)
-> (Map a c -> [(b, c)]) -> Map a c -> Map b c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, c) -> Maybe (b, c)) -> [(a, c)] -> [(b, c)]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe (a, c) -> Maybe (b, c)
g ([(a, c)] -> [(b, c)])
-> (Map a c -> [(a, c)]) -> Map a c -> [(b, c)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map a c -> [(a, c)]
forall k a. Map k a -> [(k, a)]
Map.toList)
  where
    g :: (a, c) -> Maybe (b, c)
g (a
k,c
x) = case a -> Maybe b
f a
k of { Just b
k' -> (b, c) -> Maybe (b, c)
forall a. a -> Maybe a
Just (b
k',c
x) ; Maybe b
Nothing -> Maybe (b, c)
forall a. Maybe a
Nothing }

-- | Like 'mapMaybeBase', but the user must guarantee that the @Just@ part of the map is injective!
unsafeMapMaybeBase :: (Ord a, Ord b) => (a -> Maybe b) -> FreeMod c a -> FreeMod c b
unsafeMapMaybeBase :: (a -> Maybe b) -> FreeMod c a -> FreeMod c b
unsafeMapMaybeBase a -> Maybe b
f = (Map a c -> Map b c) -> FreeMod c a -> FreeMod c b
forall a b c.
(Ord a, Ord b) =>
(Map a c -> Map b c) -> FreeMod c a -> FreeMod c b
onFreeMod ([(b, c)] -> Map b c
forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList ([(b, c)] -> Map b c)
-> (Map a c -> [(b, c)]) -> Map a c -> Map b c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, c) -> Maybe (b, c)) -> [(a, c)] -> [(b, c)]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe (a, c) -> Maybe (b, c)
g ([(a, c)] -> [(b, c)])
-> (Map a c -> [(a, c)]) -> Map a c -> [(b, c)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map a c -> [(a, c)]
forall k a. Map k a -> [(k, a)]
Map.toList)
  where
    g :: (a, c) -> Maybe (b, c)
g (a
k,c
x) = case a -> Maybe b
f a
k of { Just b
k' -> (b, c) -> Maybe (b, c)
forall a. a -> Maybe a
Just (b
k',c
x) ; Maybe b
Nothing -> Maybe (b, c)
forall a. Maybe a
Nothing }

mapMaybeBaseCoeff :: (Ord a, Ord b, Eq c, Num c) => (a -> Maybe (b,c)) -> FreeMod c a -> FreeMod c b
mapMaybeBaseCoeff :: (a -> Maybe (b, c)) -> FreeMod c a -> FreeMod c b
mapMaybeBaseCoeff a -> Maybe (b, c)
f 
  = FreeMod c b -> FreeMod c b
forall b c. (Ord b, Eq c, Num c) => FreeMod c b -> FreeMod c b
normalize      -- it can happen that we merge a (-1) and (+1) for example ...
  (FreeMod c b -> FreeMod c b)
-> (FreeMod c a -> FreeMod c b) -> FreeMod c a -> FreeMod c b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map a c -> Map b c) -> FreeMod c a -> FreeMod c b
forall a b c.
(Ord a, Ord b) =>
(Map a c -> Map b c) -> FreeMod c a -> FreeMod c b
onFreeMod ((c -> c -> c) -> [(b, c)] -> Map b c
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Map.fromListWith c -> c -> c
forall a. Num a => a -> a -> a
(+) ([(b, c)] -> Map b c)
-> (Map a c -> [(b, c)]) -> Map a c -> Map b c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, c) -> Maybe (b, c)) -> [(a, c)] -> [(b, c)]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe (a, c) -> Maybe (b, c)
g ([(a, c)] -> [(b, c)])
-> (Map a c -> [(a, c)]) -> Map a c -> [(b, c)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map a c -> [(a, c)]
forall k a. Map k a -> [(k, a)]
Map.toList)
  where
    g :: (a, c) -> Maybe (b, c)
g (a
k,c
x) = case a -> Maybe (b, c)
f a
k of 
        Just (b
k',c
y) -> let z :: c
z = c
xc -> c -> c
forall a. Num a => a -> a -> a
*c
y in if c
zc -> c -> Bool
forall a. Eq a => a -> a -> Bool
/=c
0 then (b, c) -> Maybe (b, c)
forall a. a -> Maybe a
Just (b
k',c
z) else Maybe (b, c)
forall a. Maybe a
Nothing
        Maybe (b, c)
Nothing     -> Maybe (b, c)
forall a. Maybe a
Nothing 

-- | NOTE: This is UNSAFE! The user must guarantee that the map respects the invariants!
onFreeMod :: (Ord a, Ord b) => (Map a c -> Map b c) -> FreeMod c a -> FreeMod c b
onFreeMod :: (Map a c -> Map b c) -> FreeMod c a -> FreeMod c b
onFreeMod Map a c -> Map b c
f = Map b c -> FreeMod c b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod (Map b c -> FreeMod c b)
-> (FreeMod c a -> Map b c) -> FreeMod c a -> FreeMod c b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map a c -> Map b c
f (Map a c -> Map b c)
-> (FreeMod c a -> Map a c) -> FreeMod c a -> Map b c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FreeMod c a -> Map a c
forall coeff base. FreeMod coeff base -> Map base coeff
unFreeMod

onFreeMod' :: (Ord a, Ord b) => (Map a c -> Map b d) -> FreeMod c a -> FreeMod d b
onFreeMod' :: (Map a c -> Map b d) -> FreeMod c a -> FreeMod d b
onFreeMod' Map a c -> Map b d
f = Map b d -> FreeMod d b
forall coeff base. Map base coeff -> FreeMod coeff base
FreeMod (Map b d -> FreeMod d b)
-> (FreeMod c a -> Map b d) -> FreeMod c a -> FreeMod d b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map a c -> Map b d
f (Map a c -> Map b d)
-> (FreeMod c a -> Map a c) -> FreeMod c a -> Map b d
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FreeMod c a -> Map a c
forall coeff base. FreeMod coeff base -> Map base coeff
unFreeMod

--------------------------------------------------------------------------------