-- |
-- 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 = ((Vector 1 Word, a) -> (Word, a))
-> v (Vector 1 Word, a) -> v (Word, a)
forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
G.map ((Vector 1 Word -> Word) -> (Vector 1 Word, a) -> (Word, a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first Vector 1 Word -> Word
Vector (1 + 0) Word -> Word
forall (n :: Natural) a. Unbox a => Vector (1 + n) a -> a
SU.head) (v (Vector 1 Word, a) -> v (Word, a))
-> (Poly v a -> v (Vector 1 Word, a)) -> Poly v a -> v (Word, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Poly v a -> v (Vector 1 Word, a)
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 = v (Vector n Word, a) -> MultiPoly v n a
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' (v (Vector n Word, a) -> MultiPoly v n a)
-> ([(Vector n Word, a)] -> v (Vector n Word, a))
-> [(Vector n Word, a)]
-> MultiPoly v n a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Vector n Word, a)] -> v (Vector n Word, a)
forall (v :: * -> *) a. Vector v a => [a] -> v a
G.fromList
  fromListN :: Int -> [Item (MultiPoly v n a)] -> MultiPoly v n a
fromListN = (v (Vector n Word, a) -> MultiPoly v n a
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' (v (Vector n Word, a) -> MultiPoly v n a)
-> ([(Vector n Word, a)] -> v (Vector n Word, a))
-> [(Vector n Word, a)]
-> MultiPoly v n a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.) (([(Vector n Word, a)] -> v (Vector n Word, a))
 -> [(Vector n Word, a)] -> MultiPoly v n a)
-> (Int -> [(Vector n Word, a)] -> v (Vector n Word, a))
-> Int
-> [(Vector n Word, a)]
-> MultiPoly v n a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [(Vector n Word, a)] -> v (Vector n Word, a)
forall (v :: * -> *) a. Vector v a => Int -> [a] -> v a
G.fromListN
  toList :: MultiPoly v n a -> [Item (MultiPoly v n a)]
toList = v (Vector n Word, a) -> [(Vector n Word, a)]
forall (v :: * -> *) a. Vector v a => v a -> [a]
G.toList (v (Vector n Word, a) -> [(Vector n Word, a)])
-> (MultiPoly v n a -> v (Vector n Word, a))
-> MultiPoly v n a
-> [(Vector n Word, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MultiPoly v n a -> v (Vector n Word, a)
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)
    | v (Vector n Word, a) -> Bool
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0)
      (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$ (ShowS -> ShowS -> ShowS) -> ShowS -> [ShowS] -> ShowS
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
(.) ShowS
forall a. a -> a
id
      ([ShowS] -> ShowS) -> [ShowS] -> ShowS
forall a b. (a -> b) -> a -> b
$ ShowS -> [ShowS] -> [ShowS]
forall a. a -> [a] -> [a]
intersperse (String -> ShowS
showString String
" + ")
      ([ShowS] -> [ShowS]) -> [ShowS] -> [ShowS]
forall a b. (a -> b) -> a -> b
$ ([ShowS] -> (Vector n Word, a) -> [ShowS])
-> [ShowS] -> v (Vector n Word, a) -> [ShowS]
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 ShowS -> [ShowS] -> [ShowS]
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
        = Int -> a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
7 a
c ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (ShowS -> ShowS -> ShowS) -> ShowS -> [ShowS] -> ShowS
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
(.) ShowS
forall a. a -> a
id
        ( ((Word, Finite n) -> ShowS) -> [(Word, Finite n)] -> [ShowS]
forall a b. (a -> b) -> [a] -> [b]
map ((String -> ShowS
showString String
" * " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.) (ShowS -> ShowS)
-> ((Word, Finite n) -> ShowS) -> (Word, Finite n) -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Word -> Finite n -> ShowS) -> (Word, Finite n) -> ShowS
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Word -> Finite n -> ShowS
showPower)
        ([(Word, Finite n)] -> [ShowS]) -> [(Word, Finite n)] -> [ShowS]
forall a b. (a -> b) -> a -> b
$ ((Word, Finite n) -> Bool)
-> [(Word, Finite n)] -> [(Word, Finite n)]
forall a. (a -> Bool) -> [a] -> [a]
filter ((Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
/= Word
0) (Word -> Bool)
-> ((Word, Finite n) -> Word) -> (Word, Finite n) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Word, Finite n) -> Word
forall a b. (a, b) -> a
fst)
        ([(Word, Finite n)] -> [(Word, Finite n)])
