{-# LANGUAGE CPP #-}

-- see NOTE: [Pattern Synonym COMPLETE]
#if !MIN_VERSION_base(4, 16, 0)
{-# OPTIONS_GHC -Wno-incomplete-patterns #-}
#endif

-- | Provides typeclass for euclidean division.
--
-- @since 0.1
module Numeric.Algebra.Multiplicative.MEuclidean
  ( MEuclidean (..),
    mdiv,
    mmod,
    mgcd,
    mlcm,
  )
where

import Data.Coerce (coerce)
import Data.Int (Int16, Int32, Int64, Int8)
import Data.Kind (Constraint, Type)
import Data.Word (Word16, Word32, Word64, Word8)
import GHC.Natural (Natural)
import Numeric.Algebra.Additive.AMonoid
  ( AMonoid,
    pattern NonZero,
    pattern Zero,
  )
import Numeric.Algebra.Deriving (FromIntegral (MkFromIntegral))
import Numeric.Algebra.Multiplicative.MGroup (MGroup)
import Numeric.Algebra.Multiplicative.MSemigroup ((.*.))
import Numeric.Algebra.Normed (Normed (norm))

-- | 'MGroup' equipped with "euclidean" division.
--
--  @since 0.1
type MEuclidean :: Type -> Constraint
class (MGroup g) => MEuclidean g where
  -- | @since 0.1
  mdivMod :: g -> g -> (g, g)

-- | @since 0.1
mdiv :: (MEuclidean g) => g -> g -> g
mdiv :: forall g. MEuclidean g => g -> g -> g
mdiv g
x g
d = (g, g) -> g
forall a b. (a, b) -> a
fst ((g, g) -> g) -> (g, g) -> g
forall a b. (a -> b) -> a -> b
$ g -> g -> (g, g)
forall g. MEuclidean g => g -> g -> (g, g)
mdivMod g
x g
d
{-# INLINE mdiv #-}

-- | @since 0.1
mmod :: (MEuclidean g) => g -> g -> g
mmod :: forall g. MEuclidean g => g -> g -> g
mmod g
x g
d = (g, g) -> g
forall a b. (a, b) -> b
snd ((g, g) -> g) -> (g, g) -> g
forall a b. (a -> b) -> a -> b
$ g -> g -> (g, g)
forall g. MEuclidean g => g -> g -> (g, g)
mdivMod g
x g
d
{-# INLINE mmod #-}

-- | @since 0.1
mgcd :: (AMonoid g, Eq g, MEuclidean g, Normed g) => g -> g -> g
mgcd :: forall g. (AMonoid g, Eq g, MEuclidean g, Normed g) => g -> g -> g
mgcd g
x g
y = g -> g -> g
forall {t}. (AMonoid t, Eq t, MEuclidean t) => t -> t -> t
gcd' (g -> g
forall s. Normed s => s -> s
norm g
x) (g -> g
forall s. Normed s => s -> s
norm g
y)
  where
    gcd' :: t -> t -> t
gcd' t
a t
Zero = t
a
    gcd' t
a (NonZero t
b) = t -> t -> t
gcd' t
b (t
a t -> t -> t
forall g. MEuclidean g => g -> g -> g
`mmod` t
b)
{-# INLINE mgcd #-}

-- | @since 0.1
mlcm :: (AMonoid g, Eq g, MEuclidean g, Normed g) => g -> g -> g
mlcm :: forall g. (AMonoid g, Eq g, MEuclidean g, Normed g) => g -> g -> g
mlcm g
Zero g
_ = g
forall m. (AMonoid m, Eq m) => m
Zero
mlcm g
_ g
Zero = g
forall m. (AMonoid m, Eq m) => m
Zero
mlcm g
x g
y = g -> g
forall s. Normed s => s -> s
norm (g
x g -> g -> g
forall g. MEuclidean g => g -> g -> g
`mdiv` g -> g -> g
forall g. (AMonoid g, Eq g, MEuclidean g, Normed g) => g -> g -> g
mgcd g
x g
y g -> g -> g
forall s. MSemigroup s => s -> s -> s
.*. g
y)
{-# INLINE mlcm #-}

-- | @since 0.1
instance (Integral a) => MEuclidean (FromIntegral a) where
  mdivMod :: FromIntegral a
-> FromIntegral a -> (FromIntegral a, FromIntegral a)
mdivMod =
    forall a b. Coercible a b => a -> b
forall a b. Coercible a b => a -> b
coerce
      @(a -> a -> (a, a))
      @(FromIntegral a -> FromIntegral a -> (FromIntegral a, FromIntegral a))
      a -> a -> (a, a)
forall a. Integral a => a -> a -> (a, a)
divMod
  {-# INLINE mdivMod #-}

-- | @since 0.1
deriving via (FromIntegral Int) instance MEuclidean Int

-- | @since 0.1
deriving via (FromIntegral Int8) instance MEuclidean Int8

-- | @since 0.1
deriving via (FromIntegral Int16) instance MEuclidean Int16

-- | @since 0.1
deriving via (FromIntegral Int32) instance MEuclidean Int32

-- | @since 0.1
deriving via (FromIntegral Int64) instance MEuclidean Int64

-- | @since 0.1
deriving via (FromIntegral Integer) instance MEuclidean Integer

-- | @since 0.1
deriving via (FromIntegral Word) instance MEuclidean Word

-- | @since 0.1
deriving via (FromIntegral Word8) instance MEuclidean Word8

-- | @since 0.1
deriving via (FromIntegral Word16) instance MEuclidean Word16

-- | @since 0.1
deriving via (FromIntegral Word32) instance MEuclidean Word32

-- | @since 0.1
deriving via (FromIntegral Word64) instance MEuclidean Word64

-- | @since 0.1
deriving via (FromIntegral Natural) instance MEuclidean Natural