{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeSynonymInstances #-}
{-# OPTIONS_GHC -Wall -fno-warn-orphans #-}
{-# OPTIONS_HADDOCK show-extensions #-}
-----------------------------------------------------------------------------
-- |
-- Module      :  ToySolver.Data.Polynomial.Factorization.FiniteField
-- Copyright   :  (c) Masahiro Sakai 2012-2013
-- License     :  BSD-style
--
-- Maintainer  :  masahiro.sakai@gmail.com
-- Stability   :  provisional
-- Portability :  non-portable
--
-- Factoriation of polynomial over a finite field.
--
-- References:
--
-- * <http://en.wikipedia.org/wiki/Factorization_of_polynomials_over_a_finite_field_and_irreducibility_tests>
--
-- * <http://en.wikipedia.org/wiki/Berlekamp%27s_algorithm>
--
-- * Martin Kreuzer and Lorenzo Robbiano. Computational Commutative Algebra 1. Springer Verlag, 2000.
--
-----------------------------------------------------------------------------
module ToySolver.Data.Polynomial.Factorization.FiniteField
  ( factor
  , sqfree
  , berlekamp
  , basisOfBerlekampSubalgebra
  ) where

import Control.Exception (assert)
import Data.FiniteField
import Data.List
import Data.Ord
import Data.Set (Set)
import qualified Data.Set as Set
import GHC.TypeLits

import ToySolver.Data.Polynomial.Base (Polynomial, UPolynomial, X (..))
import qualified ToySolver.Data.Polynomial.Base as P
import qualified ToySolver.Data.Polynomial.GroebnerBasis as GB

instance KnownNat p => P.Factor (UPolynomial (PrimeField p)) where
  factor :: UPolynomial (PrimeField p)
-> [(UPolynomial (PrimeField p), Integer)]
factor = UPolynomial (PrimeField p)
-> [(UPolynomial (PrimeField p), Integer)]
forall k.
(Ord k, FiniteField k) =>
UPolynomial k -> [(UPolynomial k, Integer)]
factor

instance KnownNat p => P.SQFree (UPolynomial (PrimeField p)) where
  sqfree :: UPolynomial (PrimeField p)
-> [(UPolynomial (PrimeField p), Integer)]
sqfree = UPolynomial (PrimeField p)
-> [(UPolynomial (PrimeField p), Integer)]
forall k.
(Eq k, FiniteField k) =>
UPolynomial k -> [(UPolynomial k, Integer)]
sqfree

factor :: forall k. (Ord k, FiniteField k) => UPolynomial k -> [(UPolynomial k, Integer)]
factor :: forall k.
(Ord k, FiniteField k) =>
UPolynomial k -> [(UPolynomial k, Integer)]
factor UPolynomial k
f = do
  (UPolynomial k
g,Integer
n) <- UPolynomial k -> [(UPolynomial k, Integer)]
forall k.
(Eq k, FiniteField k) =>
UPolynomial k -> [(UPolynomial k, Integer)]
sqfree UPolynomial k
f
  if UPolynomial k -> Integer
forall t. Degree t => t -> Integer
P.deg UPolynomial k
g Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
0
    then do
      UPolynomial k
h <- UPolynomial k -> [UPolynomial k]
forall k.
(Eq k, Ord k, FiniteField k) =>
UPolynomial k -> [UPolynomial k]
berlekamp UPolynomial k
g
      (UPolynomial k, Integer) -> [(UPolynomial k, Integer)]
forall a. a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return (UPolynomial k
h,Integer
n)
    else do
      (UPolynomial k, Integer) -> [(UPolynomial k, Integer)]
forall a. a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return (UPolynomial k
g,Integer
n)

-- | Square-free decomposition of univariate polynomials over a finite field.
sqfree :: forall k. (Eq k, FiniteField k) => UPolynomial k -> [(UPolynomial k, Integer)]
sqfree :: forall k.
(Eq k, FiniteField k) =>
UPolynomial k -> [(UPolynomial k, Integer)]
sqfree UPolynomial k
f
  | k
c k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
1    = UPolynomial k -> [(UPolynomial k, Integer)]
forall k.
(Eq k, FiniteField k) =>
UPolynomial k -> [(UPolynomial k, Integer)]
sqfree' UPolynomial k
f
  | Bool
otherwise = (k -> UPolynomial k
forall k v. (Eq k, Num k) => k -> Polynomial k v
P.constant k
c, Integer
1) (UPolynomial k, Integer)
-> [(UPolynomial k, Integer)] -> [(UPolynomial k, Integer)]
forall a. a -> [a] -> [a]
: UPolynomial k -> [(UPolynomial k, Integer)]
forall k.
(Eq k, FiniteField k) =>
UPolynomial k -> [(UPolynomial k, Integer)]
sqfree' ((k -> k) -> UPolynomial k -> UPolynomial k
forall k1 k v.
(Eq k1, Num k1) =>
(k -> k1) -> Polynomial k v -> Polynomial k1 v
P.mapCoeff (k -> k -> k
forall a. Fractional a => a -> a -> a
/k
c) UPolynomial k
f)
  where
    c :: k
c = MonomialOrder X -> UPolynomial k -> k
forall k v. Num k => MonomialOrder v -> Polynomial k v -> k
P.lc MonomialOrder X
P.nat UPolynomial k
f

sqfree' :: forall k. (Eq k, FiniteField k) => UPolynomial k -> [(UPolynomial k, Integer)]
sqfree' :: forall k.
(Eq k, FiniteField k) =>
UPolynomial k -> [(UPolynomial k, Integer)]
sqfree' UPolynomial k
0 = []
sqfree' UPolynomial k
f
  | UPolynomial k
g UPolynomial k -> UPolynomial k -> Bool
forall a. Eq a => a -> a -> Bool
== UPolynomial k
0    = [(UPolynomial k
h, Integer
nInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
p) | (UPolynomial k
h,Integer
n) <- UPolynomial k -> [(UPolynomial k, Integer)]
forall k.
(Eq k, FiniteField k) =>
UPolynomial k -> [(UPolynomial k, Integer)]
sqfree' (UPolynomial k -> UPolynomial k
forall k. (Eq k, FiniteField k) => UPolynomial k -> UPolynomial k
polyPthRoot UPolynomial k
f)]
  | Bool
otherwise = Integer
-> UPolynomial k
-> UPolynomial k
-> [(UPolynomial k, Integer)]
-> [(UPolynomial k, Integer)]
forall {k}.
(FiniteField k, Eq k) =>
Integer
-> UPolynomial k
-> UPolynomial k
-> [(UPolynomial k, Integer)]
-> [(UPolynomial k, Integer)]
go Integer
1 UPolynomial k
c0 UPolynomial k
w0 []
  where
    p :: Integer
p = k -> Integer
forall k. FiniteField k => k -> Integer
char (k
forall a. HasCallStack => a
undefined :: k)
    g :: UPolynomial k
g = UPolynomial k -> X -> UPolynomial k
forall k v.
(Eq k, Num k, Ord v) =>
Polynomial k v -> v -> Polynomial k v
P.deriv UPolynomial k
f X
X
    c0 :: UPolynomial k
c0 = UPolynomial k -> UPolynomial k -> UPolynomial k
forall k.
(Eq k, Fractional k) =>
UPolynomial k -> UPolynomial k -> UPolynomial k
P.gcd UPolynomial k
f UPolynomial k
g
    w0 :: UPolynomial k
w0 = UPolynomial k -> UPolynomial k -> UPolynomial k
forall k.
(Eq k, Fractional k) =>
UPolynomial k -> UPolynomial k -> UPolynomial k
P.div UPolynomial k
f UPolynomial k
c0
    go :: Integer
-> UPolynomial k
-> UPolynomial k
-> [(UPolynomial k, Integer)]
-> [(UPolynomial k, Integer)]
go !Integer
i UPolynomial k
c UPolynomial k
w ![(UPolynomial k, Integer)]
result
      | UPolynomial k
w UPolynomial k -> UPolynomial k -> Bool
forall a. Eq a => a -> a -> Bool
== UPolynomial k
1    =
          if UPolynomial k
c UPolynomial k -> UPolynomial k -> Bool
forall a. Eq a => a -> a -> Bool
== UPolynomial k
1
          then [(UPolynomial k, Integer)]
result
          else [(UPolynomial k, Integer)]
result [(UPolynomial k, Integer)]
-> [(UPolynomial k, Integer)] -> [(UPolynomial k, Integer)]
forall a. [a] -> [a] -> [a]
++ [(UPolynomial k
h, Integer
nInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
p) | (UPolynomial k
h,Integer
n) <- UPolynomial k -> [(UPolynomial k, Integer)]
forall k.
(Eq k, FiniteField k) =>
UPolynomial k -> [(UPolynomial k, Integer)]
sqfree' (UPolynomial k -> UPolynomial k
forall k. (Eq k, FiniteField k) => UPolynomial k -> UPolynomial k
polyPthRoot UPolynomial k
c)]
      | Bool