-> [(Word, Finite n)] -> [(Word, Finite n)]
forall a b. (a -> b) -> a -> b
$ [Word] -> [Finite n] -> [(Word, Finite n)]
forall a b. [a] -> [b] -> [(a, b)]
zip (Vector n Word -> [Word]
forall a (n :: Natural). Unbox a => Vector n a -> [a]
SU.toList Vector n Word
is) ([Finite n]
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) ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString (String
"^" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Word -> String
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" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Finite n -> String
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 = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly (v (Vector n Word, a) -> MultiPoly v n a)
-> (v (Vector n Word, a) -> v (Vector n Word, a))
-> v (Vector n Word, a)
-> MultiPoly v n a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool)
-> (a -> a -> a) -> v (Vector n Word, a) -> v (Vector n Word, a)
forall (v :: * -> *) t a.
(Vector v (t, a), Ord t) =>
(a -> Bool) -> (a -> a -> a) -> v (t, a) -> v (t, a)
normalize (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
0) a -> a -> a
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' = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly (v (Vector n Word, a) -> MultiPoly v n a)
-> (v (Vector n Word, a) -> v (Vector n Word, a))
-> v (Vector n Word, a)
-> MultiPoly v n a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool)
-> (a -> a -> a) -> v (Vector n Word, a) -> v (Vector n Word, a)
forall (v :: * -> *) t a.
(Vector v (t, a), Ord t) =>
(a -> Bool) -> (a -> a -> a) -> v (t, a) -> v (t, a)
normalize (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
forall a. Semiring a => a
zero) a -> a -> a
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
(+) = (v (Vector n Word, a)
 -> v (Vector n Word, a) -> v (Vector n Word, a))
-> MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
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 (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
0) a -> a -> a
forall a. Num a => a -> a -> a
(+))
  (-) = (v (Vector n Word, a)
 -> v (Vector n Word, a) -> v (Vector n Word, a))
-> MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
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 (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
0) a -> a
forall a. Num a => a -> a
negate (-))
  * :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
(*) = (v (Vector n Word, a)
 -> v (Vector n Word, a) -> v (Vector n Word, a))
-> MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
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 (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
0) a -> a -> a
forall a. Num a => a -> a -> 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) = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly (v (Vector n Word, a) -> MultiPoly v n a)
-> v (Vector n Word, a) -> MultiPoly v n a
forall a b. (a -> b) -> a -> b
$ ((Vector n Word, a) -> (Vector n Word, a))
-> v (Vector n Word, a) -> v (Vector n Word, a)
forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
G.map ((a -> a) -> (Vector n Word, a) -> (Vector n Word, a)
forall a b. (a -> b) -> (Vector n Word, a) -> (Vector n Word, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> a
forall a. Num a => a -> a
negate) v (Vector n Word, a)
xs
  abs :: MultiPoly v n a -> MultiPoly v n a
abs = MultiPoly v n a -> MultiPoly v n a
forall a. a -> a
id
  signum :: MultiPoly v n a -> MultiPoly v n a
signum = MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
forall a b. a -> b -> a
const MultiPoly v n a
1
  fromInteger :: Integer -> MultiPoly v n a
fromInteger Integer
n = case Integer -> a
forall a. Num a => Integer -> a
fromInteger Integer
n of
    a
0 -> v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly v (Vector n Word, a)
forall (v :: * -> *) a. Vector v a => v a
G.empty
    a
m -> v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly (v (Vector n Word, a) -> MultiPoly v n a)
-> v (Vector n Word, a) -> MultiPoly v n a
forall a b. (a -> b) -> a -> b
$ (Vector n Word, a) -> v (Vector n Word, a)
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 = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly v (Vector n Word, a)
forall (v :: * -> *) a. Vector v a => v a
G.empty
  one :: MultiPoly v n a
one
    | (a
forall a. Semiring a => a
one :: a) a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
forall a. Semiring a => a
zero = MultiPoly v n a
forall a. Semiring a => a
zero
    | Bool
otherwise = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly (v (Vector n Word, a) -> MultiPoly v n a)
-> v (Vector n Word, a) -> MultiPoly v n a
forall a b. (a -> b) -> a -> b
$ (Vector n Word, a) -> v (Vector n Word, a)
forall (v :: * -> *) a. Vector v a => a -> v a
G.singleton (Vector n Word
0, a
forall a. Semiring a => a
one)

  plus :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
plus  = (v (Vector n Word, a)
 -> v (Vector n Word, a) -> v (Vector n Word, a))
-> MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
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 (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
forall a. Semiring a => a
zero) a -> a -> a
forall a. Semiring a => a -> a -> a
plus)
  times :: MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
