-- |
-- Module:      Data.Poly.Internal.Dense.GcdDomain
-- Copyright:   (c) 2019 Andrew Lelechenko
-- Licence:     BSD3
-- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
--
-- 'GcdDomain' instance with a 'GcdDomain' constraint on the coefficient type.
--

{-# 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

-- | @since 0.3.0.0
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 #-}