-- |
-- Module:      Data.Poly.Internal.Multi.Laurent
-- Copyright:   (c) 2020 Andrew Lelechenko
-- Licence:     BSD3
-- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
--
-- Sparse multivariate
-- <https://en.wikipedia.org/wiki/Laurent_polynomial Laurent polynomials>.
--

{-# LANGUAGE CPP                        #-}
{-# LANGUAGE DataKinds                  #-}
{-# LANGUAGE FlexibleContexts           #-}
{-# LANGUAGE FlexibleInstances          #-}
{-# LANGUAGE LambdaCase                 #-}
{-# LANGUAGE PatternSynonyms            #-}
{-# LANGUAGE QuantifiedConstraints      #-}
{-# LANGUAGE ScopedTypeVariables        #-}
{-# LANGUAGE StandaloneDeriving         #-}
{-# LANGUAGE TypeFamilies               #-}
{-# LANGUAGE TypeOperators              #-}
{-# LANGUAGE UndecidableInstances       #-}
{-# LANGUAGE ViewPatterns               #-}

module Data.Poly.Internal.Multi.Laurent
  ( MultiLaurent
  , VMultiLaurent
  , UMultiLaurent
  , unMultiLaurent
  , toMultiLaurent
  , leading
  , monomial
  , scale
  , pattern X
  , pattern Y
  , pattern Z
  , (^-)
  , eval
  , subst
  , deriv
  -- * Univariate polynomials
  , Laurent
  , VLaurent
  , ULaurent
  , unLaurent
  , toLaurent
  -- * Conversions
  , segregate
  , unsegregate
  ) where

import Prelude hiding (quotRem, quot, rem, gcd, lcm)
import Control.Arrow (first)
import Control.DeepSeq (NFData(..))
import Control.Exception
import Data.Euclidean (GcdDomain(..), Euclidean(..), Field)
import Data.Finite
import Data.Kind
import Data.List (intersperse, foldl1')
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.Sized as SV
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Sized as SU
import GHC.Exts
import GHC.TypeNats (KnownNat, Nat, type (+), type (<=))

import Data.Poly.Internal.Multi.Core (derivPoly)
import Data.Poly.Internal.Multi (Poly, MultiPoly(..))
import qualified Data.Poly.Internal.Multi as Multi
import Data.Poly.Internal.Multi.Field ()
import Data.Poly.Internal.Multi.GcdDomain ()

-- | Sparse
-- <https://en.wikipedia.org/wiki/Laurent_polynomial Laurent polynomials>
-- of @n@ variables with coefficients from @a@,
-- backed by a 'G.Vector' @v@ (boxed, unboxed, storable, etc.).
--
-- Use the patterns 'X', 'Y', 'Z' and the '^-' operator for construction:
--
-- >>> (X + 1) + (Y^-1 - 1) :: VMultiLaurent 2 Integer
-- 1 * X + 1 * Y^-1
-- >>> (X + 1) * (Z - X^-1) :: UMultiLaurent 3 Int
-- 1 * X * Z + 1 * Z + (-1) + (-1) * X^-1
--
-- Polynomials are stored normalized, without
-- zero coefficients, so 0 * X + 1 + 0 * 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 `MultiLaurent` 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
data MultiLaurent (v :: Type -> Type) (n :: Nat) (a :: Type) =
  MultiLaurent !(SU.Vector n Int) !(MultiPoly v n a)

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

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

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

-- | <https://en.wikipedia.org/wiki/Laurent_polynomial Laurent polynomials>
-- of one variable with coefficients from @a@,
-- backed by a 'G.Vector' @v@ (boxed, unboxed, storable, etc.).
--
-- Use the pattern 'X' and the '^-' operator for construction:
--
-- >>> (X + 1) + (X^-1 - 1) :: VLaurent Integer
-- 1 * X + 1 * X^-1
-- >>> (X + 1) * (1 - X^-1) :: ULaurent Int
-- 1 * X + (-1) * X^-1
--
-- Polynomials are stored normalized, without
-- zero coefficients, so 0 * X + 1 + 0 * 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 `Laurent` crucially
-- depends on specialisation of instances. Clients are strongly recommended
-- to compile with @ghc-options:@ @-fspecialise-aggressively@ and suggested to enable @-O2@.
--
-- @since 0.4.0.0
type Laurent (v :: Type -> Type) (a :: Type) = MultiLaurent v 1 a

-- | Laurent polynomials backed by boxed vectors.
--
-- @since 0.4.0.0
type VLaurent (a :: Type) = Laurent V.Vector a

-- | Laurent polynomials backed by unboxed vectors.
--
-- @since 0.4.0.0
type ULaurent (a :: Type) = Laurent U.Vector a

instance (Eq a, Semiring a, KnownNat n, G.Vector v (SU.Vector n Int, a), G.Vector v (SU.Vector n Word, a)) => IsList (MultiLaurent v n a) where
  type Item (MultiLaurent v n a) = (SU.Vector n Int, a)

  fromList :: [Item (MultiLaurent v n a)] -> MultiLaurent v n a
fromList [] = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (v :: * -> *) (n :: Natural) a.
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
MultiLaurent Vector n Int
0 MultiPoly v n a
forall a. Semiring a => a
zero
  fromList [Item (MultiLaurent v n a)]
xs = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent Vector n Int
minPow ([Item (MultiPoly v n a)] -> MultiPoly v n a
forall l. IsList l => [Item l] -> l
fromList [(Vector n Word, a)]
[Item (MultiPoly v n a)]
ys)
    where
      minPow :: Vector n Int
minPow = (Vector n Int -> Vector n Int -> Vector n Int)
-> [Vector n Int] -> Vector n Int
forall a. HasCallStack => (a -> a -> a) -> [a] -> a
foldl1' ((Int -> Int -> Int) -> Vector n Int -> Vector n Int -> Vector n Int
forall a b c (n :: Natural).
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector n a -> Vector n b -> Vector n c
SU.zipWith Int -> Int -> Int
forall a. Ord a => a -> a -> a
min) (((Vector n Int, a) -> Vector n Int)
-> [(Vector n Int, a)] -> [Vector n Int]
forall a b. (a -> b) -> [a] -> [b]
map (Vector n Int, a) -> Vector n Int
forall a b. (a, b) -> a
fst [(Vector n Int, a)]
[Item (MultiLaurent v n a)]
xs)
      ys :: [(Vector n Word, a)]
ys = ((Vector n Int, a) -> (Vector n Word, a))
-> [(Vector n Int, a)] -> [(Vector n Word, a)]
forall a b. (a -> b) -> [a] -> [b]
map ((Vector n Int -> Vector n Word)
-> (Vector n Int, a) -> (Vector n 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 ((Int -> Word) -> Vector n Int -> Vector n Word
forall a b (n :: Natural).
(Unbox a, Unbox b) =>
(a -> b) -> Vector n a -> Vector n b
SU.map Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector n Int -> Vector n Word)
-> (Vector n Int -> Vector n Int) -> Vector n Int -> Vector n Word
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vector n Int -> Vector n Int -> Vector n Int
forall a. Num a => a -> a -> a
subtract Vector n Int
minPow)) [(Vector n Int, a)]
[Item (MultiLaurent v n a)]
xs

  toList :: MultiLaurent v n a -> [Item (MultiLaurent v n a)]
toList (MultiLaurent Vector n Int
off (MultiPoly v (Vector n Word, a)
poly)) =
    ((Vector n Word, a) -> Item (MultiLaurent v n a))
-> [(Vector n Word, a)] -> [Item (MultiLaurent v n a)]
forall a b. (a -> b) -> [a] -> [b]
map ((Vector n Word -> Vector n Int)
-> (Vector n Word, a) -> (Vector n Int, 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 n Int -> Vector n Int -> Vector n Int
forall a. Num a => a -> a -> a
+ Vector n Int
off) (Vector n Int -> Vector n Int)
-> (Vector n Word -> Vector n Int) -> Vector n Word -> Vector n Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Word -> Int) -> Vector n Word -> Vector n Int
forall a b (n :: Natural).
(Unbox a, Unbox b) =>
(a -> b) -> Vector n a -> Vector n b
SU.map Word -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral)) ([(Vector n Word, a)] -> [Item (MultiLaurent v n a)])
-> [(Vector n Word, a)] -> [Item (MultiLaurent v n a)]
forall a b. (a -> b) -> a -> b
$ 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)
poly

-- | Deconstruct a 'MultiLaurent' polynomial into an offset (largest possible)
-- and a regular polynomial.
--
-- >>> unMultiLaurent (2 * X + 1 :: UMultiLaurent 2 Int)
-- (Vector [0,0],2 * X + 1)
-- >>> unMultiLaurent (1 + 2 * X^-1 :: UMultiLaurent 2 Int)
-- (Vector [-1,0],1 * X + 2)
-- >>> unMultiLaurent (2 * X^2 + X :: UMultiLaurent 2 Int)
-- (Vector [1,0],2 * X + 1)
-- >>> unMultiLaurent (0 :: UMultiLaurent 2 Int)
-- (Vector [0,0],0)
--
-- @since 0.5.0.0
unMultiLaurent :: MultiLaurent v n a -> (SU.Vector n Int, MultiPoly v n a)
unMultiLaurent :: forall (v :: * -> *) (n :: Natural) a.
MultiLaurent v n a -> (Vector n Int, MultiPoly v n a)
unMultiLaurent (MultiLaurent Vector n Int
off MultiPoly v n a
poly) = (Vector n Int
off, MultiPoly v n a
poly)

-- | Deconstruct a 'Laurent' polynomial into an offset (largest possible)
-- and a regular polynomial.
--
-- >>> unLaurent (2 * X + 1 :: ULaurent Int)
-- (0,2 * X + 1)
-- >>> unLaurent (1 + 2 * X^-1 :: ULaurent Int)
-- (-1,1 * X + 2)
-- >>> unLaurent (2 * X^2 + X :: ULaurent Int)
-- (1,2 * X + 1)
-- >>> unLaurent (0 :: ULaurent Int)
-- (0,0)
--
-- @since 0.4.0.0
unLaurent :: Laurent v a -> (Int, Poly v a)
unLaurent :: forall (v :: * -> *) a. Laurent v a -> (Int, Poly v a)
unLaurent = (Vector 1 Int -> Int)
-> (Vector 1 Int, MultiPoly v 1 a) -> (Int, MultiPoly v 1 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 Int -> Int
Vector (1 + 0) Int -> Int
forall (n :: Natural) a. Unbox a => Vector (1 + n) a -> a
SU.head ((Vector 1 Int, MultiPoly v 1 a) -> (Int, MultiPoly v 1 a))
-> (Laurent v a -> (Vector 1 Int, MultiPoly v 1 a))
-> Laurent v a
-> (Int, MultiPoly v 1 a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Laurent v a -> (Vector 1 Int, MultiPoly v 1 a)
forall (v :: * -> *) (n :: Natural) a.
MultiLaurent v n a -> (Vector n Int, MultiPoly v n a)
unMultiLaurent

-- | Construct a 'MultiLaurent' polynomial from an offset and a regular polynomial.
-- One can imagine it as 'Data.Poly.Multi.Semiring.scale', but allowing negative offsets.
--
-- >>> :set -XDataKinds
-- >>> import Data.Vector.Generic.Sized (fromTuple)
-- >>> toMultiLaurent (fromTuple (2, 0)) (2 * Data.Poly.Multi.X + 1) :: UMultiLaurent 2 Int
-- 2 * X^3 + 1 * X^2
-- >>> toMultiLaurent (fromTuple (0, -2)) (2 * Data.Poly.Multi.X + 1) :: UMultiLaurent 2 Int
-- 2 * X * Y^-2 + 1 * Y^-2
toMultiLaurent
  :: (KnownNat n, G.Vector v (SU.Vector n Word, a))
  => SU.Vector n Int
  -> MultiPoly v n a
  -> MultiLaurent v n a
toMultiLaurent :: forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent Vector n Int
off (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 = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (v :: * -> *) (n :: Natural) a.
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
MultiLaurent Vector n Int
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 = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (v :: * -> *) (n :: Natural) a.
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
MultiLaurent ((Int -> Word -> Int)
-> Vector n Int -> Vector n Word -> Vector n Int
forall a b c (n :: Natural).
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector n a -> Vector n b -> Vector n c
SU.zipWith (\Int
o Word
m -> Int
o Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word
m) Vector n Int
off Vector n Word
minPow) (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)
ys)
    where
      minPow :: Vector n Word
minPow = (Vector n Word -> (Vector n Word, a) -> Vector n Word)
-> Vector n Word -> v (Vector n Word, a) -> Vector n Word
forall (v :: * -> *) b a.
Vector v b =>
(a -> b -> a) -> a -> v b -> a
G.foldl'(\Vector n Word
acc (Vector n Word
x, a
_) -> (Word -> Word -> Word)
-> Vector n Word -> Vector n Word -> Vector n Word
forall a b c (n :: Natural).
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector n a -> Vector n b -> Vector n c
SU.zipWith Word -> Word -> Word
forall a. Ord a => a -> a -> a
min Vector n Word
acc Vector n Word
x) (Word -> Vector n Word
forall (n :: Natural) a. (KnownNat n, Unbox a) => a -> Vector n a
SU.replicate Word
forall a. Bounded a => a
maxBound) v (Vector n Word, a)
xs
      ys :: v (Vector n Word, a)
ys
        | (Word -> Bool) -> Vector n Word -> Bool
forall a (n :: Natural).
Unbox a =>
(a -> Bool) -> Vector n a -> Bool
SU.all (Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
0) Vector n Word
minPow = v (Vector n Word, a)
xs
        | Bool
otherwise = ((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 -> Vector n Word)
-> (Vector n Word, a) -> (Vector n 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 ((Word -> Word -> Word)
-> Vector n Word -> Vector n Word -> Vector n Word
forall a b c (n :: Natural).
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector n a -> Vector n b -> Vector n c
SU.zipWith Word -> Word -> Word
forall a. Num a => a -> a -> a
subtract Vector n Word
minPow)) v (Vector n Word, a)
xs
{-# INLINE toMultiLaurent #-}

-- | Construct a 'Laurent' polynomial from an offset and a regular polynomial.
-- One can imagine it as 'Data.Poly.Sparse.Semiring.scale', but allowing negative offsets.
--
-- >>> toLaurent 2 (2 * Data.Poly.Sparse.X + 1) :: ULaurent Int
-- 2 * X^3 + 1 * X^2
-- >>> toLaurent (-2) (2 * Data.Poly.Sparse.X + 1) :: ULaurent Int
-- 2 * X^-1 + 1 * X^-2
--
-- @since 0.4.0.0
toLaurent
  :: G.Vector v (SU.Vector 1 Word, a)
  => Int
  -> Poly v a
  -> Laurent v a
toLaurent :: forall (v :: * -> *) a.
Vector v (Vector 1 Word, a) =>
Int -> Poly v a -> Laurent v a
toLaurent = Vector 1 Int -> MultiPoly v 1 a -> MultiLaurent v 1 a
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent (Vector 1 Int -> MultiPoly v 1 a -> MultiLaurent v 1 a)
-> (Int -> Vector 1 Int)
-> Int
-> MultiPoly v 1 a
-> MultiLaurent v 1 a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Vector 1 Int
forall a. Unbox a => a -> Vector 1 a
SU.singleton
{-# INLINABLE toLaurent #-}

instance NFData (v (SU.Vector n Word, a)) => NFData (MultiLaurent v n a) where
  rnf :: MultiLaurent v n a -> ()
rnf (MultiLaurent Vector n Int
off MultiPoly v n a
poly) = Vector n Int -> ()
forall a. NFData a => a -> ()
rnf Vector n Int
off () -> () -> ()
forall a b. a -> b -> b
`seq` MultiPoly v n a -> ()
forall a. NFData a => a -> ()
rnf MultiPoly v n a
poly

instance (Show a, KnownNat n, G.Vector v (SU.Vector n Word, a)) => Show (MultiLaurent v n a) where
  showsPrec :: Int -> MultiLaurent v n a -> ShowS
showsPrec Int
d (MultiLaurent Vector n Int
off (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 Int -> a -> ShowS
showCoeff ((Word -> Int) -> Vector n Word -> Vector n Int
forall a b (n :: Natural).
(Unbox a, Unbox b) =>
(a -> b) -> Vector n a -> Vector n b
SU.map Word -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Vector n Word
is Vector n Int -> Vector n Int -> Vector n Int
forall a. Num a => a -> a -> a
+ Vector n Int
off) a
c ShowS -> [ShowS] -> [ShowS]
forall a. a -> [a] -> [a]
: [ShowS]
acc) [] v (Vector n Word, a)
xs
    where
      showCoeff :: Vector n Int -> a -> ShowS
showCoeff Vector n Int
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
        ( ((Int, Finite n) -> ShowS) -> [(Int, 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)
-> ((Int, Finite n) -> ShowS) -> (Int, Finite n) -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Finite n -> ShowS) -> (Int, Finite n) -> ShowS
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Int -> Finite n -> ShowS
showPower)
        ([(Int, Finite n)] -> [ShowS]) -> [(Int, Finite n)] -> [ShowS]
forall a b. (a -> b) -> a -> b
$ ((Int, Finite n) -> Bool) -> [(Int, Finite n)] -> [(Int, Finite n)]
forall a. (a -> Bool) -> [a] -> [a]
filter ((Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
0) (Int -> Bool)
-> ((Int, Finite n) -> Int) -> (Int, Finite n) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, Finite n) -> Int
forall a b. (a, b) -> a
fst)
        ([(Int, Finite n)] -> [(Int, Finite n)])
-> [(Int, Finite n)] -> [(Int, Finite n)]
forall a b. (a -> b) -> a -> b
$ [Int] -> [Finite n] -> [(Int, Finite n)]
forall a b. [a] -> [b] -> [(a, b)]
zip (Vector n Int -> [Int]
forall a (n :: Natural). Unbox a => Vector n a -> [a]
SU.toList Vector n Int
is) ([Finite n]
forall (n :: Natural). KnownNat n => [Finite n]
finites :: [Finite n]))

      -- Negative powers should be displayed without surrounding brackets
      showPower :: Int -> Finite n -> String -> String
      showPower :: Int -> Finite n -> ShowS
showPower Int
1 Finite n
n = String -> ShowS
showString (Finite n -> String
showVar Finite n
n)
      showPower Int
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]
++ Int -> String
forall a. Show a => a -> String
show Int
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

-- | Return the leading power and coefficient of a non-zero polynomial.
--
-- >>> leading ((2 * X + 1) * (2 * X^2 - 1) :: ULaurent Int)
-- Just (3,4)
-- >>> leading (0 :: ULaurent Int)
-- Nothing
--
-- @since 0.4.0.0
leading :: G.Vector v (SU.Vector 1 Word, a) => Laurent v a -> Maybe (Int, a)
leading :: forall (v :: * -> *) a.
Vector v (Vector 1 Word, a) =>
Laurent v a -> Maybe (Int, a)
leading (MultiLaurent Vector 1 Int
off MultiPoly v 1 a
poly) = (Word -> Int) -> (Word, a) -> (Int, 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 ((Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Vector (1 + 0) Int -> Int
forall (n :: Natural) a. Unbox a => Vector (1 + n) a -> a
SU.head Vector 1 Int
Vector (1 + 0) Int
off) (Int -> Int) -> (Word -> Int) -> Word -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral) ((Word, a) -> (Int, a)) -> Maybe (Word, a) -> Maybe (Int, a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MultiPoly v 1 a -> Maybe (Word, a)
forall (v :: * -> *) a.
Vector v (Vector 1 Word, a) =>
Poly v a -> Maybe (Word, a)
Multi.leading MultiPoly v 1 a
poly

-- | Note that 'abs' = 'id' and 'signum' = 'const' 1.
instance (Eq a, Num a, KnownNat n, G.Vector v (SU.Vector n Word, a)) => Num (MultiLaurent v n a) where
  MultiLaurent Vector n Int
off1 MultiPoly v n a
poly1 * :: MultiLaurent v n a -> MultiLaurent v n a -> MultiLaurent v n a
* MultiLaurent Vector n Int
off2 MultiPoly v n a
poly2 = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent (Vector n Int
off1 Vector n Int -> Vector n Int -> Vector n Int
forall a. Num a => a -> a -> a
+ Vector n Int
off2) (MultiPoly v n a
poly1 MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
forall a. Num a => a -> a -> a
* MultiPoly v n a
poly2)
  MultiLaurent Vector n Int
off1 MultiPoly v n a
poly1 + :: MultiLaurent v n a -> MultiLaurent v n a -> MultiLaurent v n a
+ MultiLaurent Vector n Int
off2 MultiPoly v n a
poly2 = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent Vector n Int
off (MultiPoly v n a
poly1' MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
forall a. Num a => a -> a -> a
+ MultiPoly v n a
poly2')
    where
      off :: Vector n Int
off    = (Int -> Int -> Int) -> Vector n Int -> Vector n Int -> Vector n Int
forall a b c (n :: Natural).
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector n a -> Vector n b -> Vector n c
SU.zipWith Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Vector n Int
off1 Vector n Int
off2
      poly1' :: MultiPoly v n a
poly1' = Vector n Word -> a -> MultiPoly v n a -> MultiPoly v n 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
Multi.scale ((Int -> Int -> Word)
-> Vector n Int -> Vector n Int -> Vector n Word
forall a b c (n :: Natural).
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector n a -> Vector n b -> Vector n c
SU.zipWith (\Int
x Int
y -> Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
y)) Vector n Int
off1 Vector n Int
off) a
1 MultiPoly v n a
poly1
      poly2' :: MultiPoly v n a
poly2' = Vector n Word -> a -> MultiPoly v n a -> MultiPoly v n 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
Multi.scale ((Int -> Int -> Word)
-> Vector n Int -> Vector n Int -> Vector n Word
forall a b c (n :: Natural).
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector n a -> Vector n b -> Vector n c
SU.zipWith (\Int
x Int
y -> Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
y)) Vector n Int
off2 Vector n Int
off) a
1 MultiPoly v n a
poly2
  MultiLaurent Vector n Int
off1 MultiPoly v n a
poly1 - :: MultiLaurent v n a -> MultiLaurent v n a -> MultiLaurent v n a
- MultiLaurent Vector n Int
off2 MultiPoly v n a
poly2 = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent Vector n Int
off (MultiPoly v n a
poly1' MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
forall a. Num a => a -> a -> a
- MultiPoly v n a
poly2')
    where
      off :: Vector n Int
off    = (Int -> Int -> Int) -> Vector n Int -> Vector n Int -> Vector n Int
forall a b c (n :: Natural).
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector n a -> Vector n b -> Vector n c
SU.zipWith Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Vector n Int
off1 Vector n Int
off2
      poly1' :: MultiPoly v n a
poly1' = Vector n Word -> a -> MultiPoly v n a -> MultiPoly v n 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
Multi.scale ((Int -> Int -> Word)
-> Vector n Int -> Vector n Int -> Vector n Word
forall a b c (n :: Natural).
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector n a -> Vector n b -> Vector n c
SU.zipWith (\Int
x Int
y -> Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
y)) Vector n Int
off1 Vector n Int
off) a
1 MultiPoly v n a
poly1
      poly2' :: MultiPoly v n a
poly2' = Vector n Word -> a -> MultiPoly v n a -> MultiPoly v n 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
Multi.scale ((Int -> Int -> Word)
-> Vector n Int -> Vector n Int -> Vector n Word
forall a b c (n :: Natural).
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector n a -> Vector n b -> Vector n c
SU.zipWith (\Int
x Int
y -> Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
y)) Vector n Int
off2 Vector n Int
off) a
1 MultiPoly v n a
poly2
  negate :: MultiLaurent v n a -> MultiLaurent v n a
negate (MultiLaurent Vector n Int
off MultiPoly v n a
poly) = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (v :: * -> *) (n :: Natural) a.
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
MultiLaurent Vector n Int
off (MultiPoly v n a -> MultiPoly v n a
forall a. Num a => a -> a
negate MultiPoly v n a
poly)
  abs :: MultiLaurent v n a -> MultiLaurent v n a
abs = MultiLaurent v n a -> MultiLaurent v n a
forall a. a -> a
id
  signum :: MultiLaurent v n a -> MultiLaurent v n a
signum = MultiLaurent v n a -> MultiLaurent v n a -> MultiLaurent v n a
forall a b. a -> b -> a
const MultiLaurent v n a
1
  fromInteger :: Integer -> MultiLaurent v n a
fromInteger Integer
n = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (v :: * -> *) (n :: Natural) a.
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
MultiLaurent Vector n Int
0 (Integer -> MultiPoly v n a
forall a. Num a => Integer -> a
fromInteger Integer
n)
  {-# INLINE (+) #-}
  {-# INLINE (-) #-}
  {-# INLINE negate #-}
  {-# INLINE fromInteger #-}
  {-# INLINE (*) #-}

instance (Eq a, Semiring a, KnownNat n, G.Vector v (SU.Vector n Word, a)) => Semiring (MultiLaurent v n a) where
  zero :: MultiLaurent v n a
zero = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (v :: * -> *) (n :: Natural) a.
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
MultiLaurent Vector n Int
0 MultiPoly v n a
forall a. Semiring a => a
zero
  one :: MultiLaurent v n a
one  = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (v :: * -> *) (n :: Natural) a.
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
MultiLaurent Vector n Int
0 MultiPoly v n a
forall a. Semiring a => a
one
  MultiLaurent Vector n Int
off1 MultiPoly v n a
poly1 times :: MultiLaurent v n a -> MultiLaurent v n a -> MultiLaurent v n a
`times` MultiLaurent Vector n Int
off2 MultiPoly v n a
poly2 =
    Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent (Vector n Int
off1 Vector n Int -> Vector n Int -> Vector n Int
forall a. Num a => a -> a -> a
+ Vector n Int
off2) (MultiPoly v n a
poly1 MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
forall a. Semiring a => a -> a -> a
`times` MultiPoly v n a
poly2)
  MultiLaurent Vector n Int
off1 MultiPoly v n a
poly1 plus :: MultiLaurent v n a -> MultiLaurent v n a -> MultiLaurent v n a
`plus` MultiLaurent Vector n Int
off2 MultiPoly v n a
poly2 = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent Vector n Int
off (MultiPoly v n a
poly1' MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
forall a. Semiring a => a -> a -> a
`plus` MultiPoly v n a
poly2')
    where
      off :: Vector n Int
off    = (Int -> Int -> Int) -> Vector n Int -> Vector n Int -> Vector n Int
forall a b c (n :: Natural).
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector n a -> Vector n b -> Vector n c
SU.zipWith Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Vector n Int
off1 Vector n Int
off2
      poly1' :: MultiPoly v n a
poly1' = Vector n Word -> a -> MultiPoly v n a -> MultiPoly v n 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
Multi.scale' ((Int -> Int -> Word)
-> Vector n Int -> Vector n Int -> Vector n Word
forall a b c (n :: Natural).
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector n a -> Vector n b -> Vector n c
SU.zipWith (\Int
x Int
y -> Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
y)) Vector n Int
off1 Vector n Int
off) a
forall a. Semiring a => a
one MultiPoly v n a
poly1
      poly2' :: MultiPoly v n a
poly2' = Vector n Word -> a -> MultiPoly v n a -> MultiPoly v n 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
Multi.scale' ((Int -> Int -> Word)
-> Vector n Int -> Vector n Int -> Vector n Word
forall a b c (n :: Natural).
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector n a -> Vector n b -> Vector n c
SU.zipWith (\Int
x Int
y -> Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
y)) Vector n Int
off2 Vector n Int
off) a
forall a. Semiring a => a
one MultiPoly v n a
poly2
  fromNatural :: Natural -> MultiLaurent v n a
fromNatural Natural
n = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (v :: * -> *) (n :: Natural) a.
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
MultiLaurent Vector n Int
0 (Natural -> MultiPoly v n a
forall a. Semiring a => Natural -> a
fromNatural Natural
n)
  {-# INLINE zero #-}
  {-# INLINE one #-}
  {-# INLINE plus #-}
  {-# INLINE times #-}
  {-# INLINE fromNatural #-}

instance (Eq a, Ring a, KnownNat n, G.Vector v (SU.Vector n Word, a)) => Ring (MultiLaurent v n a) where
  negate :: MultiLaurent v n a -> MultiLaurent v n a
negate (MultiLaurent Vector n Int
off MultiPoly v n a
poly) = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (v :: * -> *) (n :: Natural) a.
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
MultiLaurent Vector n Int
off (MultiPoly v n a -> MultiPoly v n a
forall a. Ring a => a -> a
Semiring.negate MultiPoly v n a
poly)

-- | Create a monomial from a power and a coefficient.
--
-- @since 0.5.0.0
monomial
  :: (Eq a, Semiring a, KnownNat n, G.Vector v (SU.Vector n Word, a))
  => SU.Vector n Int
  -> a
  -> MultiLaurent v n a
monomial :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> a -> MultiLaurent v n a
monomial Vector n Int
p a
c
  | a
c a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
forall a. Semiring a => a
zero = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (v :: * -> *) (n :: Natural) a.
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
MultiLaurent Vector n Int
0 MultiPoly v n a
forall a. Semiring a => a
zero
  | Bool
otherwise = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (v :: * -> *) (n :: Natural) a.
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
MultiLaurent Vector n Int
p (Vector n Word -> a -> MultiPoly v n a
forall a (v :: * -> *) (n :: Natural).
(Eq a, Semiring a, Vector v (Vector n Word, a)) =>
Vector n Word -> a -> MultiPoly v n a
Multi.monomial' Vector n Word
0 a
c)
{-# INLINE monomial #-}

-- | Multiply a polynomial by a monomial, expressed as a power and a coefficient.
--
-- >>> :set -XDataKinds
-- >>> import Data.Vector.Generic.Sized (fromTuple)
-- >>> scale (fromTuple (1, 1)) 3 (X^-2 + Y) :: UMultiLaurent 2 Int
-- 3 * X * Y^2 + 3 * X^-1 * Y
--
-- @since 0.5.0.0
scale
  :: (Eq a, Semiring a, KnownNat n, G.Vector v (SU.Vector n Word, a))
  => SU.Vector n Int
  -> a
  -> MultiLaurent v n a
  -> MultiLaurent v n a
scale :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> a -> MultiLaurent v n a -> MultiLaurent v n a
scale Vector n Int
yp a
yc (MultiLaurent Vector n Int
off MultiPoly v n a
poly) = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent (Vector n Int
off Vector n Int -> Vector n Int -> Vector n Int
forall a. Num a => a -> a -> a
+ Vector n Int
yp) (Vector n Word -> a -> MultiPoly v n a -> MultiPoly v n 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
Multi.scale' Vector n Word
0 a
yc MultiPoly v n a
poly)

-- | Evaluate the polynomial at a given point.
--
-- >>> :set -XDataKinds
-- >>> import Data.Vector.Generic.Sized (fromTuple)
-- >>> eval (X^2 + Y^-1 :: UMultiLaurent 2 Double) (fromTuple (3, 4) :: Data.Vector.Sized.Vector 2 Double)
-- 9.25
--
-- @since 0.5.0.0
eval
  :: (Field a, G.Vector v (SU.Vector n Word, a), G.Vector u a)
  => MultiLaurent v n a
  -> SG.Vector u n a
  -> a
eval :: forall a (v :: * -> *) (n :: Natural) (u :: * -> *).
(Field a, Vector v (Vector n Word, a), Vector u a) =>
MultiLaurent v n a -> Vector u n a -> a
eval (MultiLaurent Vector n Int
off MultiPoly v n a
poly) Vector u n a
xs = MultiPoly v n a -> Vector u n a -> a
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
Multi.eval' MultiPoly v n a
poly Vector u n a
xs a -> a -> a
forall a. Semiring a => a -> a -> a
`times`
  (a -> Finite n -> Int -> a) -> a -> Vector n Int -> a
forall b a (n :: Natural).
Unbox b =>
(a -> Finite n -> b -> a) -> a -> Vector n b -> a
SU.ifoldl' (\a
acc Finite n
i Int
o -> a
acc a -> a -> a
forall a. Semiring a => a -> a -> a
`times` (let x :: a
x = Vector u n a -> Finite n -> a
forall (v :: * -> *) (n :: Natural) a.
Vector v a =>
Vector v n a -> Finite n -> a
SG.index Vector u n a
xs Finite n
i in if Int
o Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 then a
x a -> Int -> a
forall a b. (Semiring a, Integral b) => a -> b -> a
Semiring.^ Int
o else a -> a -> a
forall a. Euclidean a => a -> a -> a
quot a
forall a. Semiring a => a
one a
x a -> Int -> a
forall a b. (Semiring a, Integral b) => a -> b -> a
Semiring.^ (- Int
o))) a
forall a. Semiring a => a
one Vector n Int
off
{-# INLINE eval #-}

-- | Substitute another polynomial instead of 'Data.Poly.Multi.X'.
--
-- >>> :set -XDataKinds
-- >>> import Data.Vector.Generic.Sized (fromTuple)
-- >>> import Data.Poly.Multi (UMultiPoly)
-- >>> subst (Data.Poly.Multi.X * Data.Poly.Multi.Y :: UMultiPoly 2 Int) (fromTuple (X + Y^-1, Y + X^-1 :: UMultiLaurent 2 Int))
-- 1 * X * Y + 2 + 1 * X^-1 * Y^-1
--
-- @since 0.5.0.0
subst
  :: (Eq a, Semiring a, KnownNat n, G.Vector v (SU.Vector n Word, a), G.Vector w (SU.Vector n Word, a))
  => MultiPoly v n a
  -> SV.Vector n (MultiLaurent w n a)
  -> MultiLaurent w n a
subst :: forall a (n :: Natural) (v :: * -> *) (w :: * -> *).
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a),
 Vector w (Vector n Word, a)) =>
MultiPoly v n a
-> Vector n (MultiLaurent w n a) -> MultiLaurent w n a
subst = (a -> MultiLaurent w n a -> MultiLaurent w n a)
-> MultiPoly v n a
-> Vector Vector n (MultiLaurent w n a)
-> MultiLaurent w n 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
Multi.substitute' (Vector n Int -> a -> MultiLaurent w n a -> MultiLaurent w n a
forall a (n :: Natural) (v :: * -> *).
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> a -> MultiLaurent v n a -> MultiLaurent v n a
scale Vector n Int
0)
{-# INLINE subst #-}

-- | Take the derivative of the polynomial with respect to the /i/-th variable.
--
-- >>> :set -XDataKinds
-- >>> deriv 0 (X^3 + 3 * Y) :: UMultiLaurent 2 Int
-- 3 * X^2
-- >>> deriv 1 (X^3 + 3 * Y) :: UMultiLaurent 2 Int
-- 3
--
-- @since 0.5.0.0
deriv
  :: (Eq a, Ring a, KnownNat n, G.Vector v (SU.Vector n Word, a))
  => Finite n
  -> MultiLaurent v n a
  -> MultiLaurent v n a
deriv :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Ring a, KnownNat n, Vector v (Vector n Word, a)) =>
Finite n -> MultiLaurent v n a -> MultiLaurent v n a
deriv Finite n
i (MultiLaurent Vector n Int
off (MultiPoly v (Vector n Word, a)
xs)) =
  Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent (Vector n Int
off Vector n Int -> [(Finite n, Int)] -> Vector n Int
forall a (m :: Natural).
Unbox a =>
Vector m a -> [(Finite m, a)] -> Vector m a
SU.// [(Finite n
i, Vector n Int
off Vector n Int -> Finite n -> Int
forall (n :: Natural) a. Unbox a => Vector n a -> Finite n -> a
`SU.index` Finite n
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)]) (MultiPoly v n a -> MultiLaurent v n a)
-> MultiPoly v n a -> MultiLaurent v n a
forall a b. (a -> b) -> a -> b
$ 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 -> Vector n Word
forall a. a -> a
id
    (\Vector n Word
ps a
c -> Int -> a
forall a b. (Integral a, Ring b) => a -> b
Semiring.fromIntegral (Word -> Int
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) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Vector n Int
off Vector n Int -> Finite n -> Int
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 #-}

-- | Create a polynomial equal to the first variable.
--
-- @since 0.5.0.0
pattern X
  :: (Eq a, Semiring a, KnownNat n, 1 <= n, G.Vector v (SU.Vector n Word, a))
  => MultiLaurent 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)) =>
MultiLaurent 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)) =>
MultiLaurent v n a
X <- (isVar 0 -> True)
  where X = Finite n -> MultiLaurent v n a
forall (v :: * -> *) (n :: Natural) a.
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) =>
Finite n -> MultiLaurent v n a
var Finite n
0

-- | Create a polynomial equal to the second variable.
--
-- @since 0.5.0.0
pattern Y
  :: (Eq a, Semiring a, KnownNat n, 2 <= n, G.Vector v (SU.Vector n Word, a))
  => MultiLaurent 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)) =>
MultiLaurent 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)) =>
MultiLaurent v n a
Y <- (isVar 1 -> True)
  where Y = Finite n -> MultiLaurent v n a
forall (v :: * -> *) (n :: Natural) a.
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) =>
Finite n -> MultiLaurent v n a
var Finite n
1

-- | Create a polynomial equal to the third variable.
--
-- @since 0.5.0.0
pattern Z
  :: (Eq a, Semiring a, KnownNat n, 3 <= n, G.Vector v (SU.Vector n Word, a))
  => MultiLaurent 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)) =>
MultiLaurent 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)) =>
MultiLaurent v n a
Z <- (isVar 2 -> True)
  where Z = Finite n -> MultiLaurent v n a
forall (v :: * -> *) (n :: Natural) a.
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) =>
Finite n -> MultiLaurent v n a
var Finite n
2

var
  :: forall v n a.
     (Eq a, Semiring a, KnownNat n, G.Vector v (SU.Vector n Word, a))
  => Finite n
  -> MultiLaurent v n a
var :: forall (v :: * -> *) (n :: Natural) a.
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) =>
Finite n -> MultiLaurent 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 = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (v :: * -> *) (n :: Natural) a.
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
MultiLaurent Vector n Int
0 MultiPoly v n a
forall a. Semiring a => a
zero
  | Bool
