{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeFamilies #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}
module Data.Poly.Internal.Dense.GcdDomain
() where
import Prelude hiding (gcd, lcm, (^))
import Control.Exception
import Control.Monad
import Control.Monad.ST
import Data.Euclidean
import Data.Maybe
import Data.Semiring (Semiring(..), Ring(), isZero, minus)
import qualified Data.Vector.Generic as G
import qualified Data.Vector.Generic.Mutable as MG
import Data.Poly.Internal.Dense
instance (Eq a, Ring a, GcdDomain a, G.Vector v a) => GcdDomain (Poly v a) where
divide :: Poly v a -> Poly v a -> Maybe (Poly v a)
divide (Poly v a
xs) (Poly v a
ys) =
forall a (v :: * -> *).
(Eq a, Semiring a, Vector v a) =>
v a -> Poly v a
toPoly' forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a (v :: * -> *).
(Eq a, Ring a, GcdDomain a, Vector v a) =>
v a -> v a -> Maybe (v a)
quotient v a
xs v a
ys
{-# INLINABLE divide #-}
gcd :: Poly v a -> Poly v a -> Poly v a
gcd (Poly v a
xs) (Poly v a
ys)
| forall (v :: * -> *) a. Vector v a => v a -> Bool
G.null v a
xs = forall (v :: * -> *) a. v a -> Poly v a
Poly v a
ys
| forall (v :: * -> *) a. Vector v a => v a -> Bool
G.null v a
ys = forall (v :: * -> *) a. v a -> Poly v a
Poly v a
xs
| forall (v :: * -> *) a. Vector v a => v a -> Int
G.length v a
xs forall a. Eq a => a -> a -> Bool
== Int
1 = forall (v :: * -> *) a. v a -> Poly v a
Poly forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a. Vector v a => a -> v a
G.singleton forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) b a.
Vector v b =>
(a -> b -> a) -> a -> v b -> a
G.foldl' forall a. GcdDomain a => a -> a -> a
gcd (forall (v :: * -> *) a. Vector v a => v a -> a
G.unsafeHead v a
xs) v a
ys
| forall (v :: * -> *) a. Vector v a => v a -> Int
G.length v a
ys forall a. Eq a => a -> a -> Bool
== Int
1 = forall (v :: * -> *) a. v a -> Poly v a
Poly forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) a. Vector v a => a -> v a
G.singleton forall a b. (a -> b) -> a -> b
$ forall (v :: * -> *) b a.
Vector v b =>
(a -> b -> a) -> a -> v b -> a
G.foldl' forall a. GcdDomain a => a -> a -> a
gcd (forall (v :: * -> *) a. Vector v a => v a -> a
G.unsafeHead v a
ys) v a
xs
| Bool
otherwise = forall a (v :: * -> *).
(Eq a, Semiring a, Vector v a) =>
v a -> Poly v a
toPoly' forall a b. (a -> b) -> a -> b
$ forall a (v :: * -> *).
(Eq a, Ring a, GcdDomain a, Vector v a) =>
v a -> v a -> v a
gcdNonEmpty v a
xs v a
ys
{-# INLINE gcd #-}
lcm :: Poly v a -> Poly v a -> Poly v a
lcm x :: Poly v a
x@(Poly v a
xs) y :: Poly v a
y@(Poly v a
ys)
| forall (v :: * -> *) a. Vector v a => v a -> Bool
G.null v a
xs Bool -> Bool -> Bool
|| forall (v :: * -> *) a. Vector v a => v a -> Bool
G.null v a
ys = forall a. Semiring a => a
zero
| Bool
otherwise = (Poly v a
x forall a. GcdDomain a => a -> a -> a
`divide'` forall a. GcdDomain a => a -> a -> a
gcd Poly v a
x Poly v a
y) forall a. Semiring a => a -> a -> a
`times` Poly v a
y
{-# INLINABLE lcm #-}
coprime :: Poly v a -> Poly v a -> Bool
coprime Poly v a
x Poly v a
y = forall a. Maybe a -> Bool
isJust (forall a. Semiring a => a
one forall a. GcdDomain a => a -> a -> Maybe a
`divide` forall a. GcdDomain a => a -> a -> a
gcd Poly v a
x Poly v a
y)
{-# INLINABLE coprime #-}
gcdNonEmpty
:: (Eq a, Ring a, GcdDomain a, G.Vector v a)
=> v a
-> v a
-> v a
gcdNonEmpty :: forall a (v :: * -> *).
(Eq a, Ring a, GcdDomain a, Vector v a) =>
v a -> v a -> v a
gcdNonEmpty v a
xs v a
ys = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
let x :: a
x = forall (v :: * -> *) a. Vector v a => (a -> a -> a) -> v a -> a
G.foldl1' forall a. GcdDomain a => a -> a -> a
gcd v a
xs
y :: a
y = forall (v :: * -> *) a. Vector v a => (a -> a -> a) -> v a -> a
G.foldl1' forall a. GcdDomain a => a -> a -> a
gcd v a
ys
xy :: a
xy = a
x forall a. GcdDomain a => a -> a -> a
`gcd` a
y
Mutable v s a
xs' <- forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
v a -> m (Mutable v (PrimState m) a)
G.thaw v a
xs
Mutable v s a
ys' <- forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
v a -> m (Mutable v (PrimState m) a)
G.thaw v a
ys
Mutable v s a
zs' <- forall a (v :: * -> *) s.
(Eq a, Ring a, GcdDomain a, Vector v a) =>
Mutable v s a -> Mutable v s a -> ST s (Mutable v s a)
gcdM Mutable v s a
xs' Mutable v s a
ys'
let lenZs :: Int
lenZs = forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
MG.length Mutable v s a
zs'
go :: a -> Int -> ST s a
go a
acc Int
0 = forall (f :: * -> *) a. Applicative f => a -> f a
pure a
acc
go a
acc Int
n = do
a
t <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
MG.unsafeRead Mutable v s a
zs' (Int
n forall a. Num a => a -> a -> a
- Int
1)
a -> Int -> ST s a
go (a
acc forall a. GcdDomain a => a -> a -> a
`gcd` a
t) (Int
n forall a. Num a => a -> a -> a
- Int
1)
a
a <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
MG.unsafeRead Mutable v s a
zs' (Int
lenZs forall a. Num a => a -> a -> a
- Int
1)
a
z <- a -> Int -> ST s a
go a
a (Int
lenZs forall a. Num a => a -> a -> a
- Int
1)
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ [Int
0 .. Int
lenZs forall a. Num a => a -> a -> a
- Int
1] forall a b. (a -> b) -> a -> b
$ \Int
i ->
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
MG.unsafeModify Mutable v s a
zs'((forall a. Semiring a => a -> a -> a
`times` a
xy) forall b c a. (b -> c) -> (a -> b) -> a -> c
. (forall a. GcdDomain a => a -> a -> a
`divide'` a
z)) Int
i
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m (v a)
G.unsafeFreeze Mutable v s a
zs'
{-# INLINABLE gcdNonEmpty #-}
gcdM
:: (Eq a, Ring a, GcdDomain a, G.Vector v a)
=> G.Mutable v s a
-> G.Mutable v s a
-> ST s (G.Mutable v s a)
gcdM :: forall a (v :: * -> *) s.
(Eq a, Ring a, GcdDomain a, Vector v a) =>
Mutable v s a -> Mutable v s a -> ST s (Mutable v s a)
gcdM Mutable v s a
xs Mutable v s a
ys
| forall (v :: * -> * -> *) a s. MVector v a => v s a -> Bool
MG.null Mutable v s a
xs = forall (f :: * -> *) a. Applicative f => a -> f a
pure Mutable v s a
ys
| forall (v :: * -> * -> *) a s. MVector v a => v s a -> Bool
MG.null Mutable v s a
ys = forall (f :: * -> *) a. Applicative f => a -> f a
pure Mutable v s a
xs
| Bool
otherwise = do
let lenXs :: Int
lenXs = forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
MG.length Mutable v s a
xs
lenYs :: Int
lenYs = forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
MG.length Mutable v s a
ys
a
xLast <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
MG.unsafeRead Mutable v s a
xs (Int
lenXs forall a. Num a => a -> a -> a
- Int
1)
a
yLast <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
MG.unsafeRead Mutable v s a
ys (Int
lenYs forall a. Num a => a -> a -> a
- Int
1)
let z :: a
z = a
xLast forall a. GcdDomain a => a -> a -> a
`lcm` a
yLast
zx :: a
zx = a
z forall a. GcdDomain a => a -> a -> a
`divide'` a
xLast
zy :: a
zy = a
z forall a. GcdDomain a => a -> a -> a
`divide'` a
yLast
if
| Int
lenYs forall a. Ord a => a -> a -> Bool
<= Int
lenXs
, Just a
xy <- a
xLast forall a. GcdDomain a => a -> a -> Maybe a
`divide` a
yLast -> do
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ [Int
0 .. Int
lenYs forall a. Num a => a -> a -> a
- Int
1] forall a b. (a -> b) -> a -> b
$ \Int
i -> do
a
y <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
MG.unsafeRead Mutable v s a
ys Int
i
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (a
y forall a. Eq a => a -> a -> Bool
/= forall a. Semiring a => a
zero) forall a b. (a -> b) -> a -> b
$
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
MG.unsafeModify
Mutable v s a
xs
(\a
x -> a
x forall a. Ring a => a -> a -> a
`minus` a
y forall a. Semiring a => a -> a -> a
`times` a
xy)
(Int
i forall a. Num a => a -> a -> a
+ Int
lenXs forall a. Num a => a -> a -> a
- Int
lenYs)
Mutable v s a
xs' <- forall (v :: * -> *) a s.
Vector v a =>
(a -> Bool) -> Mutable v s a -> ST s (Mutable v s a)
dropWhileEndM forall a. (Eq a, Semiring a) => a -> Bool
isZero Mutable v s a
xs
forall a (v :: * -> *) s.
(Eq a, Ring a, GcdDomain a, Vector v a) =>
Mutable v s a -> Mutable v s a -> ST s (Mutable v s a)
gcdM Mutable v s a
xs' Mutable v s a
ys
| Int
lenXs forall a. Ord a => a -> a -> Bool
<= Int
lenYs
, Just a
yx <- a
yLast forall a. GcdDomain a => a -> a -> Maybe a
`divide` a
xLast -> do
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ [Int
0 .. Int
lenXs forall a. Num a => a -> a -> a
- Int
1] forall a b. (a -> b) -> a -> b
$ \Int
i -> do
a
x <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
MG.unsafeRead Mutable v s a
xs Int
i
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (a
x forall a. Eq a => a -> a -> Bool
/= forall a. Semiring a => a
zero) forall a b. (a -> b) -> a -> b
$
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
MG.unsafeModify
Mutable v s a
ys
(\a
y -> a
y forall a. Ring a => a -> a -> a
`minus` a
x forall a. Semiring a => a -> a -> a
`times` a
yx)
(Int
i forall a. Num a => a -> a -> a
+ Int
lenYs forall a. Num a => a -> a -> a
- Int
lenXs)
Mutable v s a
ys' <- forall (v :: * -> *) a s.
Vector v a =>
(a -> Bool) -> Mutable v s a -> ST s (Mutable v s a)
dropWhileEndM forall a. (Eq a, Semiring a) => a -> Bool
isZero Mutable v s a
ys
forall a (v :: * -> *) s.
(Eq a, Ring a, GcdDomain a, Vector v a) =>
Mutable v s a -> Mutable v s a -> ST s (Mutable v s a)
gcdM Mutable v s a
xs Mutable v s a
ys'
| Int
lenYs forall a. Ord a => a -> a -> Bool
<= Int
lenXs -> do
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ [Int
0 .. Int
lenYs forall a. Num a => a -> a -> a
- Int
1] forall a b. (a -> b) -> a -> b
$ \Int
i -> do
a
y <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
MG.unsafeRead Mutable v s a
ys Int
i
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
MG.unsafeModify
Mutable v s a
xs
(\a
x -> a
x forall a. Semiring a => a -> a -> a
`times` a
zx forall a. Ring a => a -> a -> a
`minus` a
y forall a. Semiring a => a -> a -> a
`times` a
zy)
(Int
i forall a. Num a => a -> a -> a
+ Int
lenXs forall a. Num a => a -> a -> a
- Int
lenYs)
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ [Int
0 .. Int
lenXs forall a. Num a => a -> a -> a
- Int
lenYs forall a. Num a => a -> a -> a
- Int
1] forall a b. (a -> b) -> a -> b
$
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
MG.unsafeModify Mutable v s a
xs (forall a. Semiring a => a -> a -> a
`times` a
zx)
Mutable v s a
xs' <- forall (v :: * -> *) a s.
Vector v a =>
(a -> Bool) -> Mutable v s a -> ST s (Mutable v s a)
dropWhileEndM forall a. (Eq a, Semiring a) => a -> Bool
isZero Mutable v s a
xs
forall a (v :: * -> *) s.
(Eq a, Ring a, GcdDomain a, Vector v a) =>
Mutable v s a -> Mutable v s a -> ST s (Mutable v s a)
gcdM Mutable v s a
xs' Mutable v s a
ys
| Bool
otherwise -> do
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ [Int
0 .. Int
lenXs forall a. Num a => a -> a -> a
- Int
1] forall a b. (a -> b) -> a -> b
$ \Int
i -> do
a
x <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
MG.unsafeRead Mutable v s a
xs Int
i
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
MG.unsafeModify
Mutable v s a
ys
(\a
y -> a
y forall a. Semiring a => a -> a -> a
`times` a
zy forall a. Ring a => a -> a -> a
`minus` a
x forall a. Semiring a => a -> a -> a
`times` a
zx)
(Int
i forall a. Num a => a -> a -> a
+ Int
lenYs forall a. Num a => a -> a -> a
- Int
lenXs)
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ [Int
0 .. Int
lenYs forall a. Num a => a -> a -> a
- Int
lenXs forall a. Num a => a -> a -> a
- Int
1] forall a b. (a -> b) -> a -> b
$
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
MG.unsafeModify Mutable v s a
ys (forall a. Semiring a => a -> a -> a
`times` a
zy)
Mutable v s a
ys' <- forall (v :: * -> *) a s.
Vector v a =>
(a -> Bool) -> Mutable v s a -> ST s (Mutable v s a)
dropWhileEndM forall a. (Eq a, Semiring a) => a -> Bool
isZero Mutable v s a
ys
forall a (v :: * -> *) s.
(Eq a, Ring a, GcdDomain a, Vector v a) =>
Mutable v s a -> Mutable v s a -> ST s (Mutable v s a)
gcdM Mutable v s a
xs Mutable v s a
ys'
{-# INLINABLE gcdM #-}
divide' :: GcdDomain a => a -> a -> a
divide' :: forall a. GcdDomain a => a -> a -> a
divide' = (forall a. a -> Maybe a -> a
fromMaybe (forall a. HasCallStack => [Char] -> a
error [Char]
"gcd: violated internal invariant") forall b c a. (b -> c) -> (a -> b) -> a -> c
.) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. GcdDomain a => a -> a -> Maybe a
divide
isZeroM
:: (Eq a, Semiring a, G.Vector v a)
=> G.Mutable v s a
-> ST s Bool
isZeroM :: forall a (v :: * -> *) s.
(Eq a, Semiring a, Vector v a) =>
Mutable v s a -> ST s Bool
isZeroM Mutable v s a
xs = Int -> ST s Bool
go (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
MG.length Mutable v s a
xs)
where
go :: Int -> ST s Bool
go Int
0 = forall (f :: * -> *) a. Applicative f => a -> f a
pure Bool
True
go Int
n = do
a
x <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
MG.unsafeRead Mutable v s a
xs (Int
n forall a. Num a => a -> a -> a
- Int
1)
if a
x forall a. Eq a => a -> a -> Bool
== forall a. Semiring a => a
zero then Int -> ST s Bool
go (Int
n forall a. Num a => a -> a -> a
- Int
1) else forall (f :: * -> *) a. Applicative f => a -> f a
pure Bool
False
{-# INLINE isZeroM #-}
quotient
:: (Eq a, Ring a, GcdDomain a, G.Vector v a)
=> v a
-> v a
-> Maybe (v a)
quotient :: forall a (v :: * -> *).
(Eq a, Ring a, GcdDomain a, Vector v a) =>
v a -> v a -> Maybe (v a)
quotient v a
xs v a
ys
| forall (v :: * -> *) a. Vector v a => v a -> Bool
G.null v a
ys = forall a e. Exception e => e -> a
throw ArithException
DivideByZero
| forall (v :: * -> *) a. Vector v a => v a -> Bool
G.null v a
xs = forall a. a -> Maybe a
Just v a
xs
| forall (v :: * -> *) a. Vector v a => v a -> Int
G.length v a
xs forall a. Ord a => a -> a -> Bool
< forall (v :: * -> *) a. Vector v a => v a -> Int
G.length v a
ys = forall a. Maybe a
Nothing
| Bool
otherwise = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
let lenXs :: Int
lenXs = forall (v :: * -> *) a. Vector v a => v a -> Int
G.length v a
xs
lenYs :: Int
lenYs = forall (v :: * -> *) a. Vector v a => v a -> Int
G.length v a
ys
lenQs :: Int
lenQs = Int
lenXs forall a. Num a => a -> a -> a
- Int
lenYs forall a. Num a => a -> a -> a
+ Int
1
Mutable v s a
qs <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
MG.unsafeNew Int
lenQs
Mutable v s a
rs <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
MG.unsafeNew Int
lenXs
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> v a -> m ()
G.unsafeCopy Mutable v s a
rs v a
xs
let go :: Int -> ST s (Maybe (v a))
go Int
i
| Int
i forall a. Ord a => a -> a -> Bool
< Int
0 = do
Bool
b <- forall a (v :: * -> *) s.
(Eq a, Semiring a, Vector v a) =>
Mutable v s a -> ST s Bool
isZeroM Mutable v s a
rs
if Bool
b
then forall a. a -> Maybe a
Just forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m (v a)
G.unsafeFreeze Mutable v s a
qs
else forall (f :: * -> *) a. Applicative f => a -> f a
pure forall a. Maybe a
Nothing
| Bool
otherwise = do
a
r <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
MG.unsafeRead Mutable v s a
rs (Int
lenYs forall a. Num a => a -> a -> a
- Int
1 forall a. Num a => a -> a -> a
+ Int
i)
case a
r forall a. GcdDomain a => a -> a -> Maybe a
`divide` forall (v :: * -> *) a. Vector v a => v a -> a
G.unsafeLast v a
ys of
Maybe a
Nothing -> forall (f :: * -> *) a. Applicative f => a -> f a
pure forall a. Maybe a
Nothing
Just a
q -> do
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
MG.unsafeWrite Mutable v s a
qs Int
i a
q
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ [Int
0 .. Int
lenYs forall a. Num a => a -> a -> a
- Int
1] forall a b. (a -> b) -> a -> b
$ \Int
k ->
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
MG.unsafeModify
Mutable v s a
rs
(\a
c -> a
c forall a. Ring a => a -> a -> a
`minus` a
q forall a. Semiring a => a -> a -> a
`times` forall (v :: * -> *) a. Vector v a => v a -> Int -> a
G.unsafeIndex v a
ys Int
k)
(Int
i forall a. Num a => a -> a -> a
+ Int
k)
Int -> ST s (Maybe (v a))
go (Int
i forall a. Num a => a -> a -> a
- Int
1)
Int -> ST s (Maybe (v a))
go (Int
lenQs forall a. Num a => a -> a -> a
- Int
1)
{-# INLINABLE quotient #-}