times = (v (Vector n Word, a)
 -> v (Vector n Word, a) -> v (Vector n Word, a))
-> MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
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 (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
forall a. Semiring a => a
zero) a -> a -> a
forall a. Semiring a => a -> a -> a
plus a -> a -> a
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' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
forall a. Semiring a => a
zero then MultiPoly v n a
forall a. Semiring a => a
zero else v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly (v (Vector n Word, a) -> MultiPoly v n a)
-> v (Vector n Word, a) -> MultiPoly v n a
forall a b. (a -> b) -> a -> b
$ (Vector n Word, a) -> v (Vector n Word, a)
forall (v :: * -> *) a. Vector v a => a -> v a
G.singleton (Vector n Word
0, a
n')
    where
      n' :: a
      n' :: a
n' = Natural -> a
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) = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly (v (Vector n Word, a) -> MultiPoly v n a)
-> v (Vector n Word, a) -> MultiPoly v n a
forall a b. (a -> b) -> a -> b
$ ((Vector n Word, a) -> (Vector n Word, a))
-> v (Vector n Word, a) -> v (Vector n Word, a)
forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
G.map ((a -> a) -> (Vector n Word, a) -> (Vector n Word, a)
forall a b. (a -> b) -> (Vector n Word, a) -> (Vector n Word, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> a
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)
  | v (Vector 1 Word, a) -> Bool
forall (v :: * -> *) a. Vector v a => v a -> Bool
G.null v (Vector 1 Word, a)
v  = Maybe (Word, a)
forall a. Maybe a
Nothing
  | Bool
otherwise = (Word, a) -> Maybe (Word, a)
forall a. a -> Maybe a
Just ((Word, a) -> Maybe (Word, a)) -> (Word, a) -> Maybe (Word, a)
forall a b. (a -> b) -> a -> b
$ (Vector 1 Word -> Word) -> (Vector 1 Word, a) -> (Word, a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first Vector 1 Word -> Word
Vector (1 + 0) Word -> Word
forall (n :: Natural) a. Unbox a => Vector (1 + n) a -> a
SU.head ((Vector 1 Word, a) -> (Word, a))
-> (Vector 1 Word, a) -> (Word, a)
forall a b. (a -> b) -> a -> b
$ v (Vector 1 Word, a) -> (Vector 1 Word, a)
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 = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly (v (Vector n Word, a) -> MultiPoly v n a)
-> (MultiPoly v n a -> v (Vector n Word, a))
-> MultiPoly v n a
-> MultiPoly v n a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool)
-> (a -> a -> a)
-> Vector n Word
-> a
-> v (Vector n Word, a)
-> v (Vector n Word, a)
forall (v :: * -> *) t a.
(Vector v (t, a), Num t) =>
(a -> Bool) -> (a -> a -> a) -> t -> a -> v (t, a) -> v (t, a)
scaleInternal (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
0) a -> a -> a
forall a. Num a => a -> a -> a
(*) Vector n Word
yp a
yc (v (Vector n Word, a) -> v (Vector n Word, a))
-> (MultiPoly v n a -> v (Vector n Word, a))
-> MultiPoly v n a
-> v (Vector n Word, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MultiPoly v n a -> v (Vector n Word, a)
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 = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly (v (Vector n Word, a) -> MultiPoly v n a)
-> (MultiPoly v n a -> v (Vector n Word, a))
-> MultiPoly v n a
-> MultiPoly v n a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool)
-> (a -> a -> a)
-> Vector n Word
-> a
-> v (Vector n Word, a)
-> v (Vector n Word, a)
forall (v :: * -> *) t a.
(Vector v (t, a), Num t) =>
(a -> Bool) -> (a -> a -> a) -> t -> a -> v (t, a) -> v (t, a)
scaleInternal (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
forall a. Semiring a => a
zero) a -> a -> a
forall a. Semiring a => a -> a -> a
times Vector n Word
yp a
yc (v (Vector n Word, a) -> v (Vector n Word, a))
-> (MultiPoly v n a -> v (Vector n Word, a))
-> MultiPoly v n a
-> v (Vector n Word, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MultiPoly v n a -> v (Vector n Word, a)
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 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0    = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly v (Vector n Word, a)
forall (v :: * -> *) a. Vector v a => v a
G.empty
  | Bool
otherwise = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly (v (Vector n Word, a) -> MultiPoly v n a)
-> v (Vector n Word, a) -> MultiPoly v n a
forall a b. (a -> b) -> a -> b
$ (Vector n Word, a) -> v (Vector n Word, a)
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 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
forall a. Semiring a => a
zero = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly v (Vector n Word, a)
forall (v :: * -> *) a. Vector v a => v a
G.empty
  | Bool
otherwise = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly (v (Vector n Word, a) -> MultiPoly v n a)
-> v (Vector n Word, a) -> MultiPoly v n a
forall a b. (a -> b) -> a -> b
$ (Vector n Word, a) -> v (Vector n Word, a)
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 = (a -> a -> a) -> MultiPoly v n a -> Vector u n a -> a
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 -> a -> a
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' = (a -> a -> a) -> MultiPoly v n a -> Vector u n a -> a
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 -> a -> a
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 = (a -> MultiPoly w m a -> MultiPoly w m a)
-> MultiPoly v n a
-> Vector Vector n (MultiPoly w m a)
-> MultiPoly w m a
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 (Vector m Word -> a -> MultiPoly w m a -> MultiPoly w m a
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' = (a -> MultiPoly w m a -> MultiPoly w m a)
-> MultiPoly v n a
-> Vector Vector n (MultiPoly w m a)
-> MultiPoly w m a
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' (Vector m Word -> a -> MultiPoly w m a -> MultiPoly w m a
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 = (b -> (Vector n Word, a) -> b) -> b -> v (Vector n Word, a) -> b
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 b -> b -> b
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 = (b -> Finite n -> Word -> b) -> b -> Vector n Word -> b
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 b -> b -> b
forall a. Num a => a -> a -> a
* ((Vector u n b
xs Vector u n b -> Finite n -> b
forall (v :: * -> *) (n :: Natural) a.
Vector v a =>
Vector v n a -> Finite n -> a
`SG.index` Finite n
i) b -> Word -> b
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 = (b -> (Vector n Word, a) -> b) -> b -> v (Vector n Word, a) -> b
forall (v :: * -> *) b a.
Vector v b =>
(a -> b -> a) -> a -> v b -> a
G.foldl' b -> (Vector n Word, a) -> b
go b
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 b -> b -> b
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 = (b -> Finite n -> Word -> b) -> b -> Vector n Word -> b
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 b -> b -> b
forall a. Semiring a => a -> a -> a
`times` ((Vector u n b
xs Vector u n b -> Finite n -> b
forall (v :: * -> *) (n :: Natural) a.
Vector v a =>
Vector v n a -> Finite n -> a
`SG.index` Finite n
i) b -> Word -> b
forall a b. (Semiring a, Integral b) => a -> b -> a
Semiring.^ Word
p)) b
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) = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly (v (Vector n Word, a) -> MultiPoly v n a)
-> v (Vector n Word, a) -> MultiPoly v n a
forall a b. (a -> b) -> a -> b
$ (a -> Bool)
-> (Vector n Word -> Vector n Word)
-> (Vector n Word -> a -> a)
-> v (Vector n Word, a)
-> v (Vector n Word, a)
forall (v :: * -> *) t a.
Vector v (t, a) =>
(a -> Bool) -> (t -> t) -> (t -> a -> a) -> v (t, a) -> v (t, a)
derivPoly
  (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
0)
  (\Vector n Word
ps -> Vector n Word
ps Vector n Word -> [(Finite n, Word)] -> Vector n Word
forall a (m :: Natural).
Unbox a =>
Vector m a -> [(Finite m, a)] -> Vector m a
SU.// [(Finite n
i, Vector n Word
ps Vector n Word -> Finite n -> Word
forall (n :: Natural) a. Unbox a => Vector n a -> Finite n -> a
`SU.index` Finite n
i Word -> Word -> Word
forall a. Num a => a -> a -> a
- Word
1)])
  (\Vector n Word
ps a
c -> Word -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector n Word
ps Vector n Word -> Finite n -> Word
forall (n :: Natural) a. Unbox a => Vector n a -> Finite n -> a
`SU.index` Finite n
i) a -> a -> a
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) = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly (v (Vector n Word, a) -> MultiPoly v n a)
-> v (Vector n Word, a) -> MultiPoly v n a
forall a b. (a -> b) -> a -> b
$ (a -> Bool)
-> (Vector n Word -> Vector n Word)
-> (Vector n Word -> a -> a)
-> v (Vector n Word, a)
-> v (Vector n Word, a)
forall (v :: * -> *) t a.
Vector v (t, a) =>
(a -> Bool) -> (t -> t) -> (t -> a -> a) -> v (t, a) -> v (t, a)
derivPoly
  (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
forall a. Semiring a => a
zero)
  (\Vector n Word
ps -> Vector n Word
ps Vector n Word -> [(Finite n, Word)] -> Vector n Word
forall a (m :: Natural).
Unbox a =>
Vector m a -> [(Finite m, a)] -> Vector m a
SU.// [(Finite n
i, Vector n Word
ps Vector n Word -> Finite n -> Word
forall (n :: Natural) a. Unbox a => Vector n a -> Finite n -> a
`SU.index` Finite n
i Word -> Word -> Word
forall a. Num a => a -> a -> a
- Word
1)])
  (\Vector n Word
ps a
c -> Natural -> a
forall a. Semiring a => Natural -> a
fromNatural (Word -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector n Word
ps Vector n Word -> Finite n -> Word
forall (n :: Natural) a. Unbox a => Vector n a -> Finite n -> a
`SU.index` Finite n
i)) a -> a -> a
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)
  = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly
  (v (Vector n Word, a) -> MultiPoly v n a)