otherwise          = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (v :: * -> *) (n :: Natural) a.
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
MultiLaurent
      ((Finite n -> Int) -> Vector n Int
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 Int
1 else Int
0)) MultiPoly v n a
forall a. Semiring a => a
one
{-# INLINE var #-}

isVar
  :: forall v n a.
     (Eq a, Semiring a, KnownNat n, G.Vector v (SU.Vector n Word, a))
  => Finite n
  -> MultiLaurent v n a
  -> Bool
isVar :: forall (v :: * -> *) (n :: Natural) a.
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) =>
Finite n -> MultiLaurent v n a -> Bool
isVar Finite n
i (MultiLaurent Vector n Int
off (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
  = Vector n Int
off Vector n Int -> Vector n Int -> Bool
forall a. Eq a => a -> a -> Bool
== Vector n Int
0 Bool -> Bool -> Bool
&& 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
  = Vector n Int
off Vector n Int -> Vector n Int -> Bool
forall a. Eq a => a -> a -> Bool
== (Finite n -> Int) -> Vector n Int
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 Int
1 else Int
0)
  Bool -> Bool -> Bool
&& 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
== (Vector n Word
0, a
forall a. Semiring a => a
one)
{-# INLINE isVar #-}

-- | Used to construct monomials with negative powers.
--
-- This operator can be applied only to monomials with unit coefficients,
-- but is instrumental to express Laurent polynomials
-- in a mathematical fashion:
--
-- >>> X^-3 * Y^-1 :: UMultiLaurent 2 Int
-- 1 * X^-3 * Y^-1
-- >>> 3 * X^-1 + 2 * (Y^2)^-2 :: UMultiLaurent 2 Int
-- 2 * Y^-4 + 3 * X^-1
--
-- @since 0.5.0.0
(^-)
  :: (Eq a, Semiring a, KnownNat n, G.Vector v (SU.Vector n Word, a))
  => MultiLaurent v n a
  -> Int
  -> MultiLaurent v n a
MultiLaurent Vector n Int
off (MultiPoly v (Vector n Word, a)
xs) ^- :: forall a (n :: Natural) (v :: * -> *).
(Eq a, Semiring a, KnownNat n, Vector v (Vector n Word, a)) =>
MultiLaurent v n a -> Int -> MultiLaurent v n a
^- Int
n
  | 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, 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
== (Vector n Word
0, a
forall a. Semiring a => a
one)
  = Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (v :: * -> *) (n :: Natural) a.
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
MultiLaurent ((Int -> Int) -> Vector n Int -> Vector n Int
forall a b (n :: Natural).
(Unbox a, Unbox b) =>
(a -> b) -> Vector n a -> Vector n b
SU.map (Int -> Int -> Int
forall a. Num a => a -> a -> a
* (-Int
n)) Vector n Int
off) (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)
xs)
  | Bool
otherwise
  = PatternMatchFail -> MultiLaurent v n a
forall a e. Exception e => e -> a
throw (PatternMatchFail -> MultiLaurent v n a)
-> PatternMatchFail -> MultiLaurent v n a
forall a b. (a -> b) -> a -> b
$ String -> PatternMatchFail
PatternMatchFail String
"(^-) can be applied only to a monom with unit coefficient"

instance {-# OVERLAPPING #-} (Eq a, Ring a, GcdDomain a, G.Vector v (SU.Vector 1 Word, a)) => GcdDomain (Laurent v a) where
  divide :: Laurent v a -> Laurent v a -> Maybe (Laurent v a)
divide (MultiLaurent Vector 1 Int
off1 MultiPoly v 1 a
poly1) (MultiLaurent Vector 1 Int
off2 MultiPoly v 1 a
poly2) =
    Vector 1 Int -> MultiPoly v 1 a -> Laurent v a
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent (Vector 1 Int
off1 Vector 1 Int -> Vector 1 Int -> Vector 1 Int
forall a. Num a => a -> a -> a
- Vector 1 Int
off2) (MultiPoly v 1 a -> Laurent v a)
-> Maybe (MultiPoly v 1 a) -> Maybe (Laurent v a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MultiPoly v 1 a -> MultiPoly v 1 a -> Maybe (MultiPoly v 1 a)
forall a. GcdDomain a => a -> a -> Maybe a
divide MultiPoly v 1 a
poly1 MultiPoly v 1 a
poly2
  {-# INLINE divide #-}

  gcd :: Laurent v a -> Laurent v a -> Laurent v a
gcd (MultiLaurent Vector 1 Int
_ MultiPoly v 1 a
poly1) (MultiLaurent Vector 1 Int
_ MultiPoly v 1 a
poly2) =
    Vector 1 Int -> MultiPoly v 1 a -> Laurent v a
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent Vector 1 Int
0 (MultiPoly v 1 a -> MultiPoly v 1 a -> MultiPoly v 1 a
forall a. GcdDomain a => a -> a -> a
gcd MultiPoly v 1 a
poly1 MultiPoly v 1 a
poly2)
  {-# INLINE gcd #-}

  lcm :: Laurent v a -> Laurent v a -> Laurent v a
lcm (MultiLaurent Vector 1 Int
_ MultiPoly v 1 a
poly1) (MultiLaurent Vector 1 Int
_ MultiPoly v 1 a
poly2) =
    Vector 1 Int -> MultiPoly v 1 a -> Laurent v a
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent Vector 1 Int
0 (MultiPoly v 1 a -> MultiPoly v 1 a -> MultiPoly v 1 a
forall a. GcdDomain a => a -> a -> a
lcm MultiPoly v 1 a
poly1 MultiPoly v 1 a
poly2)
  {-# INLINE lcm #-}

  coprime :: Laurent v a -> Laurent v a -> Bool
coprime (MultiLaurent Vector 1 Int
_ MultiPoly v 1 a
poly1) (MultiLaurent Vector 1 Int
_ MultiPoly v 1 a
poly2) =
    MultiPoly v 1 a -> MultiPoly v 1 a -> Bool
forall a. GcdDomain a => a -> a -> Bool
coprime MultiPoly v 1 a
poly1 MultiPoly v 1 a
poly2
  {-# INLINE coprime #-}

instance (Eq a, Ring a, GcdDomain a, KnownNat n, forall m. KnownNat m => G.Vector v (SU.Vector m Word, a), forall m. KnownNat m => Eq (v (SU.Vector m Word, a))) => GcdDomain (MultiLaurent v n a) where
  divide :: MultiLaurent v n a
-> MultiLaurent v n a -> Maybe (MultiLaurent v n a)
divide (MultiLaurent Vector n Int
off1 MultiPoly v n a
poly1) (MultiLaurent Vector n Int
off2 MultiPoly v n a
poly2) =
    Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent (Vector n Int
off1 Vector n Int -> Vector n Int -> Vector n Int
forall a. Num a => a -> a -> a
- Vector n Int
off2) (MultiPoly v n a -> MultiLaurent v n a)
-> Maybe (MultiPoly v n a) -> Maybe (MultiLaurent v n a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MultiPoly v n a -> MultiPoly v n a -> Maybe (MultiPoly v n a)
forall a. GcdDomain a => a -> a -> Maybe a
divide MultiPoly v n a
poly1 MultiPoly v n a
poly2
  {-# INLINE divide #-}

  gcd :: MultiLaurent v n a -> MultiLaurent v n a -> MultiLaurent v n a
gcd (MultiLaurent Vector n Int
_ MultiPoly v n a
poly1) (MultiLaurent Vector n Int
_ MultiPoly v n a
poly2) =
    Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent Vector n Int
0 (MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
forall a. GcdDomain a => a -> a -> a
gcd MultiPoly v n a
poly1 MultiPoly v n a
poly2)
  {-# INLINE gcd #-}

  lcm :: MultiLaurent v n a -> MultiLaurent v n a -> MultiLaurent v n a
lcm (MultiLaurent Vector n Int
_ MultiPoly v n a
poly1) (MultiLaurent Vector n Int
_ MultiPoly v n a
poly2) =
    Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent Vector n Int
0 (MultiPoly v n a -> MultiPoly v n a -> MultiPoly v n a
forall a. GcdDomain a => a -> a -> a
lcm MultiPoly v n a
poly1 MultiPoly v n a
poly2)
  {-# INLINE lcm #-}

  coprime :: MultiLaurent v n a -> MultiLaurent v n a -> Bool
coprime (MultiLaurent Vector n Int
_ MultiPoly v n a
poly1) (MultiLaurent Vector n Int
_ MultiPoly v n a
poly2) =
    MultiPoly v n a -> MultiPoly v n a -> Bool
forall a. GcdDomain a => a -> a -> Bool
coprime MultiPoly v n a
poly1 MultiPoly v n a
poly2
  {-# INLINE coprime #-}

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

-- | Interpret a multivariate Laurent polynomial over 1+/m/ variables
-- as a univariate Laurent polynomial, whose coefficients are
-- multivariate Laurent polynomials over the last /m/ variables.
--
-- @since 0.5.0.0
segregate
  :: (KnownNat m, G.Vector v (SU.Vector (1 + m) Word, a), G.Vector v (SU.Vector m Word, a))
  => MultiLaurent v (1 + m) a
  -> VLaurent (MultiLaurent v m a)
segregate :: forall (m :: Natural) (v :: * -> *) a.
(KnownNat m, Vector v (Vector (1 + m) Word, a),
 Vector v (Vector m Word, a)) =>
MultiLaurent v (1 + m) a -> VLaurent (MultiLaurent v m a)
segregate (MultiLaurent Vector (1 + m) Int
off MultiPoly v (1 + m) a
poly)
  = Vector 1 Int
-> MultiPoly Vector 1 (MultiLaurent v m a)
-> MultiLaurent Vector 1 (MultiLaurent v m a)
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent (Vector (1 + m) Int -> Vector 1 Int
forall (n :: Natural) (m :: Natural) a.
(KnownNat n, Unbox a) =>
Vector (n + m) a -> Vector n a
SU.take Vector (1 + m) Int
off)
  (MultiPoly Vector 1 (MultiLaurent v m a)
 -> MultiLaurent Vector 1 (MultiLaurent v m a))
-> MultiPoly Vector 1 (MultiLaurent v m a)
-> MultiLaurent Vector 1 (MultiLaurent v m a)
forall a b. (a -> b) -> a -> b
$ Vector (Vector 1 Word, MultiLaurent v m a)
-> MultiPoly Vector 1 (MultiLaurent v m a)
forall (v :: * -> *) (n :: Natural) a.
v (Vector n Word, a) -> MultiPoly v n a
MultiPoly
  (Vector (Vector 1 Word, MultiLaurent v m a)
 -> MultiPoly Vector 1 (MultiLaurent v m a))
-> Vector (Vector 1 Word, MultiLaurent v m a)
-> MultiPoly Vector 1 (MultiLaurent v m a)
forall a b. (a -> b) -> a -> b
$ ((Vector 1 Word, MultiPoly v m a)
 -> (Vector 1 Word, MultiLaurent v m a))
-> Vector (Vector 1 Word, MultiPoly v m a)
-> Vector (Vector 1 Word, MultiLaurent v m a)
forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
G.map ((MultiPoly v m a -> MultiLaurent v m a)
-> (Vector 1 Word, MultiPoly v m a)
-> (Vector 1 Word, MultiLaurent v m a)
forall a b. (a -> b) -> (Vector 1 Word, a) -> (Vector 1 Word, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Vector m Int -> MultiPoly v m a -> MultiLaurent v m a
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent (Vector (1 + m) Int -> Vector m Int
forall (n :: Natural) a. Unbox a => Vector (1 + n) a -> Vector n a
SU.tail Vector (1 + m) Int
off)))
  (Vector (Vector 1 Word, MultiPoly v m a)
 -> Vector (Vector 1 Word, MultiLaurent v m a))
-> Vector (Vector 1 Word, MultiPoly v m a)
-> Vector (Vector 1 Word, MultiLaurent v m a)
forall a b. (a -> b) -> a -> b
$ MultiPoly Vector 1 (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)
Multi.unMultiPoly
  (MultiPoly Vector 1 (MultiPoly v m a)
 -> Vector (Vector 1 Word, MultiPoly v m a))
-> MultiPoly Vector 1 (MultiPoly v m a)
-> Vector (Vector 1 Word, MultiPoly v m a)
forall a b. (a -> b) -> a -> b
$ MultiPoly v (1 + m) a -> MultiPoly Vector 1 (MultiPoly v m a)
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)
Multi.segregate MultiPoly v (1 + m) a
poly

-- | Interpret a univariate Laurent polynomials, whose coefficients are
-- multivariate Laurent polynomials over the first /m/ variables,
-- as a multivariate polynomial over 1+/m/ variables.
--
-- @since 0.5.0.0
unsegregate
  :: forall v m a.
     (KnownNat m, KnownNat (1 + m), G.Vector v (SU.Vector (1 + m) Word, a), G.Vector v (SU.Vector m Word, a))
  => VLaurent (MultiLaurent v m a)
  -> MultiLaurent v (1 + m) a
unsegregate :: forall (v :: * -> *) (m :: Natural) a.
(KnownNat m, KnownNat (1 + m), Vector v (Vector (1 + m) Word, a),
 Vector v (Vector m Word, a)) =>
VLaurent (MultiLaurent v m a) -> MultiLaurent v (1 + m) a
unsegregate (MultiLaurent Vector 1 Int
off MultiPoly Vector 1 (MultiLaurent v m a)
poly)
  | Vector (Vector 1 Word, MultiLaurent v m a) -> Bool
forall (v :: * -> *) a. Vector v a => v a -> Bool
G.null (MultiPoly Vector 1 (MultiLaurent v m a)
-> Vector (Vector 1 Word, MultiLaurent v m a)
forall (v :: * -> *) (n :: Natural) a.
MultiPoly v n a -> v (Vector n Word, a)
unMultiPoly MultiPoly Vector 1 (MultiLaurent v m a)
poly)
  = Vector (1 + m) Int
-> MultiPoly v (1 + m) a -> MultiLaurent v (1 + m) a
forall (v :: * -> *) (n :: Natural) a.
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
MultiLaurent Vector (1 + m) Int
0 (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)
forall (v :: * -> *) a. Vector v a => v a
G.empty)
  | Bool
otherwise
  = Vector (1 + m) Int
-> MultiPoly v (1 + m) a -> MultiLaurent v (1 + m) a
forall (n :: Natural) (v :: * -> *) a.
(KnownNat n, Vector v (Vector n Word, a)) =>
Vector n Int -> MultiPoly v n a -> MultiLaurent v n a
toMultiLaurent (Vector 1 Int
off Vector 1 Int -> Vector m Int -> Vector (1 + m) Int
forall (n :: Natural) (m :: Natural) a.
Unbox a =>
Vector n a -> Vector m a -> Vector (n + m) a
SU.++ Vector m Int
offs) (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)] -> v (Vector (1 + m) Word, a)
forall (v :: * -> *) a. Vector v a => [v a] -> v a
G.concat (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))
ys)))
  where
    xs :: V.Vector (SU.Vector 1 Word, (SU.Vector m Int, MultiPoly v m a))
    xs :: Vector (Vector 1 Word, (Vector m Int, MultiPoly v m a))
xs = ((Vector 1 Word, MultiLaurent v m a)
 -> (Vector 1 Word, (Vector m Int, MultiPoly v m a)))
-> Vector (Vector 1 Word, MultiLaurent v m a)
-> Vector (Vector 1 Word, (Vector m Int, MultiPoly v m a))
forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
G.map ((MultiLaurent v m a -> (Vector m Int, MultiPoly v m a))
-> (Vector 1 Word, MultiLaurent v m a)
-> (Vector 1 Word, (Vector m Int, MultiPoly v m a))
forall a b. (a -> b) -> (Vector 1 Word, a) -> (Vector 1 Word, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap MultiLaurent v m a -> (Vector m Int, MultiPoly v m a)
forall (v :: * -> *) (n :: Natural) a.
MultiLaurent v n a -> (Vector n Int, MultiPoly v n a)
unMultiLaurent) (Vector (Vector 1 Word, MultiLaurent v m a)
 -> Vector (Vector 1 Word, (Vector m Int, MultiPoly v m a)))
-> Vector (Vector 1 Word, MultiLaurent v m a)
-> Vector (Vector 1 Word, (Vector m Int, MultiPoly v m a))
forall a b. (a -> b) -> a -> b
$ MultiPoly Vector 1 (MultiLaurent v m a)
-> Vector (Vector 1 Word, MultiLaurent v m a)
forall (v :: * -> *) (n :: Natural) a.
MultiPoly v n a -> v (Vector n Word, a)
Multi.unMultiPoly MultiPoly Vector 1 (MultiLaurent v m a)
poly
    offs :: SU.Vector m Int
    offs :: Vector m Int
offs = (Vector m Int
 -> (Vector 1 Word, (Vector m Int, MultiPoly v m a))
 -> Vector m Int)
-> Vector m Int
-> Vector (Vector 1 Word, (Vector m Int, MultiPoly v m a))
-> Vector m Int
forall (v :: * -> *) b a.
Vector v b =>
(a -> b -> a) -> a -> v b -> a
G.foldl' (\Vector m Int
acc (Vector 1 Word
_, (Vector m Int
v, MultiPoly v m a
_)) -> (Int -> Int -> Int) -> Vector m Int -> Vector m Int -> Vector m Int
forall a b c (n :: Natural).
(Unbox a, Unbox b, Unbox c) =>
(a -> b -> c) -> Vector n a -> Vector n b -> Vector n c
SU.zipWith Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Vector m Int
acc Vector m Int
v) (Int -> Vector m Int
forall (n :: Natural) a. (KnownNat n, Unbox a) => a -> Vector n a
SU.replicate Int
forall a. Bounded a => a
maxBound) Vector (Vector 1 Word, (Vector m Int, MultiPoly v m a))
xs
    ys :: V.Vector (v (SU.Vector (1 + m) Word, a))
    ys :: Vector (v (Vector (1 + m) Word, a))
ys = ((Vector 1 Word, (Vector m Int, MultiPoly v m a))
 -> v (Vector (1 + m) Word, a))
-> Vector (Vector 1 Word, (Vector m Int, 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, (Vector m Int
vs, MultiPoly v m a
p)) -> ((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.++) (Vector m Word -> Vector (1 + m) Word)
-> (Vector m Word -> Vector m Word)
-> Vector m Word
-> Vector (1 + m) Word
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Int -> Word -> Word)
-> Vector m Int -> Vector m Int -> Vector m Word -> Vector m Word
forall a b c d (n :: Natural).
(Unbox a, Unbox b, Unbox c, Unbox d) =>
(a -> b -> c -> d)
-> Vector n a -> Vector n b -> Vector n c -> Vector n d
SU.zipWith3 (\Int
a Int
b Word
c -> Word
c Word -> Word -> Word
forall a. Num a => a -> a -> a
+ Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
b Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
a)) Vector m Int
offs Vector m Int
vs)) (MultiPoly v m a -> v (Vector m Word, a)
forall (v :: * -> *) (n :: Natural) a.
MultiPoly v n a -> v (Vector n Word, a)
unMultiPoly MultiPoly v m a
p)) Vector (Vector 1 Word, (Vector m Int, MultiPoly v m a))
xs