{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MonoLocalBinds #-}
{-# LANGUAGE OverloadedLabels #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE NoImplicitPrelude #-}

-- | Partial fraction decomposition for unary polynomials
module Algebra.Ring.Fraction.Decomp where

import Algebra.Prelude.Core
import Algebra.Ring.Euclidean.Quotient
import Algebra.Ring.Polynomial.Univariate
import Data.Functor ((<&>))
import qualified Data.IntMap.Strict as IM
import Data.List.NonEmpty (NonEmpty (..))
import Data.Monoid (Dual (..))

data PartialFractionDecomp k = PartialFraction
  { PartialFractionDecomp k -> Unipol k
residualPoly :: Unipol k
  , PartialFractionDecomp k -> NonEmpty (Unipol k, IntMap (Unipol k))
partialFracs :: NonEmpty (Unipol k, IntMap (Unipol k))
  }
  deriving (Int -> PartialFractionDecomp k -> ShowS
[PartialFractionDecomp k] -> ShowS
PartialFractionDecomp k -> String
(Int -> PartialFractionDecomp k -> ShowS)
-> (PartialFractionDecomp k -> String)
-> ([PartialFractionDecomp k] -> ShowS)
-> Show (PartialFractionDecomp k)
forall k.
(DecidableZero k, Ring k, Commutative k, Eq k, PrettyCoeff k) =>
Int -> PartialFractionDecomp k -> ShowS
forall k.
(DecidableZero k, Ring k, Commutative k, Eq k, PrettyCoeff k) =>
[PartialFractionDecomp k] -> ShowS
forall k.
(DecidableZero k, Ring k, Commutative k, Eq k, PrettyCoeff k) =>
PartialFractionDecomp k -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [PartialFractionDecomp k] -> ShowS
$cshowList :: forall k.
(DecidableZero k, Ring k, Commutative k, Eq k, PrettyCoeff k) =>
[PartialFractionDecomp k] -> ShowS
show :: PartialFractionDecomp k -> String
$cshow :: forall k.
(DecidableZero k, Ring k, Commutative k, Eq k, PrettyCoeff k) =>
PartialFractionDecomp k -> String
showsPrec :: Int -> PartialFractionDecomp k -> ShowS
$cshowsPrec :: forall k.
(DecidableZero k, Ring k, Commutative k, Eq k, PrettyCoeff k) =>
Int -> PartialFractionDecomp k -> ShowS
Show, PartialFractionDecomp k -> PartialFractionDecomp k -> Bool
(PartialFractionDecomp k -> PartialFractionDecomp k -> Bool)
-> (PartialFractionDecomp k -> PartialFractionDecomp k -> Bool)
-> Eq (PartialFractionDecomp k)
forall k.
(Eq k, DecidableZero k) =>
PartialFractionDecomp k -> PartialFractionDecomp k -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: PartialFractionDecomp k -> PartialFractionDecomp k -> Bool
$c/= :: forall k.
(Eq k, DecidableZero k) =>
PartialFractionDecomp k -> PartialFractionDecomp k -> Bool
== :: PartialFractionDecomp k -> PartialFractionDecomp k -> Bool
$c== :: forall k.
(Eq k, DecidableZero k) =>
PartialFractionDecomp k -> PartialFractionDecomp k -> Bool
Eq, Eq (PartialFractionDecomp k)
Eq (PartialFractionDecomp k)
-> (PartialFractionDecomp k -> PartialFractionDecomp k -> Ordering)
-> (PartialFractionDecomp k -> PartialFractionDecomp k -> Bool)
-> (PartialFractionDecomp k -> PartialFractionDecomp k -> Bool)
-> (PartialFractionDecomp k -> PartialFractionDecomp k -> Bool)
-> (PartialFractionDecomp k -> PartialFractionDecomp k -> Bool)
-> (PartialFractionDecomp k
    -> PartialFractionDecomp k -> PartialFractionDecomp k)
-> (PartialFractionDecomp k
    -> PartialFractionDecomp k -> PartialFractionDecomp k)
-> Ord (PartialFractionDecomp k)
PartialFractionDecomp k -> PartialFractionDecomp k -> Bool
PartialFractionDecomp k -> PartialFractionDecomp k -> Ordering
PartialFractionDecomp k
-> PartialFractionDecomp k -> PartialFractionDecomp k
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall k. (Ord k, DecidableZero k) => Eq (PartialFractionDecomp k)
forall k.
(Ord k, DecidableZero k) =>
PartialFractionDecomp k -> PartialFractionDecomp k -> Bool
forall k.
(Ord k, DecidableZero k) =>
PartialFractionDecomp k -> PartialFractionDecomp k -> Ordering
forall k.
(Ord k, DecidableZero k) =>
PartialFractionDecomp k
-> PartialFractionDecomp k -> PartialFractionDecomp k
min :: PartialFractionDecomp k
-> PartialFractionDecomp k -> PartialFractionDecomp k
$cmin :: forall k.
(Ord k, DecidableZero k) =>
PartialFractionDecomp k
-> PartialFractionDecomp k -> PartialFractionDecomp k
max :: PartialFractionDecomp k
-> PartialFractionDecomp k -> PartialFractionDecomp k
$cmax :: forall k.
(Ord k, DecidableZero k) =>
PartialFractionDecomp k
-> PartialFractionDecomp k -> PartialFractionDecomp k
>= :: PartialFractionDecomp k -> PartialFractionDecomp k -> Bool
$c>= :: forall k.
(Ord k, DecidableZero k) =>
PartialFractionDecomp k -> PartialFractionDecomp k -> Bool
> :: PartialFractionDecomp k -> PartialFractionDecomp k -> Bool
$c> :: forall k.
(Ord k, DecidableZero k) =>
PartialFractionDecomp k -> PartialFractionDecomp k -> Bool
<= :: PartialFractionDecomp k -> PartialFractionDecomp k -> Bool
$c<= :: forall k.
(Ord k, DecidableZero k) =>
PartialFractionDecomp k -> PartialFractionDecomp k -> Bool
< :: PartialFractionDecomp k -> PartialFractionDecomp k -> Bool
$c< :: forall k.
(Ord k, DecidableZero k) =>
PartialFractionDecomp k -> PartialFractionDecomp k -> Bool
compare :: PartialFractionDecomp k -> PartialFractionDecomp k -> Ordering
$ccompare :: forall k.
(Ord k, DecidableZero k) =>
PartialFractionDecomp k -> PartialFractionDecomp k -> Ordering
$cp1Ord :: forall k. (Ord k, DecidableZero k) => Eq (PartialFractionDecomp k)
Ord)

partialFractionDecomposition ::
  (Field k, CoeffRing k, Functor m) =>
  (Unipol k -> m (k, NonEmpty (Unipol k, Natural))) ->
  Fraction (Unipol k) ->
  m (PartialFractionDecomp k)
partialFractionDecomposition :: (Unipol k -> m (k, NonEmpty (Unipol k, Natural)))
-> Fraction (Unipol k) -> m (PartialFractionDecomp k)
partialFractionDecomposition Unipol k -> m (k, NonEmpty (Unipol k, Natural))
factor Fraction (Unipol k)
q =
  let g0 :: Unipol k
g0 = Fraction (Unipol k) -> Unipol k
forall t. Fraction t -> t
numerator Fraction (Unipol k)
q
      f0 :: Unipol k
f0 = Fraction (Unipol k) -> Unipol k
forall t. Fraction t -> t
denominator Fraction (Unipol k)
q
      g :: Unipol k
g = k -> k
forall r. Division r => r -> r
recip (Unipol k -> Coefficient (Unipol k)
forall poly. IsOrderedPolynomial poly => poly -> Coefficient poly
leadingCoeff Unipol k
f0) k -> Unipol k -> Unipol k
forall r m. Module (Scalar r) m => r -> m -> m
.*. Unipol k
g0
      f :: Unipol k
f = Unipol k -> Unipol k
forall poly.
(Field (Coefficient poly), IsOrderedPolynomial poly) =>
poly -> poly
monoize Unipol k
f0
   in Unipol k -> m (k, NonEmpty (Unipol k, Natural))
factor Unipol k
f m (k, NonEmpty (Unipol k, Natural))
-> ((k, NonEmpty (Unipol k, Natural)) -> PartialFractionDecomp k)
-> m (PartialFractionDecomp k)
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> \(k
k, NonEmpty (Unipol k, Natural)
fs) ->
        k -> PartialFractionDecomp k -> PartialFractionDecomp k
forall k.
CoeffRing k =>
k -> PartialFractionDecomp k -> PartialFractionDecomp k
scalePF k
k (PartialFractionDecomp k -> PartialFractionDecomp k)
-> PartialFractionDecomp k -> PartialFractionDecomp k
forall a b. (a -> b) -> a -> b
$ Unipol k -> NonEmpty (Unipol k, Natural) -> PartialFractionDecomp k
forall k.
(CoeffRing k, Field k) =>
Unipol k -> NonEmpty (Unipol k, Natural) -> PartialFractionDecomp k
partialFractionDecompositionWith Unipol k
g NonEmpty (Unipol k, Natural)
fs

scalePF :: (CoeffRing k) => k -> PartialFractionDecomp k -> PartialFractionDecomp k
scalePF :: k -> PartialFractionDecomp k -> PartialFractionDecomp k
scalePF k
c PartialFractionDecomp k
pf =
  PartialFraction :: forall k.
Unipol k
-> NonEmpty (Unipol k, IntMap (Unipol k))
-> PartialFractionDecomp k
PartialFraction
    { residualPoly :: Unipol k
residualPoly = k
c k -> Unipol k -> Unipol k
forall r m. Module (Scalar r) m => r -> m -> m
.*. PartialFractionDecomp k -> Unipol k
forall k. PartialFractionDecomp k -> Unipol k
residualPoly PartialFractionDecomp k
pf
    , partialFracs :: NonEmpty (Unipol k, IntMap (Unipol k))
partialFracs = (IntMap (Unipol k) -> IntMap (Unipol k))
-> (Unipol k, IntMap (Unipol k)) -> (Unipol k, IntMap (Unipol k))
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second ((Unipol k -> Unipol k) -> IntMap (Unipol k) -> IntMap (Unipol k)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (k
c k -> Unipol k -> Unipol k
forall r m. Module (Scalar r) m => r -> m -> m
.*.)) ((Unipol k, IntMap (Unipol k)) -> (Unipol k, IntMap (Unipol k)))
-> NonEmpty (Unipol k, IntMap (Unipol k))
-> NonEmpty (Unipol k, IntMap (Unipol k))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> PartialFractionDecomp k -> NonEmpty (Unipol k, IntMap (Unipol k))
forall k.
PartialFractionDecomp k -> NonEmpty (Unipol k, IntMap (Unipol k))
partialFracs PartialFractionDecomp k
pf
    }

{- | Calculates the partial fraction decomposition
with respect to the given pairwise coprime
monic factorisation of the denominator.

>>> partialFractionDecompositionWith (#x ^ 3 + 4 * #x^2 - #x - 2 :: Unipol Rational) ((#x, 2) :| [(#x - 1, 1), (#x + 1, 1)])
(x,fromList [(1,1),(2,2)]) :| [(x - 1,fromList [(1,1)]),(x + 1,fromList [(1,-1)])]
-}
partialFractionDecompositionWith ::
  (CoeffRing k, Field k) =>
  -- | Numerator
  Unipol k ->
  -- | Pairwise coprime (partial) factorisation of
  -- denominator \(f = \sum_i f_i^{e_i}\) with each
  -- \(f_i\) monic and non-constant.
  NonEmpty (Unipol k, Natural) ->
  PartialFractionDecomp k
partialFractionDecompositionWith :: Unipol k -> NonEmpty (Unipol k, Natural) -> PartialFractionDecomp k
partialFractionDecompositionWith Unipol k
g NonEmpty (Unipol k, Natural)
fs =
  let f :: Unipol k
f = Mult (Unipol k) -> Unipol k
forall a. Mult a -> a
runMult (Mult (Unipol k) -> Unipol k) -> Mult (Unipol k) -> Unipol k
forall a b. (a -> b) -> a -> b
$ ((Unipol k, Natural) -> Mult (Unipol k))
-> NonEmpty (Unipol k, Natural) -> Mult (Unipol k)
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap (Unipol k -> Mult (Unipol k)
forall a. a -> Mult a
Mult (Unipol k -> Mult (Unipol k))
-> ((Unipol k, Natural) -> Unipol k)
-> (Unipol k, Natural)
-> Mult (Unipol k)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Unipol k -> Natural -> Unipol k)
-> (Unipol k, Natural) -> Unipol k
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Unipol k -> Natural -> Unipol k
forall r. Unital r => r -> Natural -> r
(^)) NonEmpty (Unipol k, Natural)
fs
      (Unipol k
q, Unipol k
r)
        | Unipol k -> Maybe Natural
forall d. Euclidean d => d -> Maybe Natural
degree Unipol k
g Maybe Natural -> Maybe Natural -> Bool
forall a. Ord a => a -> a -> Bool
< Unipol k -> Maybe Natural
forall d. Euclidean d => d -> Maybe Natural
degree Unipol k
f = (Unipol k
forall m. Monoidal m => m
zero, Unipol k
g)
        | Bool
otherwise = Unipol k
g Unipol k -> Unipol k -> (Unipol k, Unipol k)
forall r.
(CoeffRing r, Field r) =>
Unipol r -> Unipol r -> (Unipol r, Unipol r)
`divModUnipol` Unipol k
f
      pf :: NonEmpty ((Unipol k, Natural), Unipol k)
pf = Unipol k
-> NonEmpty (Unipol k, Natural)
-> NonEmpty ((Unipol k, Natural), Unipol k)
forall k.
(Field k, CoeffRing k) =>
Unipol k
-> NonEmpty (Unipol k, Natural)
-> NonEmpty ((Unipol k, Natural), Unipol k)
poweredPartialFraction Unipol k
r NonEmpty (Unipol k, Natural)
fs
      pows :: NonEmpty (Unipol k, IntMap (Unipol k))
pows =
        NonEmpty ((Unipol k, Natural), Unipol k)
pf NonEmpty ((Unipol k, Natural), Unipol k)
-> (((Unipol k, Natural), Unipol k)
    -> (Unipol k, IntMap (Unipol k)))
-> NonEmpty (Unipol k, IntMap (Unipol k))
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> \((Unipol k
fi, Natural
e), Unipol k
gi) ->
          (Unipol k
fi, (Int -> Int) -> IntMap (Unipol k) -> IntMap (Unipol k)
forall a. (Int -> Int) -> IntMap a -> IntMap a
IM.mapKeys (Natural -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Natural
e Int -> Int -> Int
forall r. Group r => r -> r -> r
-) (IntMap (Unipol k) -> IntMap (Unipol k))
-> IntMap (Unipol k) -> IntMap (Unipol k)
forall a b. (a -> b) -> a -> b
$ Unipol k -> Unipol k -> IntMap (Unipol k)
forall k.
(Field k, CoeffRing k) =>
Unipol k -> Unipol k -> IntMap (Unipol k)
pAdicExpansion Unipol k
gi Unipol k
fi)
   in Unipol k
-> NonEmpty (Unipol k, IntMap (Unipol k))
-> PartialFractionDecomp k
forall k.
Unipol k
-> NonEmpty (Unipol k, IntMap (Unipol k))
-> PartialFractionDecomp k
PartialFraction Unipol k
q NonEmpty (Unipol k, IntMap (Unipol k))
pows

{- | @'pAdicExpansion' f p@ gives a @p@-adic expansion of @f@ by a monic nonconstant polynomial @p@; i.e. \(a_i \in k[X]\) such that \(\deg a_i < \deg p\)_{i < k}, \(\deg f < km\), and:

\[
  f = a_{k - 1} p^{k-1} + \cdots + a_1 p + a_0.
\]

>>> pAdicExpansion (#x + 2 :: Unipol Rational) #x
fromList [(0,2),(1,1)]
-}
pAdicExpansion ::
  (Field k, CoeffRing k) =>
  Unipol k ->
  Unipol k ->
  IntMap (Unipol k)
pAdicExpansion :: Unipol k -> Unipol k -> IntMap (Unipol k)
pAdicExpansion Unipol k
f Unipol k
p = Int -> Unipol k -> IntMap (Unipol k) -> IntMap (Unipol k)
loop Int
0 Unipol k
f IntMap (Unipol k)
forall a. IntMap a
IM.empty
  where
    !degp :: Maybe Natural
degp = Unipol k -> Maybe Natural
forall d. Euclidean d => d -> Maybe Natural
degree Unipol k
p
    loop :: Int -> Unipol k -> IntMap (Unipol k) -> IntMap (Unipol k)
loop !Int
n !Unipol k
ai !IntMap (Unipol k)
acc
      | Unipol k -> Maybe Natural
forall d. Euclidean d => d -> Maybe Natural
degree Unipol k
ai Maybe Natural -> Maybe Natural -> Bool
forall a. Ord a => a -> a -> Bool
< Maybe Natural
degp =
        if Unipol k -> Bool
forall r. DecidableZero r => r -> Bool
isZero Unipol k
ai then IntMap (Unipol k)
acc else Int -> Unipol k -> IntMap (Unipol k) -> IntMap (Unipol k)
forall a. Int -> a -> IntMap a -> IntMap a
IM.insert Int
n Unipol k
ai IntMap (Unipol k)
acc
      | Bool
otherwise =
        let (Unipol k
q, Unipol k
r) = Unipol k
ai Unipol k -> Unipol k -> (Unipol k, Unipol k)
forall r.
(CoeffRing r, Field r) =>
Unipol r -> Unipol r -> (Unipol r, Unipol r)
`divModUnipol` Unipol k
p
            !acc' :: IntMap (Unipol k)
acc'
              | Unipol k -> Bool
forall r. DecidableZero r => r -> Bool
isZero Unipol k
r = IntMap (Unipol k)
acc
              | Bool
otherwise = Int -> Unipol k -> IntMap (Unipol k) -> IntMap (Unipol k)
forall a. Int -> a -> IntMap a -> IntMap a
IM.insert Int
n Unipol k
r IntMap (Unipol k)
acc
         in Int -> Unipol k -> IntMap (Unipol k) -> IntMap (Unipol k)
loop (Int
n Int -> Int -> Int
forall r. Additive r => r -> r -> r
+ Int
1) Unipol k
q IntMap (Unipol k)
acc'

-- >>> poweredPartialFraction (#x ^ 3 + 4 * #x^2 - #x - 2 :: Unipol Rational) ((#x, 2) :| [(#x - 1, 1), (#x + 1, 1)])
-- ((x,2),x + 2) :| [((x - 1,1),1),((x + 1,1),-1)]

-- | Pseudo-partial fraction decomposition
poweredPartialFraction ::
  forall k.
  (Field k, CoeffRing k) =>
  -- | Numerator @g@ with \(\deg g < \deg f).
  Unipol k ->
  -- | Pairwise coprime (partial) factorisation of
  -- denominator \(f = \sum_i f_i^{e_i}\) with each
  -- \(f_i\) monic and non-constant.
  NonEmpty (Unipol k, Natural) ->
  NonEmpty ((Unipol k, Natural), Unipol k)
poweredPartialFraction :: Unipol k
-> NonEmpty (Unipol k, Natural)
-> NonEmpty ((Unipol k, Natural), Unipol k)
poweredPartialFraction Unipol k
g = (NonEmpty (Unipol k, Natural)
 -> [(Unipol k, Natural)] -> ((Unipol k, Natural), Unipol k))
-> NonEmpty (Unipol k, Natural)
-> NonEmpty ((Unipol k, Natural), Unipol k)
forall a b. (NonEmpty a -> [a] -> b) -> NonEmpty a -> NonEmpty b
scanZipper NonEmpty (Unipol k, Natural)
-> [(Unipol k, Natural)] -> ((Unipol k, Natural), Unipol k)
ci
  where
    invert :: (a, Natural) -> Quotient r a
invert (a
fi, Natural
ei) =
      Quotient r a -> Maybe (Quotient r a) -> Quotient r a
forall a. a -> Maybe a -> a
fromMaybe (String -> Quotient r a
forall a. HasCallStack => String -> a
error String
"Not coprime!") (Quotient r a -> Maybe (Quotient r a)
forall r. DecidableUnits r => r -> Maybe r
recipUnit (Quotient r a -> Maybe (Quotient r a))
-> Quotient r a -> Maybe (Quotient r a)
forall a b. (a -> b) -> a -> b
$ a -> Quotient r a
forall k (r :: k) a.
(Reifies r a, Euclidean a) =>
a -> Quotient r a
quotient a
fi) Quotient r a -> Natural -> Quotient r a
forall r. Unital r => r -> Natural -> r
^ Natural
ei
    ci :: NonEmpty (Unipol k, Natural)
-> [(Unipol k, Natural)] -> ((Unipol k, Natural), Unipol k)
ci ((Unipol k
f, Natural
e) :| [(Unipol k, Natural)]
fs) [(Unipol k, Natural)]
xs =
      let fe :: Unipol k
fe = Unipol k
f Unipol k -> Natural -> Unipol k
forall r. Unital r => r -> Natural -> r
^ Natural
e
       in ( (Unipol k
f, Natural
e)
          , Unipol k
-> (forall r. Reifies r (Unipol k) => Quotient r (Unipol k))
-> Unipol k
forall a.
Euclidean a =>
a -> (forall r. Reifies r a => Quotient r a) -> a
withQuotient Unipol k
fe ((forall r. Reifies r (Unipol k) => Quotient r (Unipol k))
 -> Unipol k)
-> (forall r. Reifies r (Unipol k) => Quotient r (Unipol k))
-> Unipol k
forall a b. (a -> b) -> a -> b
$
              Unipol k -> Quotient r (Unipol k)
forall k (r :: k) a.
(Reifies r a, Euclidean a) =>
a -> Quotient r a
quotient
                Unipol k
g
                Quotient r (Unipol k)
-> Quotient r (Unipol k) -> Quotient r (Unipol k)
forall r. Multiplicative r => r -> r -> r
* Mult (Quotient r (Unipol k)) -> Quotient r (Unipol k)
forall a. Mult a -> a
runMult (Dual (Mult (Quotient r (Unipol k))) -> Mult (Quotient r (Unipol k))
forall a. Dual a -> a
getDual (((Unipol k, Natural) -> Dual (Mult (Quotient r (Unipol k))))
-> [(Unipol k, Natural)] -> Dual (Mult (Quotient r (Unipol k)))
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap (Mult (Quotient r (Unipol k)) -> Dual (Mult (Quotient r (Unipol k)))
forall a. a -> Dual a
Dual (Mult (Quotient r (Unipol k))
 -> Dual (Mult (Quotient r (Unipol k))))
-> ((Unipol k, Natural) -> Mult (Quotient r (Unipol k)))
-> (Unipol k, Natural)
-> Dual (Mult (Quotient r (Unipol k)))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Quotient r (Unipol k) -> Mult (Quotient r (Unipol k))
forall a. a -> Mult a
Mult (Quotient r (Unipol k) -> Mult (Quotient r (Unipol k)))
-> ((Unipol k, Natural) -> Quotient r (Unipol k))
-> (Unipol k, Natural)
-> Mult (Quotient r (Unipol k))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Unipol k, Natural) -> Quotient r (Unipol k)
forall a r.
(Euclidean a, Reifies r a) =>
(a, Natural) -> Quotient r a
invert) [(Unipol k, Natural)]
xs))
                Quotient r (Unipol k)
-> Quotient r (Unipol k) -> Quotient r (Unipol k)
forall r. Multiplicative r => r -> r -> r
* Mult (Quotient r (Unipol k)) -> Quotient r (Unipol k)
forall a. Mult a -> a
runMult (((Unipol k, Natural) -> Mult (Quotient r (Unipol k)))
-> [(Unipol k, Natural)] -> Mult (Quotient r (Unipol k))
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap (Quotient r (Unipol k) -> Mult (Quotient r (Unipol k))
forall a. a -> Mult a
Mult (Quotient r (Unipol k) -> Mult (Quotient r (Unipol k)))
-> ((Unipol k, Natural) -> Quotient r (Unipol k))
-> (Unipol k, Natural)
-> Mult (Quotient r (Unipol k))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Unipol k, Natural) -> Quotient r (Unipol k)
forall a r.
(Euclidean a, Reifies r a) =>
(a, Natural) -> Quotient r a
invert) [(Unipol k, Natural)]
fs)
          )

scanZipper :: (NonEmpty a -> [a] -> b) -> NonEmpty a -> NonEmpty b
{-# INLINE scanZipper #-}
scanZipper :: (NonEmpty a -> [a] -> b) -> NonEmpty a -> NonEmpty b
scanZipper NonEmpty a -> [a] -> b
f (a
x0 :| [a]
ini) = NonEmpty a -> [a] -> b
f (a
x0 a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [a]
ini) [] b -> [b] -> NonEmpty b
forall a. a -> [a] -> NonEmpty a
:| [a] -> [a] -> [b]
go [a]
ini [a
x0]
  where
    go :: [a] -> [a] -> [b]
go [] [a]
_ = []
    go (a
x : [a]
xs) [a]
rest = NonEmpty a -> [a] -> b
f (a
x a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [a]
xs) [a]
rest b -> [b] -> [b]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [b]
go [a]
xs (a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
rest)