-> v (Vector n Word, a) -> MultiPoly v n a
forall a b. (a -> b) -> a -> b
$ ((Vector n Word, a) -> (Vector n Word, a))
-> v (Vector n Word, a) -> v (Vector n Word, a)
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 Vector n Word -> Finite n -> Word
forall (n :: Natural) a. Unbox a => Vector n a -> Finite n -> a
`SU.index` Finite n
i in
    (Vector n Word
ps Vector n Word -> [(Finite n, Word)] -> Vector n Word
forall a (m :: Natural).
Unbox a =>
Vector m a -> [(Finite m, a)] -> Vector m a
SU.// [(Finite n
i, Word
p Word -> Word -> Word
forall a. Num a => a -> a -> a
+ Word
1)], a
c a -> a -> a
forall a. Fractional a => a -> a -> a
/ Word -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word
p Word -> Word -> Word
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)
  = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly
  (v (Vector n Word, a) -> MultiPoly v n a)
-> v (Vector n Word, a) -> MultiPoly v n a
forall a b. (a -> b) -> a -> b
$ ((Vector n Word, a) -> (Vector n Word, a))
-> v (Vector n Word, a) -> v (Vector n Word, a)
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 Vector n Word -> Finite n -> Word
forall (n :: Natural) a. Unbox a => Vector n a -> Finite n -> a
`SU.index` Finite n
i in
    (Vector n Word
ps Vector n Word -> [(Finite n, Word)] -> Vector n Word
forall a (m :: Natural).
Unbox a =>
Vector m a -> [(Finite m, a)] -> Vector m a
SU.// [(Finite n
i, Word
p Word -> Word -> Word
forall a. Num a => a -> a -> a
+ Word
1)], a
c a -> a -> a
forall a. Euclidean a => a -> a -> a
`quot` Word -> a
forall a b. (Integral a, Ring b) => a -> b
Semiring.fromIntegral (Word
p Word -> Word -> Word
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 $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
$bX :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Num a, KnownNat n, 1 <= n, Vector v (Vector n Word, a)) =>
MultiPoly v n a
X <- (isVar 0 -> True)
  where X = Finite n -> MultiPoly v n a
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 $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
$bX' :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Semiring a, KnownNat n, 1 <= n,
 Vector v (Vector n Word, a)) =>
