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

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 (zero))
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}. (Eq t, AMonoid 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
b =
      if t
b t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
forall m. AMonoid m => m
zero
        then t
a
        else 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
x g
y
  | g
x g -> g -> Bool
forall a. Eq a => a -> a -> Bool
== g
forall m. AMonoid m => m
zero = g
forall m. AMonoid m => m
zero
  | g
y g -> g -> Bool
forall a. Eq a => a -> a -> Bool
== g
forall m. AMonoid m => m
zero = g
forall m. AMonoid m => m
zero
  | Bool
otherwise = 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 MEuclidean Int where
  mdivMod :: Int -> Int -> (Int, Int)
mdivMod = Int -> Int -> (Int, Int)
forall a. Integral a => a -> a -> (a, a)
divMod
  {-# INLINE mdivMod #-}

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

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

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

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

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

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

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

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

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

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

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