otherwise = Integer
-> UPolynomial k
-> UPolynomial k
-> [(UPolynomial k, Integer)]
-> [(UPolynomial k, Integer)]
go (Integer
iInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
+Integer
1) UPolynomial k
c' UPolynomial k
w' [(UPolynomial k, Integer)]
result'
          where
            y :: UPolynomial k
y  = UPolynomial k -> UPolynomial k -> UPolynomial k
forall k.
(Eq k, Fractional k) =>
UPolynomial k -> UPolynomial k -> UPolynomial k
P.gcd UPolynomial k
w UPolynomial k
c
            z :: UPolynomial k
z  = UPolynomial k
w UPolynomial k -> UPolynomial k -> UPolynomial k
forall k.
(Eq k, Fractional k) =>
UPolynomial k -> UPolynomial k -> UPolynomial k
`P.div` UPolynomial k
y
            c' :: UPolynomial k
c' = UPolynomial k
c UPolynomial k -> UPolynomial k -> UPolynomial k
forall k.
(Eq k, Fractional k) =>
UPolynomial k -> UPolynomial k -> UPolynomial k
`P.div` UPolynomial k
y
            w' :: UPolynomial k
w' = UPolynomial k
y
            result' :: [(UPolynomial k, Integer)]
result' = [(UPolynomial k
z,Integer
i) | UPolynomial k
z UPolynomial k -> UPolynomial k -> Bool
forall a. Eq a => a -> a -> Bool
/= UPolynomial k
1] [(UPolynomial k, Integer)]
-> [(UPolynomial k, Integer)] -> [(UPolynomial k, Integer)]
forall a. [a] -> [a] -> [a]
++ [(UPolynomial k, Integer)]
result

