-- |
-- Module:      Data.Poly.Internal.Multi
-- Copyright:   (c) 2020 Andrew Lelechenko
-- Licence:     BSD3
-- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
--

{-# LANGUAGE DataKinds                  #-}
{-# LANGUAGE FlexibleContexts           #-}
{-# LANGUAGE FlexibleInstances          #-}
{-# LANGUAGE GADTs                      #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE LambdaCase                 #-}
{-# LANGUAGE PatternSynonyms            #-}
{-# LANGUAGE PolyKinds                  #-}
{-# LANGUAGE ScopedTypeVariables        #-}
{-# LANGUAGE StandaloneDeriving         #-}
{-# LANGUAGE TypeApplications           #-}
{-# LANGUAGE TypeFamilies               #-}
{-# LANGUAGE TypeOperators              #-}
{-# LANGUAGE UndecidableInstances       #-}
{-# LANGUAGE ViewPatterns               #-}

{-# OPTIONS_GHC -fno-warn-orphans #-}

module Data.Poly.Internal.Multi
  ( MultiPoly(..)
  , VMultiPoly
  , UMultiPoly
  , toMultiPoly
  , toMultiPoly'
  , leading
  , monomial
  , monomial'
  , scale
  , scale'
  , pattern X
  , pattern Y
  , pattern Z
  , pattern X'
  , pattern Y'
  , pattern Z'
  , eval
  , eval'
  , subst
  , subst'
  , substitute
  , substitute'
  , deriv
  , deriv'
  , integral
  , integral'
  -- * Univariate polynomials
  , Poly
  , VPoly
  , UPoly
  , unPoly
  -- * Conversions
  , segregate
  , unsegregate
  ) where

import Prelude hiding (quot, gcd)
import Control.Arrow
import Control.DeepSeq
import Data.Coerce
import Data.Euclidean (Field, quot)
import Data.Finite
import Data.Kind
import Data.List (intersperse)
import Data.Semiring (Semiring(..), Ring())
import qualified Data.Semiring as Semiring
import qualified Data.Vector as V
import qualified Data.Vector.Generic as G
import qualified Data.Vector.Generic.Sized as SG
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Sized as SU
import qualified Data.Vector.Sized as SV
import GHC.Exts (IsList(..))
import GHC.TypeNats (KnownNat, Nat, type (+), type (<=))

import Data.Poly.Internal.Multi.Core

-- | Sparse polynomials of @n@ variables with coefficients from @a@,
-- backed by a 'G.Vector' @v@ (boxed, unboxed, storable, etc.).
--
-- Use the patterns 'Data.Poly.Multi.X',
-- 'Data.Poly.Multi.Y' and
-- 'Data.Poly.Multi.Z' for construction:
--
-- >>> :set -XDataKinds
-- >>> (X + 1) + (Y - 1) + Z :: VMultiPoly 3 Integer
-- 1 * X + 1 * Y + 1 * Z
-- >>> (X + 1) * (Y - 1) :: UMultiPoly 2 Int
-- 1 * X * Y + (-1) * X + 1 * Y + (-1)
--
-- Polynomials are stored normalized, without
-- zero coefficients, so 0 * 'Data.Poly.Multi.X' + 1 equals to 1.
--
-- The 'Ord' instance does not make much sense mathematically,
-- it is defined only for the sake of 'Data.Set.Set', 'Data.Map.Map', etc.
--
-- Due to being polymorphic by multiple axis, the performance of `MultiPoly` crucially
-- depends on specialisation of instances. Clients are strongly recommended
-- to compile with @ghc-options:@ @-fspecialise-aggressively@ and suggested to enable @-O2@.
--
-- @since 0.5.0.0
newtype MultiPoly (v :: Type -> Type) (n :: Nat) (a :: Type) = MultiPoly
  { forall (v :: * -> *) (n :: Natural) a.
MultiPoly v n a -> v (Vector n Word, a)
unMultiPoly :: v (SU.Vector n Word, a)
  -- ^ Convert a 'MultiPoly' to a vector of (powers, coefficient) pairs.
  --
  -- @since 0.5.0.0
  }

deriving instance Eq     (v (SU.Vector n Word, a)) => Eq     (MultiPoly v n a)
deriving instance Ord    (v (SU.Vector n Word, a)) => Ord    (MultiPoly v n a)
deriving instance NFData (v (SU.Vector n Word, a)) => NFData (MultiPoly v n a)

-- | Multivariate polynomials backed by boxed vectors.
--
-- @since 0.5.0.0
type VMultiPoly (n :: Nat) (a :: Type) = MultiPoly V.Vector n a

-- | Multivariate polynomials backed by unboxed vectors.
--
-- @since 0.5.0.0
type UMultiPoly (n :: Nat) (a :: Type) = MultiPoly U.Vector n a

-- | Sparse univariate polynomials with coefficients from @a@,
-- backed by a 'G.Vector' @v@ (boxed, unboxed, storable, etc.).
--
-- Use pattern 'Data.Poly.Multi.X' for construction:
--
-- >>> (X + 1) + (X - 1) :: VPoly Integer
-- 2 * X
-- >>> (X + 1) * (X - 1) :: UPoly Int
-- 1 * X^2 + (-1)
--
-- Polynomials are stored normalized, without
-- zero coefficients, so 0 * 'Data.Poly.Multi.X' + 1 equals to 1.
--
-- 'Ord' instance does not make much sense mathematically,
-- it is defined only for the sake of 'Data.Set.Set', 'Data.Map.Map', etc.
--
-- Due to being polymorphic by multiple axis, the performance of `Poly` crucially
-- depends on specialisation of instances. Clients are strongly recommended
-- to compile with @ghc-options:@ @-fspecialise-aggressively@ and suggested to enable @-O2@.
--
-- @since 0.3.0.0
type Poly (v :: Type -> Type) (a :: Type) = MultiPoly v 1 a

-- | Polynomials backed by boxed vectors.
--
-- @since 0.3.0.0
type VPoly (a :: Type) = Poly V.Vector a

-- | Polynomials backed by unboxed vectors.
--
-- @since 0.3.0.0
type UPoly (a :: Type) = Poly U.Vector a

-- | Convert a 'Poly' to a vector of coefficients.
--
-- @since 0.3.0.0
unPoly
  :: (G.Vector v (Word, a), G.Vector v (SU.Vector 1 Word, a))
  => Poly v a
  -> v (Word, a)
unPoly :: forall (v :: * -> *) a.
(Vector v (Word, a), Vector v (Vector 1 Word, a)) =>
Poly v a -> v (Word, a)
unPoly = forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
G.map (forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first forall (n :: Natural) a. Unbox a => Vector (1 + n) a -> a
SU.head) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) (n :: Natural) a.
MultiPoly v n a -> v (Vector n Word, a)
unMultiPoly

instance (Eq a, Semiring a, G.Vector v (SU.Vector n Word, a)) => IsList (MultiPoly v n a) where
  type Item (MultiPoly v n a) = (SU.Vector n Word, a)
  fromList :: [Item (MultiPoly v n a)] -> MultiPoly v n a
fromList = forall a (v :: * -> *) (n :: Natural).
(Eq a, Semiring a, Vector v (Vector n Word, a)) =>
v (Vector n Word, a) -> MultiPoly v n a
toMultiPoly' forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a. Vector v a => [a] -> v a
G.fromList
  fromListN :: Int -> [Item (MultiPoly v n a)] -> MultiPoly v n a
fromListN = (forall a (v :: * -> *) (n :: Natural).
(Eq a, Semiring a, Vector v (Vector n Word, a)) =>
v (Vector n Word, a) -> MultiPoly v n a
toMultiPoly' forall b c a. (b -> c) -> (a -> b) -> a -> c
.) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a. Vector v a => Int -> [a] -> v a
G.fromListN
  toList :: MultiPoly v n a -> [Item (MultiPoly v n a)]
toList = forall (v :: * -> *) a. Vector v a => v a -> [a]
G.toList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) (n :: Natural) a.
MultiPoly v n a -> v (Vector n Word, a)
unMultiPoly

instance (Show a, KnownNat n, G.Vector v (SU.Vector n Word, a)) => Show (MultiPoly v n a) where
  showsPrec :: Int -> MultiPoly v n a -> ShowS
showsPrec Int
d (MultiPoly v (Vector n Word, a)
xs)
    | forall (v :: * -> *) a. Vector v a => v a -> Bool
G.null v (Vector n Word, a)
xs
      = String -> ShowS
showString String
"0"
    | Bool
otherwise
      = Bool -> ShowS -> ShowS
showParen (Int
d forall a. Ord a => a -> a -> Bool
> Int
0)
      forall a b. (a -> b) -> a -> b
$ forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl forall b c a. (b -> c) -> (a -> b) -> a -> c
(.) forall a. a -> a
id
      forall a b. (a -> b) -> a -> b
$ forall a. a -> [a] -> [a]
intersperse (String -> ShowS
showString String
" + ")
      forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) b a.
Vector v b =>
(a -> b -> a) -> a -> v b -> a
G.foldl (\[ShowS]
acc (Vector n Word
is, a
c) -> Vector n Word -> a -> ShowS
showCoeff Vector n Word
is a
c forall a. a -> [a] -> [a]
: [ShowS]
acc) [] v (Vector n Word, a)
xs
    where
      showCoeff :: Vector n Word -> a -> ShowS
showCoeff Vector n Word
is a
c
        = forall a. Show a => Int -> a -> ShowS
showsPrec Int
7 a
c forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl forall b c a. (b -> c) -> (a -> b) -> a -> c
(.) forall a. a -> a
id
        ( forall a b. (a -> b) -> [a] -> [b]
map ((String -> ShowS
showString String
" * " forall b c a. (b -> c) -> (a -> b) -> a -> c
.) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Word -> Finite n -> ShowS
showPower)
        forall a b. (a -> b) -> a -> b
$ forall a. (a -> Bool) -> [a] -> [a]
filter ((forall a. Eq a => a -> a -> Bool
/= Word
0) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a, b) -> a
fst)
        forall a b. (a -> b) -> a -> b
$ forall a b. [a] -> [b] -> [(a, b)]
zip (forall a (n :: Natural). Unbox a => Vector n a -> [a]
SU.toList Vector n Word
is) (forall (n :: Natural). KnownNat n => [Finite n]
finites :: [Finite n]))

      -- Powers are guaranteed to be non-negative
      showPower :: Word -> Finite n -> String -> String
      showPower :: Word -> Finite n -> ShowS
showPower Word
1 Finite n
n = String -> ShowS
showString (Finite n -> String
showVar Finite n
n)
      showPower Word
i Finite n
n = String -> ShowS
showString (Finite n -> String
showVar Finite n
n) forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString (String
"^" forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Word
i)

      showVar :: Finite n -> String
      showVar :: Finite n -> String
showVar = \case
        Finite n
0 -> String
"X"
        Finite n
1 -> String
"Y"
        Finite n
2 -> String
"Z"
        Finite n
k -> String
"X" forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Finite n
k

-- | Make a 'MultiPoly' from a list of (powers, coefficient) pairs.
--
-- >>> :set -XOverloadedLists -XDataKinds
-- >>> import Data.Vector.Generic.Sized (fromTuple)
-- >>> toMultiPoly [(fromTuple (0,0),1),(fromTuple (0,1),2),(fromTuple (1,0),3)] :: VMultiPoly 2 Integer
-- 3 * X + 2 * Y + 1
-- >>> toMultiPoly [(fromTuple (0,0),0),(fromTuple (0,1),0),(fromTuple (1,0),0)] :: UMultiPoly 2 Int
-- 0
--
-- @since 0.5.0.0
toMultiPoly
  :: (Eq a, Num a, G.Vector v (SU.Vector n Word, a))
  => v (SU.Vector n Word, a)
  -> MultiPoly v n a
toMultiPoly :: forall a (v :: * -> *) (n :: Natural).
(Eq a, Num a, Vector v (Vector n Word, a)) =>
v (Vector n Word, a) -> MultiPoly v n a
toMultiPoly = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) t a.
(Vector v (t, a), Ord t) =>
(a -> Bool) -> (a -> a -> a) -> v (t, a) -> v (t, a)
normalize (forall a. Eq a => a -> a -> Bool
/= a
0) forall a. Num a => a -> a -> a
(+)
{-# INLINABLE toMultiPoly #-}

toMultiPoly'
  :: (Eq a, Semiring a, G.Vector v (SU.Vector n Word, a))
  => v (SU.Vector n Word, a)
  -> MultiPoly v n a
toMultiPoly' :: forall a (v :: * -> *) (n :: Natural).
(Eq a, Semiring a, Vector v (Vector n Word, a)) =>
v (Vector n Word, a) -> MultiPoly v n a
toMultiPoly' = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) t a.
(Vector v (t, a), Ord t) =>
(a -> Bool) -> (a -> a -> a) -> v (t, a) -> v (t, a)
normalize (forall a. Eq a => a -> a -> Bool
/= forall a. Semiring a => a
zero) forall a. Semiring a => a -> a -> a
plus
{-# INLINABLE toMultiPoly' #-}

-- | Note that 'abs' = 'id' and 'signum' = 'const' 1.
instance (Eq a, Num a, KnownNat n, G.Vector v (SU.Vector n Word, a)) => Num (MultiPoly v n a) where

  + :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
(+) = coerce :: forall a b. Coercible a b => a -> b
coerce (forall (v :: * -> *) t a.
(Vector v (t, a), Ord t) =>
(a -> Bool) -> (a -> a -> a) -> v (t, a) -> v (t, a) -> v (t, a)
plusPoly    @v @(SU.Vector n Word) @a (forall a. Eq a => a -> a -> Bool
/= a
0) forall a. Num a => a -> a -> a
(+))
  (-) = coerce :: forall a b. Coercible a b => a -> b
coerce (forall (v :: * -> *) t a.
(Vector v (t, a), Ord t) =>
(a -> Bool)
-> (a -> a) -> (a -> a -> a) -> v (t, a) -> v (t, a) -> v (t, a)
minusPoly   @v @(SU.Vector n Word) @a (forall a. Eq a => a -> a -> Bool
/= a
0) forall a. Num a => a -> a
negate (-))
  * :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
(*) = coerce :: forall a b. Coercible a b => a -> b
coerce (forall (v :: * -> *) t a.
(Vector v (t, a), Ord t, Num t) =>
(a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> v (t, a)
-> v (t, a)
-> v (t, a)
convolution @v @(SU.Vector n Word) @a (forall a. Eq a => a -> a -> Bool
/= a
0) forall a. Num a => a -> a -> a
(+) forall a. Num a => a -> a -> a
(*))

  negate :: MultiPoly v n a -> MultiPoly v n a
negate (MultiPoly v (Vector n Word, a)
xs) = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
G.map (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. Num a => a -> a
negate) v (Vector n Word, a)
xs
  abs :: MultiPoly v n a -> MultiPoly v n a
abs = forall a. a -> a
id
  signum :: MultiPoly v n a -> MultiPoly v n a
signum = forall a b. a -> b -> a
const MultiPoly v n a
1
  fromInteger :: Integer -> MultiPoly v n a
fromInteger Integer
n = case forall a. Num a => Integer -> a
fromInteger Integer
n of
    a
0 -> forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall (v :: * -> *) a. Vector v a => v a
G.empty
    a
m -> forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a. Vector v a => a -> v a
G.singleton (Vector n Word
0, a
m)

  {-# INLINE (+) #-}
  {-# INLINE (-) #-}
  {-# INLINE negate #-}
  {-# INLINE fromInteger #-}
  {-# INLINE (*) #-}

instance (Eq a, Semiring a, KnownNat n, G.Vector v (SU.Vector n Word, a)) => Semiring (MultiPoly v n a) where
  zero :: MultiPoly v n a
zero = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall (v :: * -> *) a. Vector v a => v a
G.empty
  one :: MultiPoly v n a
one
    | (forall a. Semiring a => a
one :: a) forall a. Eq a => a -> a -> Bool
== forall a. Semiring a => a
zero = forall a. Semiring a => a
zero
    | Bool
otherwise = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a. Vector v a => a -> v a
G.singleton (Vector n Word
0, forall a. Semiring a => a
one)

  plus :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
plus  = coerce :: forall a b. Coercible a b => a -> b
coerce (forall (v :: * -> *) t a.
(Vector v (t, a), Ord t) =>
(a -> Bool) -> (a -> a -> a) -> v (t, a) -> v (t, a) -> v (t, a)
plusPoly    @v @(SU.Vector n Word) @a (forall a. Eq a => a -> a -> Bool
/= forall a. Semiring a => a
zero) forall a. Semiring a => a -> a -> a
plus)
  times :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
times = coerce :: forall a b. Coercible a b => a -> b
coerce (forall (v :: * -> *) t a.
(Vector v (t, a), Ord t, Num t) =>
(a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> v (t, a)
-> v (t, a)
-> v (t, a)
convolution @v @(SU.Vector n Word) @a (forall a. Eq a => a -> a -> Bool
/= forall a. Semiring a => a
zero) forall a. Semiring a => a -> a -> a
plus forall a. Semiring a => a -> a -> a
times)

  {-# INLINE zero #-}
  {-# INLINE one #-}
  {-# INLINE plus #-}
  {-# INLINE times #-}

  fromNatural :: Natural -> MultiPoly v n a
fromNatural Natural
n = if a
n' forall a. Eq a => a -> a -> Bool
== forall a. Semiring a => a
zero then forall a. Semiring a => a
zero else forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a. Vector v a => a -> v a
G.singleton (Vector n Word
0, a
n')
    where
      n' :: a
      n' :: a
n' = forall a. Semiring a => Natural -> a
fromNatural Natural
n
  {-# INLINE fromNatural #-}

instance (Eq a, Ring a, KnownNat n, G.Vector v (SU.Vector n Word, a)) => Ring (MultiPoly v n a) where
  negate :: MultiPoly v n a -> MultiPoly v n a
negate (MultiPoly v (Vector n Word, a)
xs) = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
G.map (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. Ring a => a -> a
Semiring.negate) v (Vector n Word, a)
xs

-- | Return the leading power and coefficient of a non-zero polynomial.
--
-- >>> import Data.Poly.Sparse (UPoly)
-- >>> leading ((2 * X + 1) * (2 * X^2 - 1) :: UPoly Int)
-- Just (3,4)
-- >>> leading (0 :: UPoly Int)
-- Nothing
--
-- @since 0.3.0.0
leading :: G.Vector v (SU.Vector 1 Word, a) => Poly v a -> Maybe (Word, a)
leading :: forall (v :: * -> *) a.
Vector v (Vector 1 Word, a) =>
Poly v a -> Maybe (Word, a)
leading (MultiPoly v (Vector 1 Word, a)
v)
  | forall (v :: * -> *) a. Vector v a => v a -> Bool
G.null v (Vector 1 Word, a)
v  = forall a. Maybe a
Nothing
  | Bool
otherwise = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first forall (n :: Natural) a. Unbox a => Vector (1 + n) a -> a
SU.head forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a. Vector v a => v a -> a
G.last v (Vector 1 Word, a)
v

-- | Multiply a polynomial by a monomial, expressed as powers and a coefficient.
--
-- >>> :set -XDataKinds
-- >>> import Data.Vector.Generic.Sized (fromTuple)
-- >>> scale (fromTuple (1, 1)) 3 (X^2 + Y) :: UMultiPoly 2 Int
-- 3 * X^3 * Y + 3 * X * Y^2
--
-- @since 0.5.0.0
scale
  :: (Eq a, Num a, KnownNat n, G.Vector v (SU.Vector n Word, a))
  => SU.Vector n Word
  -> a
  -> MultiPoly v n a
  -> MultiPoly v n a
scale :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Num a, KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Word -> a -> MultiPoly v n a -> MultiPoly v n a
scale Vector n Word
yp a
yc = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) t a.
(Vector v (t, a), Num t) =>
(a -> Bool) -> (a -> a -> a) -> t -> a -> v (t, a) -> v (t, a)
scaleInternal (forall a. Eq a => a -> a -> Bool
/= a
0) forall a. Num a => a -> a -> a
(*) Vector n Word
yp a
yc forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) (n :: Natural) a.
MultiPoly v n a -> v (Vector n Word, a)
unMultiPoly

scale'
  :: (Eq a, Semiring a, KnownNat n, G.Vector v (SU.Vector n Word, a))
  => SU.Vector n Word
  -> a
  -> MultiPoly v n a
  -> MultiPoly v n a
scale' :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Word -> a -> MultiPoly v n a -> MultiPoly v n a
scale' Vector n Word
yp a
yc = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) t a.
(Vector v (t, a), Num t) =>
(a -> Bool) -> (a -> a -> a) -> t -> a -> v (t, a) -> v (t, a)
scaleInternal (forall a. Eq a => a -> a -> Bool
/= forall a. Semiring a => a
zero) forall a. Semiring a => a -> a -> a
times Vector n Word
yp a
yc forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) (n :: Natural) a.
MultiPoly v n a -> v (Vector n Word, a)
unMultiPoly

-- | Create a monomial from powers and a coefficient.
--
-- @since 0.5.0.0
monomial
  :: (Eq a, Num a, G.Vector v (SU.Vector n Word, a))
  => SU.Vector n Word
  -> a
  -> MultiPoly v n a
monomial :: forall a (v :: * -> *) (n :: Natural).
(Eq a, Num a, Vector v (Vector n Word, a)) =>
Vector n Word -> a -> MultiPoly v n a
monomial Vector n Word
p a
c
  | a
c forall a. Eq a => a -> a -> Bool
== a
0    = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall (v :: * -> *) a. Vector v a => v a
G.empty
  | Bool
otherwise = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a. Vector v a => a -> v a
G.singleton (Vector n Word
p, a
c)
{-# INLINABLE monomial #-}

monomial'
  :: (Eq a, Semiring a, G.Vector v (SU.Vector n Word, a))
  => SU.Vector n Word
  -> a
  -> MultiPoly v n a
monomial' :: forall a (v :: * -> *) (n :: Natural).
(Eq a, Semiring a, Vector v (Vector n Word, a)) =>
Vector n Word -> a -> MultiPoly v n a
monomial' Vector n Word
p a
c
  | a
c forall a. Eq a => a -> a -> Bool
== forall a. Semiring a => a
zero = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall (v :: * -> *) a. Vector v a => v a
G.empty
  | Bool
otherwise = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a. Vector v a => a -> v a
G.singleton (Vector n Word
p, a
c)
{-# INLINABLE monomial' #-}

-- | Evaluate the polynomial at a given point.
--
-- >>> :set -XDataKinds
-- >>> import Data.Vector.Generic.Sized (fromTuple)
-- >>> eval (X^2 + Y^2 :: UMultiPoly 2 Int) (fromTuple (3, 4) :: Data.Vector.Sized.Vector 2 Int)
-- 25
--
-- @since 0.5.0.0
eval
  :: (Num a, G.Vector v (SU.Vector n Word, a), G.Vector u a)
  => MultiPoly v n a
  -> SG.Vector u n a
  -> a
eval :: forall a (v :: * -> *) (n :: Natural) (u :: * -> *).
(Num a, Vector v (Vector n Word, a), Vector u a) =>
MultiPoly v n a -> Vector u n a -> a
eval = forall (v :: * -> *) (u :: * -> *) (n :: Natural) a b.
(Vector v (Vector n Word, a), Vector u b, Num b) =>
(a -> b -> b) -> MultiPoly v n a -> Vector u n b -> b
substitute forall a. Num a => a -> a -> a
(*)
{-# INLINE eval #-}

eval'
  :: (Semiring a, G.Vector v (SU.Vector n Word, a), G.Vector u a)
  => MultiPoly v n a
  -> SG.Vector u n a
  -> a
eval' :: forall a (v :: * -> *) (n :: Natural) (u :: * -> *).
(Semiring a, Vector v (Vector n Word, a), Vector u a) =>
MultiPoly v n a -> Vector u n a -> a
eval' = forall (v :: * -> *) (u :: * -> *) (n :: Natural) a b.
(Vector v (Vector n Word, a), Vector u b, Semiring b) =>
(a -> b -> b) -> MultiPoly v n a -> Vector u n b -> b
substitute' forall a. Semiring a => a -> a -> a
times
{-# INLINE eval' #-}

-- | Substitute other polynomials instead of the variables.
--
-- >>> :set -XDataKinds
-- >>> import Data.Vector.Generic.Sized (fromTuple)
-- >>> subst (X^2 + Y^2 + Z^2 :: UMultiPoly 3 Int) (fromTuple (X + 1, Y + 1, X + Y :: UMultiPoly 2 Int))
-- 2 * X^2 + 2 * X * Y + 2 * X + 2 * Y^2 + 2 * Y + 2
--
-- @since 0.5.0.0
subst
  :: (Eq a, Num a, KnownNat m, G.Vector v (SU.Vector n Word, a), G.Vector w (SU.Vector m Word, a))
  => MultiPoly v n a
  -> SV.Vector n (MultiPoly w m a)
  -> MultiPoly w m a
subst :: forall a (m :: Natural) (v :: * -> *) (n :: Natural) (w :: * -> *).
(Eq a, Num a, KnownNat m, Vector v (Vector n Word, a),
 Vector w (Vector m Word, a)) =>
MultiPoly v n a -> Vector n (MultiPoly w m a) -> MultiPoly w m a
subst = forall (v :: * -> *) (u :: * -> *) (n :: Natural) a b.
(Vector v (Vector n Word, a), Vector u b, Num b) =>
(a -> b -> b) -> MultiPoly v n a -> Vector u n b -> b
substitute (forall a (n :: Natural) (v :: * -> *).
(Eq a, Num a, KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Word -> a -> MultiPoly v n a -> MultiPoly v n a
scale Vector m Word
0)
{-# INLINE subst #-}

subst'
  :: (Eq a, Semiring a, KnownNat m, G.Vector v (SU.Vector n Word, a), G.Vector w (SU.Vector m Word, a))
  => MultiPoly v n a
  -> SV.Vector n (MultiPoly w m a)
  -> MultiPoly w m a
subst' :: forall a (m :: Natural) (v :: * -> *) (n :: Natural) (w :: * -> *).
(Eq a, Semiring a, KnownNat m, Vector v (Vector n Word, a),
 Vector w (Vector m Word, a)) =>
MultiPoly v n a -> Vector n (MultiPoly w m a) -> MultiPoly w m a
subst' = forall (v :: * -> *) (u :: * -> *) (n :: Natural) a b.
(Vector v (Vector n Word, a), Vector u b, Semiring b) =>
(a -> b -> b) -> MultiPoly v n a -> Vector u n b -> b
substitute' (forall a (n :: Natural) (v :: * -> *).
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Word -> a -> MultiPoly v n a -> MultiPoly v n a
scale' Vector m Word
0)
{-# INLINE subst' #-}

substitute
  :: forall v u n a b.
     (G.Vector v (SU.Vector n Word, a), G.Vector u b, Num b)
  => (a -> b -> b)
  -> MultiPoly v n a
  -> SG.Vector u n b
  -> b
substitute :: forall (v :: * -> *) (u :: * -> *) (n :: Natural) a b.
(Vector v (Vector n Word, a), Vector u b, Num b) =>
(a -> b -> b) -> MultiPoly v n a -> Vector u n b -> b
substitute a -> b -> b
f (MultiPoly v (Vector n Word, a)
cs) Vector u n b
xs = forall (v :: * -> *) b a.
Vector v b =>
(a -> b -> a) -> a -> v b -> a
G.foldl' b -> (Vector n Word, a) -> b
go b
0 v (Vector n Word, a)
cs
  where
    go :: b -> (SU.Vector n Word, a) -> b
    go :: b -> (Vector n Word, a) -> b
go b
acc (Vector n Word
ps, a
c) = b
acc forall a. Num a => a -> a -> a
+ a -> b -> b
f a
c (Vector n Word -> b
doMonom Vector n Word
ps)

    doMonom :: SU.Vector n Word -> b
    doMonom :: Vector n Word -> b
doMonom = forall b a (n :: Natural).
Unbox b =>
(a -> Finite n -> b -> a) -> a -> Vector n b -> a
SU.ifoldl' (\b
acc Finite n
i Word
p -> b
acc forall a. Num a => a -> a -> a
* ((Vector u n b
xs forall (v :: * -> *) (n :: Natural) a.
Vector v a =>
Vector v n a -> Finite n -> a
`SG.index` Finite n
i) forall a b. (Num a, Integral b) => a -> b -> a
^ Word
p)) b
1
{-# INLINE substitute #-}

substitute'
  :: forall v u n a b.
     (G.Vector v (SU.Vector n Word, a), G.Vector u b, Semiring b)
  => (a -> b -> b)
  -> MultiPoly v n a
  -> SG.Vector u n b
  -> b
substitute' :: forall (v :: * -> *) (u :: * -> *) (n :: Natural) a b.
(Vector v (Vector n Word, a), Vector u b, Semiring b) =>
(a -> b -> b) -> MultiPoly v n a -> Vector u n b -> b
substitute' a -> b -> b
f (MultiPoly v (Vector n Word, a)
cs) Vector u n b
xs = forall (v :: * -> *) b a.
Vector v b =>
(a -> b -> a) -> a -> v b -> a
G.foldl' b -> (Vector n Word, a) -> b
go forall a. Semiring a => a
zero v (Vector n Word, a)
cs
  where
    go :: b -> (SU.Vector n Word, a) -> b
    go :: b -> (Vector n Word, a) -> b
go b
acc (Vector n Word
ps, a
c) = b
acc forall a. Semiring a => a -> a -> a
`plus` a -> b -> b
f a
c (Vector n Word -> b
doMonom Vector n Word
ps)

    doMonom :: SU.Vector n Word -> b
    doMonom :: Vector n Word -> b
doMonom = forall b a (n :: Natural).
Unbox b =>
(a -> Finite n -> b -> a) -> a -> Vector n b -> a
SU.ifoldl' (\b
acc Finite n
i Word
p -> b
acc forall a. Semiring a => a -> a -> a
`times` ((Vector u n b
xs forall (v :: * -> *) (n :: Natural) a.
Vector v a =>
Vector v n a -> Finite n -> a
`SG.index` Finite n
i) forall a b. (Semiring a, Integral b) => a -> b -> a
Semiring.^ Word
p)) forall a. Semiring a => a
one
{-# INLINE substitute' #-}

-- | Take the derivative of the polynomial with respect to the /i/-th variable.
--
-- >>> :set -XDataKinds
-- >>> deriv 0 (X^3 + 3 * Y) :: UMultiPoly 2 Int
-- 3 * X^2
-- >>> deriv 1 (X^3 + 3 * Y) :: UMultiPoly 2 Int
-- 3
--
-- @since 0.5.0.0
deriv
  :: (Eq a, Num a, G.Vector v (SU.Vector n Word, a))
  => Finite n
  -> MultiPoly v n a
  -> MultiPoly v n a
deriv :: forall a (v :: * -> *) (n :: Natural).
(Eq a, Num a, Vector v (Vector n Word, a)) =>
Finite n -> MultiPoly v n a -> MultiPoly v n a
deriv Finite n
i (MultiPoly v (Vector n Word, a)
xs) = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) t a.
Vector v (t, a) =>
(a -> Bool) -> (t -> t) -> (t -> a -> a) -> v (t, a) -> v (t, a)
derivPoly
  (forall a. Eq a => a -> a -> Bool
/= a
0)
  (\Vector n Word
ps -> Vector n Word
ps forall a (m :: Natural).
Unbox a =>
Vector m a -> [(Finite m, a)] -> Vector m a
SU.// [(Finite n
i, Vector n Word
ps forall (n :: Natural) a. Unbox a => Vector n a -> Finite n -> a
`SU.index` Finite n
i forall a. Num a => a -> a -> a
- Word
1)])
  (\Vector n Word
ps a
c -> forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector n Word
ps forall (n :: Natural) a. Unbox a => Vector n a -> Finite n -> a
`SU.index` Finite n
i) forall a. Num a => a -> a -> a
* a
c)
  v (Vector n Word, a)
xs
{-# INLINE deriv #-}

deriv'
  :: (Eq a, Semiring a, G.Vector v (SU.Vector n Word, a))
  => Finite n
  -> MultiPoly v n a
  -> MultiPoly v n a
deriv' :: forall a (v :: * -> *) (n :: Natural).
(Eq a, Semiring a, Vector v (Vector n Word, a)) =>
Finite n -> MultiPoly v n a -> MultiPoly v n a
deriv' Finite n
i (MultiPoly v (Vector n Word, a)
xs) = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) t a.
Vector v (t, a) =>
(a -> Bool) -> (t -> t) -> (t -> a -> a) -> v (t, a) -> v (t, a)
derivPoly
  (forall a. Eq a => a -> a -> Bool
/= forall a. Semiring a => a
zero)
  (\Vector n Word
ps -> Vector n Word
ps forall a (m :: Natural).
Unbox a =>
Vector m a -> [(Finite m, a)] -> Vector m a
SU.// [(Finite n
i, Vector n Word
ps forall (n :: Natural) a. Unbox a => Vector n a -> Finite n -> a
`SU.index` Finite n
i forall a. Num a => a -> a -> a
- Word
1)])
  (\Vector n Word
ps a
c -> forall a. Semiring a => Natural -> a
fromNatural (forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector n Word
ps forall (n :: Natural) a. Unbox a => Vector n a -> Finite n -> a
`SU.index` Finite n
i)) forall a. Semiring a => a -> a -> a
`times` a
c)
  v (Vector n Word, a)
xs
{-# INLINE deriv' #-}

-- | Compute an indefinite integral of the polynomial
-- with respect to the /i/-th variable,
-- setting the constant term to zero.
--
-- >>> :set -XDataKinds
-- >>> integral 0 (3 * X^2 + 2 * Y) :: UMultiPoly 2 Double
-- 1.0 * X^3 + 2.0 * X * Y
-- >>> integral 1 (3 * X^2 + 2 * Y) :: UMultiPoly 2 Double
-- 3.0 * X^2 * Y + 1.0 * Y^2
--
-- @since 0.5.0.0
integral
  :: (Fractional a, G.Vector v (SU.Vector n Word, a))
  => Finite n
  -> MultiPoly v n a
  -> MultiPoly v n a
integral :: forall a (v :: * -> *) (n :: Natural).
(Fractional a, Vector v (Vector n Word, a)) =>
Finite n -> MultiPoly v n a -> MultiPoly v n a
integral Finite n
i (MultiPoly v (Vector n Word, a)
xs)
  = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly
  forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
G.map (\(Vector n Word
ps, a
c) -> let p :: Word
p = Vector n Word
ps forall (n :: Natural) a. Unbox a => Vector n a -> Finite n -> a
`SU.index` Finite n
i in
    (Vector n Word
ps forall a (m :: Natural).
Unbox a =>
Vector m a -> [(Finite m, a)] -> Vector m a
SU.// [(Finite n
i, Word
p forall a. Num a => a -> a -> a
+ Word
1)], a
c forall a. Fractional a => a -> a -> a
/ forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word
p forall a. Num a => a -> a -> a
+ Word
1))) v (Vector n Word, a)
xs
{-# INLINE integral #-}

integral'
  :: (Field a, G.Vector v (SU.Vector n Word, a))
  => Finite n
  -> MultiPoly v n a
  -> MultiPoly v n a
integral' :: forall a (v :: * -> *) (n :: Natural).
(Field a, Vector v (Vector n Word, a)) =>
Finite n -> MultiPoly v n a -> MultiPoly v n a
integral' Finite n
i (MultiPoly v (Vector n Word, a)
xs)
  = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly
  forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
G.map (\(Vector n Word
ps, a
c) -> let p :: Word
p = Vector n Word
ps forall (n :: Natural) a. Unbox a => Vector n a -> Finite n -> a
`SU.index` Finite n
i in
    (Vector n Word
ps forall a (m :: Natural).
Unbox a =>
Vector m a -> [(Finite m, a)] -> Vector m a
SU.// [(Finite n
i, Word
p forall a. Num a => a -> a -> a
+ Word
1)], a
c forall a. Euclidean a => a -> a -> a
`quot` forall a b. (Integral a, Ring b) => a -> b
Semiring.fromIntegral (Word
p forall a. Num a => a -> a -> a
+ Word
1))) v (Vector n Word, a)
xs
{-# INLINE integral' #-}

-- | Create a polynomial equal to the first variable.
--
-- @since 0.5.0.0
pattern X
  :: (Eq a, Num a, KnownNat n, 1 <= n, G.Vector v (SU.Vector n Word, a))
  => MultiPoly v n a
pattern $bX :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Num a, KnownNat n, 1 <= n, Vector v (Vector n Word, a)) =>
MultiPoly v n a
$mX :: forall {r} {a} {n :: Natural} {v :: * -> *}.
(Eq a, Num a, KnownNat n, 1 <= n, Vector v (Vector n Word, a)) =>
MultiPoly v n a -> ((# #) -> r) -> ((# #) -> r) -> r
X <- (isVar 0 -> True)
  where X = forall (v :: * -> *) (n :: Natural) a.
(Eq a, Num a, KnownNat n, Vector v (Vector n Word, a)) =>
Finite n -> MultiPoly v n a
var Finite n
0

pattern X'
  :: (Eq a, Semiring a, KnownNat n, 1 <= n, G.Vector v (SU.Vector n Word, a))
  => MultiPoly v n a
pattern $bX' :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Semiring a, KnownNat n, 1 <= n,
 Vector v (Vector n Word, a)) =>
MultiPoly v n a
$mX' :: forall {r} {a} {n :: Natural} {v :: * -> *}.
(Eq a, Semiring a, KnownNat n, 1 <= n,
 Vector v (Vector n Word, a)) =>
MultiPoly v n a -> ((# #) -> r) -> ((# #) -> r) -> r
X' <- (isVar' 0 -> True)
  where X' = forall (v :: * -> *) (n :: Natural) a.
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) =>
Finite n -> MultiPoly v n a
var' Finite n
0

-- | Create a polynomial equal to the second variable.
--
-- @since 0.5.0.0
pattern Y
  :: (Eq a, Num a, KnownNat n, 2 <= n, G.Vector v (SU.Vector n Word, a))
  => MultiPoly v n a
pattern $bY :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Num a, KnownNat n, 2 <= n, Vector v (Vector n Word, a)) =>
MultiPoly v n a
$mY :: forall {r} {a} {n :: Natural} {v :: * -> *}.
(Eq a, Num a, KnownNat n, 2 <= n, Vector v (Vector n Word, a)) =>
MultiPoly v n a -> ((# #) -> r) -> ((# #) -> r) -> r
Y <- (isVar 1 -> True)
  where Y = forall (v :: * -> *) (n :: Natural) a.
(Eq a, Num a, KnownNat n, Vector v (Vector n Word, a)) =>
Finite n -> MultiPoly v n a
var Finite n
1

pattern Y'
  :: (Eq a, Semiring a, KnownNat n, 2 <= n, G.Vector v (SU.Vector n Word, a))
  => MultiPoly v n a
pattern $bY' :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Semiring a, KnownNat n, 2 <= n,
 Vector v (Vector n Word, a)) =>
MultiPoly v n a
$mY' :: forall {r} {a} {n :: Natural} {v :: * -> *}.
(Eq a, Semiring a, KnownNat n, 2 <= n,
 Vector v (Vector n Word, a)) =>
MultiPoly v n a -> ((# #) -> r) -> ((# #) -> r) -> r
Y' <- (isVar' 1 -> True)
  where Y' = forall (v :: * -> *) (n :: Natural) a.
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) =>
Finite n -> MultiPoly v n a
var' Finite n
1

-- | Create a polynomial equal to the third variable.
--
-- @since 0.5.0.0
pattern Z
  :: (Eq a, Num a, KnownNat n, 3 <= n, G.Vector v (SU.Vector n Word, a))
  => MultiPoly v n a
pattern $bZ :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Num a, KnownNat n, 3 <= n, Vector v (Vector n Word, a)) =>
MultiPoly v n a
$mZ :: forall {r} {a} {n :: Natural} {v :: * -> *}.
(Eq a, Num a, KnownNat n, 3 <= n, Vector v (Vector n Word, a)) =>
MultiPoly v n a -> ((# #) -> r) -> ((# #) -> r) -> r
Z <- (isVar 2 -> True)
  where Z = forall (v :: * -> *) (n :: Natural) a.
(Eq a, Num a, KnownNat n, Vector v (Vector n Word, a)) =>
Finite n -> MultiPoly v n a
var Finite n
2

pattern Z'
  :: (Eq a, Semiring a, KnownNat n, 3 <= n, G.Vector v (SU.Vector n Word, a))
  => MultiPoly v n a
pattern $bZ' :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Semiring a, KnownNat n, 3 <= n,
 Vector v (Vector n Word, a)) =>
MultiPoly v n a
$mZ' :: forall {r} {a} {n :: Natural} {v :: * -> *}.
(Eq a, Semiring a, KnownNat n, 3 <= n,
 Vector v (Vector n Word, a)) =>
MultiPoly v n a -> ((# #) -> r) -> ((# #) -> r) -> r
Z' <- (isVar' 2 -> True)
  where Z' = forall (v :: * -> *) (n :: Natural) a.
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) =>
Finite n -> MultiPoly v n a
var' Finite n
2

var
  :: forall v n a.
     (Eq a, Num a, KnownNat n, G.Vector v (SU.Vector n Word, a))
  => Finite n
  -> MultiPoly v n a
var :: forall (v :: * -> *) (n :: Natural) a.
(Eq a, Num a, KnownNat n, Vector v (Vector n Word, a)) =>
Finite n -> MultiPoly v n a
var Finite n
i
  | (a
1 :: a) forall a. Eq a => a -> a -> Bool
== a
0 = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall (v :: * -> *) a. Vector v a => v a
G.empty
  | Bool
otherwise     = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a. Vector v a => a -> v a
G.singleton
    (forall (n :: Natural) a.
(KnownNat n, Unbox a) =>
(Finite n -> a) -> Vector n a
SU.generate (\Finite n
j -> if Finite n
i forall a. Eq a => a -> a -> Bool
== Finite n
j then Word
1 else Word
0), a
1)
{-# INLINE var #-}

var'
  :: forall v n a.
     (Eq a, Semiring a, KnownNat n, G.Vector v (SU.Vector n Word, a))
  => Finite n
  -> MultiPoly v n a
var' :: forall (v :: * -> *) (n :: Natural) a.
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) =>
Finite n -> MultiPoly v n a
var' Finite n
i
  | (forall a. Semiring a => a
one :: a) forall a. Eq a => a -> a -> Bool
== forall a. Semiring a => a
zero = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall (v :: * -> *) a. Vector v a => v a
G.empty
  | Bool
otherwise          = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a. Vector v a => a -> v a
G.singleton
    (forall (n :: Natural) a.
(KnownNat n, Unbox a) =>
(Finite n -> a) -> Vector n a
SU.generate (\Finite n
j -> if Finite n
i forall a. Eq a => a -> a -> Bool
== Finite n
j then Word
1 else Word
0), forall a. Semiring a => a
one)
{-# INLINE var' #-}

isVar
  :: forall v n a.
     (Eq a, Num a, KnownNat n, G.Vector v (SU.Vector n Word, a))
  => Finite n
  -> MultiPoly v n a
  -> Bool
isVar :: forall (v :: * -> *) (n :: Natural) a.
(Eq a, Num a, KnownNat n, Vector v (Vector n Word, a)) =>
Finite n -> MultiPoly v n a -> Bool
isVar Finite n
i (MultiPoly v (Vector n Word, a)
xs)
  | (a
1 :: a) forall a. Eq a => a -> a -> Bool
== a
0 = forall (v :: * -> *) a. Vector v a => v a -> Bool
G.null v (Vector n Word, a)
xs
  | Bool
otherwise     = forall (v :: * -> *) a. Vector v a => v a -> Int
G.length v (Vector n Word, a)
xs forall a. Eq a => a -> a -> Bool
== Int
1 Bool -> Bool -> Bool
&& forall (v :: * -> *) a. Vector v a => v a -> a
G.unsafeHead v (Vector n Word, a)
xs forall a. Eq a => a -> a -> Bool
== (forall (n :: Natural) a.
(KnownNat n, Unbox a) =>
(Finite n -> a) -> Vector n a
SU.generate (\Finite n
j -> if Finite n
i forall a. Eq a => a -> a -> Bool
== Finite n
j then Word
1 else Word
0), a
1)
{-# INLINE isVar #-}

isVar'
  :: forall v n a.
     (Eq a, Semiring a, KnownNat n, G.Vector v (SU.Vector n Word, a))
  => Finite n
  -> MultiPoly v n a
  -> Bool
isVar' :: forall (v :: * -> *) (n :: Natural) a.
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) =>
Finite n -> MultiPoly v n a -> Bool
isVar' Finite n
i (MultiPoly v (Vector n Word, a)
xs)
  | (forall a. Semiring a => a
one :: a) forall a. Eq a => a -> a -> Bool
== forall a. Semiring a => a
zero = forall (v :: * -> *) a. Vector v a => v a -> Bool
G.null v (Vector n Word, a)
xs
  | Bool
otherwise          = forall (v :: * -> *) a. Vector v a => v a -> Int
G.length v (Vector n Word, a)
xs forall a. Eq a => a -> a -> Bool
== Int
1 Bool -> Bool -> Bool
&& forall (v :: * -> *) a. Vector v a => v a -> a
G.unsafeHead v (Vector n Word, a)
xs forall a. Eq a => a -> a -> Bool
== (forall (n :: Natural) a.
(KnownNat n, Unbox a) =>
(Finite n -> a) -> Vector n a
SU.generate (\Finite n
j -> if Finite n
i forall a. Eq a => a -> a -> Bool
== Finite n
j then Word
1 else Word
0), forall a. Semiring a => a
one)
{-# INLINE isVar' #-}

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

groupOn :: (G.Vector v a, Eq b) => (a -> b) -> v a -> [v a]
groupOn :: forall (v :: * -> *) a b.
(Vector v a, Eq b) =>
(a -> b) -> v a -> [v a]
groupOn a -> b
f = v a -> [v a]
go
  where
    go :: v a -> [v a]
go v a
xs
      | forall (v :: * -> *) a. Vector v a => v a -> Bool
G.null v a
xs = []
      | Bool
otherwise = case Maybe Int
mk of
        Maybe Int
Nothing -> [v a
xs]
        Just Int
k  -> forall (v :: * -> *) a. Vector v a => Int -> v a -> v a
G.unsafeTake (Int
k forall a. Num a => a -> a -> a
+ Int
1) v a
xs forall a. a -> [a] -> [a]
: v a -> [v a]
go (forall (v :: * -> *) a. Vector v a => Int -> v a -> v a
G.unsafeDrop (Int
k forall a. Num a => a -> a -> a
+ Int
1) v a
xs)
        where
          fy :: b
fy = a -> b
f (forall (v :: * -> *) a. Vector v a => v a -> a
G.unsafeHead v a
xs)
          mk :: Maybe Int
mk = forall (v :: * -> *) a.
Vector v a =>
(a -> Bool) -> v a -> Maybe Int
G.findIndex ((forall a. Eq a => a -> a -> Bool
/= b
fy) forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
f) (forall (v :: * -> *) a. Vector v a => v a -> v a
G.unsafeTail v a
xs)

-- | Interpret a multivariate polynomial over 1+/m/ variables
-- as a univariate polynomial, whose coefficients are
-- multivariate polynomials over the last /m/ variables.
--
-- @since 0.5.0.0
segregate
  :: (G.Vector v (SU.Vector (1 + m) Word, a), G.Vector v (SU.Vector m Word, a))
  => MultiPoly v (1 + m) a
  -> VPoly (MultiPoly v m a)
segregate :: forall (v :: * -> *) (m :: Natural) a.
(Vector v (Vector (1 + m) Word, a), Vector v (Vector m Word, a)) =>
MultiPoly v (1 + m) a -> VPoly (MultiPoly v m a)
segregate
  = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly
  forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a. Vector v a => [a] -> v a
G.fromList
  forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map (\v (Vector (1 + m) Word, a)
vs -> (forall (n :: Natural) (m :: Natural) a.
(KnownNat n, Unbox a) =>
Vector (n + m) a -> Vector n a
SU.take (forall a b. (a, b) -> a
fst (forall (v :: * -> *) a. Vector v a => v a -> a
G.unsafeHead v (Vector (1 + m) Word, a)
vs)), forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
G.map (forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first forall (n :: Natural) a. Unbox a => Vector (1 + n) a -> Vector n a
SU.tail) v (Vector (1 + m) Word, a)
vs))
  forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a b.
(Vector v a, Eq b) =>
(a -> b) -> v a -> [v a]
groupOn (forall (n :: Natural) a. Unbox a => Vector (1 + n) a -> a
SU.head forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a, b) -> a
fst)
  forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) (n :: Natural) a.
MultiPoly v n a -> v (Vector n Word, a)
unMultiPoly

-- | Interpret a univariate polynomials, whose coefficients are
-- multivariate polynomials over the first /m/ variables,
-- as a multivariate polynomial over 1+/m/ variables.
--
-- @since 0.5.0.0
unsegregate
  :: (G.Vector v (SU.Vector (1 + m) Word, a), G.Vector v (SU.Vector m Word, a))
  => VPoly (MultiPoly v m a)
  -> MultiPoly v (1 + m) a
unsegregate :: forall (v :: * -> *) (m :: Natural) a.
(Vector v (Vector (1 + m) Word, a), Vector v (Vector m Word, a)) =>
VPoly (MultiPoly v m a) -> MultiPoly v (1 + m) a
unsegregate
  = forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly
  forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a. Vector v a => [v a] -> v a
G.concat
  forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a. Vector v a => v a -> [a]
G.toList
  forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
G.map (\(Vector 1 Word
v, MultiPoly v (Vector m Word, a)
vs) -> forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
G.map (forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first (Vector 1 Word
v forall (n :: Natural) (m :: Natural) a.
Unbox a =>
Vector n a -> Vector m a -> Vector (n + m) a
SU.++)) v (Vector m Word, a)
vs)
  forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) (n :: Natural) a.
MultiPoly v n a -> v (Vector n Word, a)
unMultiPoly