MultiPoly v n a
X' <- (isVar' 0 -> True)
  where X' = Finite n -> MultiPoly v n a
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 $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
$bY :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Num a, KnownNat n, 2 <= n, Vector v (Vector n Word, a)) =>
MultiPoly v n a
Y <- (isVar 1 -> True)
  where Y = Finite n -> MultiPoly v n a
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 $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
$bY' :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Semiring a, KnownNat n, 2 <= n,
 Vector v (Vector n Word, a)) =>
MultiPoly v n a
Y' <- (isVar' 1 -> True)
  where Y' = Finite n -> MultiPoly v n a
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 $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
$bZ :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Num a, KnownNat n, 3 <= n, Vector v (Vector n Word, a)) =>
MultiPoly v n a
Z <- (isVar 2 -> True)
  where Z = Finite n -> MultiPoly v n a
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 $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
$bZ' :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Semiring a, KnownNat n, 3 <= n,
 Vector v (Vector n Word, a)) =>
MultiPoly v n a
Z' <- (isVar' 2 -> True)
  where Z' = Finite n -> MultiPoly v n a
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) a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0 = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly v (Vector n Word, a)
forall (v :: * -> *) a. Vector v a => v a
G.empty
  | Bool
otherwise     = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly (v (Vector n Word, a) -> MultiPoly v n a)
-> v (Vector n Word, a) -> MultiPoly v n a
forall a b. (a -> b) -> a -> b
$ (Vector n Word, a) -> v (Vector n Word, a)
forall (v :: * -> *) a. Vector v a => a -> v a
G.singleton
    ((Finite n -> Word) -> Vector n Word
forall (n :: Natural) a.
(KnownNat n, Unbox a) =>
(Finite n -> a) -> Vector n a
SU.generate (\Finite n
j -> if Finite n
i Finite n -> Finite n -> Bool
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
  | (a
forall a. Semiring a => a
one :: a) a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
forall a. Semiring a => a
zero = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly v (Vector n Word, a)
forall (v :: * -> *) a. Vector v a => v a
G.empty
  | Bool
otherwise          = v (Vector n Word, a) -> MultiPoly v n a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly (v (Vector n Word, a) -> MultiPoly v n a)
-> v (Vector n Word, a) -> MultiPoly v n a
forall a b. (a -> b) -> a -> b
$ (Vector n Word, a) -> v (Vector n Word, a)
forall (v :: * -> *) a. Vector v a => a -> v a
G.singleton
    ((Finite n -> Word) -> Vector n Word
forall (n :: Natural) a.
(KnownNat n, Unbox a) =>
(Finite n -> a) -> Vector n a
SU.generate (\Finite n
j -> if Finite n
i Finite n -> Finite n -> Bool
forall a. Eq a => a -> a -> Bool
== Finite n
j then Word
1 else Word
0), a
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) a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0 = v (Vector n Word, a) -> Bool
forall (v :: * -> *) a. Vector v a => v a -> Bool
G.null v (Vector n Word, a)
xs
  | Bool
otherwise     = v (Vector n Word, a) -> Int
forall (v :: * -> *) a. Vector v a => v a -> Int
G.length v (Vector n Word, a)
xs Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 Bool -> Bool -> Bool
&& v (Vector n Word, a) -> (Vector n Word, a)
forall (v :: * -> *) a. Vector v a => v a -> a
G.unsafeHead v (Vector n Word, a)
xs (Vector n Word, a) -> (Vector n Word, a) -> Bool
forall a. Eq a => a -> a -> Bool
== ((Finite n -> Word) -> Vector n Word
forall (n :: Natural) a.
(KnownNat n, Unbox a) =>
(Finite n -> a) -> Vector n a
SU.generate (\Finite n
j -> if Finite n
i Finite n -> Finite n -> Bool
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)
  | (a
forall a. Semiring a => a
one :: a) a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
forall a. Semiring a => a
zero = v (Vector n Word, a) -> Bool
forall (v :: * -> *) a. Vector v a => v a -> Bool
G.null v (Vector n Word, a)
xs
  | Bool
otherwise          = v (Vector n Word, a) -> Int
forall (v :: * -> *) a. Vector v a => v a -> Int
G.length v (Vector n Word, a)
xs Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 Bool -> Bool -> Bool
&& v (Vector n Word, a) -> (Vector n Word, a)
forall (v :: * -> *) a. Vector v a => v a -> a
G.unsafeHead v (Vector n Word, a)
xs (Vector n Word, a) -> (Vector n Word, a) -> Bool
forall a. Eq a => a -> a -> Bool
== ((Finite n -> Word) -> Vector n Word
forall (n :: Natural) a.
(KnownNat n, Unbox a) =>
(Finite n -> a) -> Vector n a
SU.generate (\Finite n
j -> if Finite n
i Finite n -> Finite n -> Bool
forall a. Eq a => a -> a -> Bool
== Finite n
j then Word
1 else Word
0), a
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
      | v a -> Bool
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  -> Int -> v a -> v a
forall (v :: * -> *) a. Vector v a => Int -> v a -> v a
G.unsafeTake (Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) v a
xs v a -> [v a] -> [v a]
forall a. a -> [a] -> [a]
: v a -> [v a]
go (Int -> v a -> v a
forall (v :: * -> *) a. Vector v a => Int -> v a -> v a
G.unsafeDrop (Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) v a
xs)
        where
          fy :: b
fy = a -> b
f (v a -> a
forall (v :: * -> *) a. Vector v a => v a -> a
G.unsafeHead v a
xs)
          mk :: Maybe Int
mk = (a -> Bool) -> v a -> Maybe Int
forall (v :: * -> *) a.
Vector v a =>
(a -> Bool) -> v a -> Maybe Int
G.findIndex ((b -> b -> Bool
forall a. Eq a => a -> a -> Bool
/= b
fy) (b -> Bool) -> (a -> b) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
f) (v a -> v a
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
  = Vector (Vector 1 Word, MultiPoly v m a) -> VPoly (MultiPoly v m a)
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly
  (Vector (Vector 1 Word, MultiPoly v m a)
 -> VPoly (MultiPoly v m a))
-> (MultiPoly v (1 + m) a
    -> Vector (Vector 1 Word, MultiPoly v m a))
-> MultiPoly v (1 + m) a
-> VPoly (MultiPoly v m a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Vector 1 Word, MultiPoly v m a)]
-> Vector (Vector 1 Word, MultiPoly v m a)
forall (v :: * -> *) a. Vector v a => [a] -> v a
G.fromList
  ([(Vector 1 Word, MultiPoly v m a)]
 -> Vector (Vector 1 Word, MultiPoly v m a))
-> (MultiPoly v (1 + m) a -> [(Vector 1 Word, MultiPoly v m a)])
-> MultiPoly v (1 + m) a
-> Vector (Vector 1 Word, MultiPoly v m a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (v (Vector (1 + m) Word, a) -> (Vector 1 Word, MultiPoly v m a))
-> [v (Vector (1 + m) Word, a)]
-> [(Vector 1 Word, MultiPoly v m a)]
forall a b. (a -> b) -> [a] -> [b]
map (\v (Vector (1 + m) Word, a)
vs -> (Vector (1 + m) Word -> Vector 1 Word
forall (n :: Natural) (m :: Natural) a.
(KnownNat n, Unbox a) =>
Vector (n + m) a -> Vector n a
SU.take ((Vector (1 + m) Word, a) -> Vector (1 + m) Word
forall a b. (a, b) -> a
fst (v (Vector (1 + m) Word, a) -> (Vector (1 + m) Word, a)
forall (v :: * -> *) a. Vector v a => v a -> a
G.unsafeHead v (Vector (1 + m) Word, a)
vs)), v (Vector m Word, a) -> MultiPoly v m a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly (v (Vector m Word, a) -> MultiPoly v m a)
-> v (Vector m Word, a) -> MultiPoly v m a
forall a b. (a -> b) -> a -> b
$ ((Vector (1 + m) Word, a) -> (Vector m Word, a))
-> v (Vector (1 + m) Word, a) -> v (Vector m Word, a)
forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
G.map ((Vector (1 + m) Word -> Vector m Word)
-> (Vector (1 + m) Word, a) -> (Vector m Word, a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first Vector (1 + m) Word -> Vector m Word
forall (n :: Natural) a. Unbox a => Vector (1 + n) a -> Vector n a
SU.tail) v (Vector (1 + m) Word, a)
vs))
  ([v (Vector (1 + m) Word, a)]
 -> [(Vector 1 Word, MultiPoly v m a)])
-> (MultiPoly v (1 + m) a -> [v (Vector (1 + m) Word, a)])
-> MultiPoly v (1 + m) a
-> [(Vector 1 Word, MultiPoly v m a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Vector (1 + m) Word, a) -> Word)
-> v (Vector (1 + m) Word, a) -> [v (Vector (1 + m) Word, a)]
forall (v :: * -> *) a b.
(Vector v a, Eq b) =>
(a -> b) -> v a -> [v a]
groupOn (Vector (1 + m) Word -> Word
forall (n :: Natural) a. Unbox a => Vector (1 + n) a -> a
SU.head (Vector (1 + m) Word -> Word)
-> ((Vector (1 + m) Word, a) -> Vector (1 + m) Word)
-> (Vector (1 + m) Word, a)
-> Word
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Vector (1 + m) Word, a) -> Vector (1 + m) Word
forall a b. (a, b) -> a
fst)
  (v (Vector (1 + m) Word, a) -> [v (Vector (1 + m) Word, a)])
-> (MultiPoly v (1 + m) a -> v (Vector (1 + m) Word, a))
-> MultiPoly v (1 + m) a
-> [v (Vector (1 + m) Word, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MultiPoly v (1 + m) a -> v (Vector (1 + m) Word, a)
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
  = v (Vector (1 + m) Word, a) -> MultiPoly v (1 + m) a
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly
  (v (Vector (1 + m) Word, a) -> MultiPoly v (1 + m) a)
-> (VPoly (MultiPoly v m a) -> v (Vector (1 + m) Word, a))
-> VPoly (MultiPoly v m a)
-> MultiPoly v (1 + m) a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [v (Vector (1 + m) Word, a)] -> v (Vector (1 + m) Word, a)
forall (v :: * -> *) a. Vector v a => [v a] -> v a
G.concat
  ([v (Vector (1 + m) Word, a)] -> v (Vector (1 + m) Word, a))
-> (VPoly (MultiPoly v m a) -> [v (Vector (1 + m) Word, a)])
-> VPoly (MultiPoly v m a)
-> v (Vector (1 + m) Word, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vector (v (Vector (1 + m) Word, a)) -> [v (Vector (1 + m) Word, a)]
forall (v :: * -> *) a. Vector v a => v a -> [a]
G.toList
  (Vector (v (Vector (1 + m) Word, a))
 -> [v (Vector (1 + m) Word, a)])
-> (VPoly (MultiPoly v m a) -> Vector (v (Vector (1 + m) Word, a)))
-> VPoly (MultiPoly v m a)
-> [v (Vector (1 + m) Word, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Vector 1 Word, MultiPoly v m a) -> v (Vector (1 + m) Word, a))
-> Vector (Vector 1 Word, MultiPoly v m a)
-> Vector (v (Vector (1 + m) Word, a))
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) -> ((Vector m Word, a) -> (Vector (1 + m) Word, a))
-> v (Vector m Word, a) -> v (Vector (1 + m) Word, a)
forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
G.map ((Vector m Word -> Vector (1 + m) Word)
-> (Vector m Word, a) -> (Vector (1 + m) Word, a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first (Vector 1 Word
v Vector 1 Word -> Vector m Word -> Vector (1 + m) Word
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)
  (Vector (Vector 1 Word, MultiPoly v m a)
 -> Vector (v (Vector (1 + m) Word, a)))
-> (VPoly (MultiPoly v m a)
    -> Vector (Vector 1 Word, MultiPoly v m a))
-> VPoly (MultiPoly v m a)
-> Vector (v (Vector (1 + m) Word, a))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. VPoly (MultiPoly v m a) -> Vector (Vector 1 Word, MultiPoly v m a)
forall (v :: * -> *) (n :: Natural) a.
MultiPoly v n a -> v (Vector n Word, a)
unMultiPoly