polyPthRoot :: forall k. (Eq k, FiniteField k) => UPolynomial k -> UPolynomial k
polyPthRoot :: forall k. (Eq k, FiniteField k) => UPolynomial k -> UPolynomial k
polyPthRoot Polynomial k X
f = Bool -> Polynomial k X -> Polynomial k X
forall a. HasCallStack => Bool -> a -> a
assert (Polynomial k X -> X -> Polynomial k X
forall k v.
(Eq k, Num k, Ord v) =>
Polynomial k v -> v -> Polynomial k v
P.deriv Polynomial k X
f X
X Polynomial k X -> Polynomial k X -> Bool
forall a. Eq a => a -> a -> Bool
== Polynomial k X
0) (Polynomial k X -> Polynomial k X)
-> Polynomial k X -> Polynomial k X
forall a b. (a -> b) -> a -> b
$
  [Term k X] -> Polynomial k X
forall k v. (Eq k, Num k, Ord v) => [Term k v] -> Polynomial k v
P.fromTerms [(k -> k
forall k. FiniteField k => k -> k
pthRoot k
c, Monomial X -> Monomial X
forall {t}. Degree t => t -> Monomial X
g Monomial X
mm) | (k
c,Monomial X
mm) <- Polynomial k X -> [Term k X]
forall k v. Polynomial k v -> [Term k v]
P.terms Polynomial k X
f]
  where
    p :: Integer
p = k -> Integer
forall k. FiniteField k => k -> Integer
char (k
forall a. HasCallStack => a
undefined :: k)
    g :: t -> Monomial X
g t
mm = X -> Monomial X
forall a v. Var a v => v -> a
P.var X
X Monomial X -> Integer -> Monomial X
forall v. Ord v => Monomial v -> Integer -> Monomial v
`P.mpow` (t -> Integer
forall t. Degree t => t -> Integer
P.deg t
mm Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`div` Integer
p)

-- | Berlekamp algorithm for polynomial factorization.
--
-- Input polynomial is assumed to be monic and square-free.
berlekamp :: forall k. (Eq k, Ord k, FiniteField k) => UPolynomial k -> [UPolynomial k]
berlekamp :: forall k.
(Eq k, Ord k, FiniteField k) =>
UPolynomial k -> [UPolynomial k]
berlekamp UPolynomial k
f = Set (UPolynomial k) -> [UPolynomial k] -> [UPolynomial k]
go (UPolynomial k -> Set (UPolynomial k)
forall a. a -> Set a
Set.singleton UPolynomial k
f) [UPolynomial k]
basis
  where
    go :: Set (UPolynomial k) -> [UPolynomial k] -> [UPolynomial k]
    go :: Set (UPolynomial k) -> [UPolynomial k] -> [UPolynomial k]
go Set (UPolynomial k)
_ [] = [Char] -> [UPolynomial k]
forall a. HasCallStack => [Char] -> a
error ([Char] -> [UPolynomial k]) -> [Char] -> [UPolynomial k]
forall a b. (a -> b) -> a -> b
$ [Char]
"ToySolver.Data.Polynomial.Factorization.FiniteField.berlekamp: should not happen"
    go Set (UPolynomial k)
fs (UPolynomial k
b:[UPolynomial k]
bs)
      | Set (UPolynomial k) -> Int
forall a. Set a -> Int
Set.size Set (UPolynomial k)
fs Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
r = Set (UPolynomial k) -> [UPolynomial k]
forall a. Set a -> [a]
Set.toList Set (UPolynomial k)
fs
      | Bool
otherwise = Set (UPolynomial k) -> [UPolynomial k] -> [UPolynomial k]
go ([Set (UPolynomial k)] -> Set (UPolynomial k)
forall (f :: * -> *) a. (Foldable f, Ord a) => f (Set a) -> Set a
Set.unions [UPolynomial k -> Set (UPolynomial k)
func UPolynomial k
fi | UPolynomial k
fi <- Set (UPolynomial k) -> [UPolynomial k]
forall a. Set a -> [a]
Set.toList Set (UPolynomial k)
fs]) [UPolynomial k]
bs
        where
          func :: UPolynomial k -> Set (UPolynomial k)
func UPolynomial k
fi = [UPolynomial k] -> Set (UPolynomial k)
forall a. Ord a => [a] -> Set a
Set.fromList ([UPolynomial k] -> Set (UPolynomial k))
-> [UPolynomial k] -> Set (UPolynomial k)
forall a b. (a -> b) -> a -> b
$ [UPolynomial k]
hs2 [UPolynomial k] -> [UPolynomial k] -> [UPolynomial k]
forall a. [a] -> [a] -> [a]
++ [UPolynomial k]
hs1
            where
              hs1 :: [UPolynomial k]
hs1 = [UPolynomial k
h | k
k <- [k]
forall k. FiniteField k => [k]
allValues, let h :: UPolynomial k
h = UPolynomial k -> UPolynomial k -> UPolynomial k
forall k.
(Eq k, Fractional k) =>
UPolynomial k -> UPolynomial k -> UPolynomial k
P.gcd UPolynomial k
fi (UPolynomial k
b UPolynomial k -> UPolynomial k -> UPolynomial k
forall a. Num a => a -> a -> a
- k -> UPolynomial k
forall k v. (Eq k, Num k) => k -> Polynomial k v
P.constant k
k), UPolynomial k -> Integer
forall t. Degree t => t -> Integer
P.deg UPolynomial k
h Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
0]
              hs2 :: [UPolynomial k]
hs2 = if UPolynomial k -> Integer
forall t. Degree t => t -> Integer
P.deg UPolynomial k
g Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
0 then [UPolynomial k
g] else []
                where
                  g :: UPolynomial k
g = UPolynomial k
fi UPolynomial k -> UPolynomial k -> UPolynomial k
forall k.
(Eq k, Fractional k) =>
UPolynomial k -> UPolynomial k -> UPolynomial k
`P.div` [UPolynomial k] -> UPolynomial k
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product [UPolynomial k]
hs1
    basis :: [UPolynomial k]
basis = UPolynomial k -> [UPolynomial k]
forall k.
(Ord k, FiniteField k) =>
UPolynomial k -> [UPolynomial k]
basisOfBerlekampSubalgebra UPolynomial k
f
    r :: Int
r     = [UPolynomial k] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [UPolynomial k]
basis

basisOfBerlekampSubalgebra :: forall k. (Ord k, FiniteField k) => UPolynomial k -> [UPolynomial k]
basisOfBerlekampSubalgebra :: forall k.
(Ord k, FiniteField k) =>
UPolynomial k -> [UPolynomial k]
basisOfBerlekampSubalgebra UPolynomial k
f =
  (UPolynomial k -> Down Integer)
-> [UPolynomial k] -> [UPolynomial k]
forall b a. Ord b => (a -> b) -> [a] -> [a]
sortOn (Integer -> Down Integer
forall a. a -> Down a
Down (Integer -> Down Integer)
-> (UPolynomial k -> Integer) -> UPolynomial k -> Down Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. UPolynomial k -> Integer
forall t. Degree t => t -> Integer
P.deg) ([UPolynomial k] -> [UPolynomial k])
-> [UPolynomial k] -> [UPolynomial k]
forall a b. (a -> b) -> a -> b
$
    (UPolynomial k -> UPolynomial k)
-> [UPolynomial k] -> [UPolynomial k]
forall a b. (a -> b) -> [a] -> [b]
map (MonomialOrder X -> UPolynomial k -> UPolynomial k
forall r v.
(Eq r, Fractional r) =>
MonomialOrder v -> Polynomial r v -> Polynomial r v
P.toMonic MonomialOrder X
P.nat) ([UPolynomial k] -> [UPolynomial k])
-> [UPolynomial k] -> [UPolynomial k]
forall a b. (a -> b) -> a -> b
$
      [UPolynomial k]
basis
  where
    q :: Integer
q    = k -> Integer
forall k. FiniteField k => k -> Integer
order (k
forall a. HasCallStack => a
undefined :: k)
    d :: Integer
d    = UPolynomial k -> Integer
forall t. Degree t => t -> Integer
P.deg UPolynomial k
f
    x :: UPolynomial k
x    = X -> UPolynomial k
forall a v. Var a v => v -> a
P.var X
X

    qs :: [UPolynomial k]
    qs :: [UPolynomial k]
qs = [(UPolynomial k
xUPolynomial k -> Integer -> UPolynomial k
forall a b. (Num a, Integral b) => a -> b -> a
^(Integer
qInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
i)) UPolynomial k -> UPolynomial k -> UPolynomial k
forall k.
(Eq k, Fractional k) =>
UPolynomial k -> UPolynomial k -> UPolynomial k
`P.mod` UPolynomial k
f | Integer
i <- [Integer
0 .. Integer
d Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1]]

    gb :: [Polynomial k Int]
    gb :: [Polynomial k Int]
gb = MonomialOrder Int -> [Polynomial k Int] -> [Polynomial k Int]
forall k v.
(Eq k, Fractional k, Ord k, Ord v) =>
MonomialOrder v -> [Polynomial k v] -> [Polynomial k v]
GB.basis MonomialOrder Int
forall v. Ord v => MonomialOrder v
P.grlex [Polynomial k Int
p3 | (Polynomial k Int
p3,Monomial X
_) <- Polynomial (Polynomial k Int) X -> [(Polynomial k Int, Monomial X)]
forall k v. Polynomial k v -> [Term k v]
P.terms Polynomial (Polynomial k Int) X
p2]

    p1 :: Polynomial k Int
    p1 :: Polynomial k Int
p1 = [Polynomial k Int] -> Polynomial k Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [Int -> Polynomial k Int
forall a v. Var a v => v -> a
P.var Int
i Polynomial k Int -> Polynomial k Int -> Polynomial k Int
forall a. Num a => a -> a -> a
* (UPolynomial k -> (X -> Polynomial k Int) -> Polynomial k Int
forall k v2 v1.
(Eq k, Num k, Ord v2) =>
Polynomial k v1 -> (v1 -> Polynomial k v2) -> Polynomial k v2
P.subst UPolynomial k
qi (\X
X -> Int -> Polynomial k Int
forall a v. Var a v => v -> a
P.var (-Int
1)) Polynomial k Int -> Polynomial k Int -> Polynomial k Int
forall a. Num a => a -> a -> a
- (Int -> Polynomial k Int
forall a v. Var a v => v -> a
P.var (-Int
1) Polynomial k Int -> Int -> Polynomial k Int
forall a b. (Num a, Integral b) => a -> b -> a
^ Int
i)) | (Int
i, UPolynomial k
qi) <- [Int] -> [UPolynomial k] -> [(Int, UPolynomial k)]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
0..] [UPolynomial k]
qs]
    p2 :: UPolynomial (Polynomial k Int)
    p2 :: Polynomial (Polynomial k Int) X
p2 = Polynomial k Int -> Int -> Polynomial (Polynomial k Int) X
forall k v.
(Ord k, Num k, Ord v) =>
Polynomial k v -> v -> UPolynomial (Polynomial k v)
P.toUPolynomialOf Polynomial k Int
p1 (-Int
1)

    es :: [(Int, Polynomial k Int)]
es  = [(Int
i, MonomialOrder Int
-> Polynomial k Int -> [Polynomial k Int] -> Polynomial k Int
forall k v.
(Eq k, Fractional k, Ord v) =>
MonomialOrder v
-> Polynomial k v -> [Polynomial k v] -> Polynomial k v
P.reduce MonomialOrder Int
forall v. Ord v => MonomialOrder v
P.grlex (Int -> Polynomial k Int
forall a v. Var a v => v -> a
P.var Int
i) [Polynomial k Int]
gb) | Int
i <- [Int
0 .. Integer -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Integer
d Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1]]
    vs1 :: [Int]
vs1 = [Int
i           | (Int
i, Polynomial k Int
gi_def) <- [(Int, Polynomial k Int)]
es, Polynomial k Int
gi_def Polynomial k Int -> Polynomial k Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int -> Polynomial k Int
forall a v. Var a v => v -> a
P.var Int
i]
    vs2 :: [(Int, Polynomial k Int)]
vs2 = [(Int
i, Polynomial k Int
gi_def) | (Int
i, Polynomial k Int
gi_def) <- [(Int, Polynomial k Int)]
es, Polynomial k Int
gi_def Polynomial k Int -> Polynomial k Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int -> Polynomial k Int
forall a v. Var a v => v -> a
P.var Int
i]

    basis :: [UPolynomial k]
    basis :: [UPolynomial k]
basis = [ UPolynomial k
xUPolynomial k -> Int -> UPolynomial k
forall a b. (Num a, Integral b) => a -> b -> a
^Int
i UPolynomial k -> UPolynomial k -> UPolynomial k
forall a. Num a => a -> a -> a
+ [UPolynomial k] -> UPolynomial k
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [k -> UPolynomial k
forall k v. (Eq k, Num k) => k -> Polynomial k v
P.constant ((Int -> k) -> Polynomial k Int -> k
forall k v. Num k => (v -> k) -> Polynomial k v -> k
P.eval (Int -> Int -> k
forall {a} {a}. (Eq a, Num a) => a -> a -> a
delta Int
i) Polynomial k Int
gj_def) UPolynomial k -> UPolynomial k -> UPolynomial k
forall a. Num a => a -> a -> a
* UPolynomial k
xUPolynomial k -> Int -> UPolynomial k
forall a b. (Num a, Integral b) => a -> b -> a
^Int
j | (Int
j, Polynomial k Int
gj_def) <- [(Int, Polynomial k Int)]
vs2] | Int
i <- [Int]
vs1 ]
      where
        delta :: a -> a -> a
delta a
i a
k
          | a
ka -> a -> Bool
forall a. Eq a => a -> a -> Bool
==a
i      = a
1
          | Bool
otherwise = a
0