-- |
-- Module:      Data.Euclidean
-- Copyright:   (c) 2019 Andrew Lelechenko
-- Licence:     BSD3
-- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
--

{-# LANGUAGE CPP                        #-}
{-# LANGUAGE DefaultSignatures          #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE MagicHash                  #-}
#if MIN_VERSION_base(4,12,0)
{-# LANGUAGE DerivingVia                #-}
{-# LANGUAGE StandaloneDeriving         #-}
#else
{-# LANGUAGE TemplateHaskell            #-}
#endif

module Data.Euclidean
  ( Euclidean(..)
  , Field
  , GcdDomain(..)
  , WrappedIntegral(..)
  , WrappedFractional(..)
  , gcdExt
  ) where

import Prelude hiding (quotRem, quot, rem, divMod, div, mod, gcd, lcm, negate, (*), Int, Word)
import qualified Prelude as P
import Control.Exception (throw, ArithException(..))
import Data.Bits (Bits)
import Data.Complex (Complex(..))
import Data.Int (Int, Int8, Int16, Int32, Int64)
import Data.Maybe (isJust)
import Data.Ratio (Ratio)
import Data.Semiring (Semiring(..), Ring(..), (*), minus, isZero, Mod2)
import Data.Word (Word, Word8, Word16, Word32, Word64)
import Foreign.C.Types (CFloat, CDouble)

#if !MIN_VERSION_base(4,12,0)
import Language.Haskell.TH.Syntax (Q, Dec, Type)
#endif

import Numeric.Natural

---------------------------------------------------------------------
-- Classes
---------------------------------------------------------------------

-- | 'GcdDomain' represents a
-- <https://en.wikipedia.org/wiki/GCD_domain GCD domain>.
-- This is a domain, where GCD can be defined,
-- but which does not necessarily allow a well-behaved
-- division with remainder (as in 'Euclidean' domains).
--
-- For example, there is no way to define 'rem' over
-- polynomials with integer coefficients such that
-- remainder is always "smaller" than divisor. However,
-- 'gcd' is still definable, just not by means of
-- Euclidean algorithm.
--
-- All methods of 'GcdDomain' have default implementations
-- in terms of 'Euclidean'. So most of the time
-- it is enough to write:
--
-- > instance GcdDomain Foo
-- > instance Euclidean Foo where
-- >   quotRem = ...
-- >   degree  = ...
class Semiring a => GcdDomain a where
  -- | Division without remainder.
  --
  -- prop> \x y -> (x * y) `divide` y == Just x
  -- prop> \x y -> maybe True (\z -> x == z * y) (x `divide` y)
  divide :: a -> a -> Maybe a

  default divide :: (Eq a, Euclidean a) => a -> a -> Maybe a
  divide a
x a
y = let (a
q, a
r) = a -> a -> (a, a)
forall a. Euclidean a => a -> a -> (a, a)
quotRem a
x a
y in
    if a -> Bool
forall a. (Eq a, Semiring a) => a -> Bool
isZero a
r then a -> Maybe a
forall a. a -> Maybe a
Just a
q else Maybe a
forall a. Maybe a
Nothing

  -- | Greatest common divisor. Must satisfy
  --
  -- prop> \x y -> isJust (x `divide` gcd x y) && isJust (y `divide` gcd x y)
  -- prop> \x y z -> isJust (gcd (x * z) (y * z) `divide` z)
  gcd :: a -> a -> a

  default gcd :: (Eq a, Euclidean a) => a -> a -> a
  gcd a
a a
b
    | a -> Bool
forall a. (Eq a, Semiring a) => a -> Bool
isZero a
b  = a
a
    | Bool
otherwise = a -> a -> a
forall a. GcdDomain a => a -> a -> a
gcd a
b (a
a a -> a -> a
forall a. Euclidean a => a -> a -> a
`rem` a
b)

  -- | Lowest common multiple. Must satisfy
  --
  -- prop> \x y -> isJust (lcm x y `divide` x) && isJust (lcm x y `divide` y)
  -- prop> \x y z -> isNothing (z `divide` x) || isNothing (z `divide` y) || isJust (z `divide` lcm x y)
  lcm :: a -> a -> a

  default lcm :: Eq a => a -> a -> a
  lcm a
a a
b
    | a -> Bool
forall a. (Eq a, Semiring a) => a -> Bool
isZero a
a Bool -> Bool -> Bool
|| a -> Bool
forall a. (Eq a, Semiring a) => a -> Bool
isZero a
b = a
forall a. Semiring a => a
zero
    | Bool
otherwise = case a
a a -> a -> Maybe a
forall a. GcdDomain a => a -> a -> Maybe a
`divide` a -> a -> a
forall a. GcdDomain a => a -> a -> a
gcd a
a a
b of
      Maybe a
Nothing -> [Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"lcm: violated gcd invariant"
      Just a
c  -> a
c a -> a -> a
forall a. Semiring a => a -> a -> a
* a
b

  -- | Test whether two arguments are
  -- <https://en.wikipedia.org/wiki/Coprime_integers coprime>.
  -- Must match its default definition:
  --
  -- prop> \x y -> coprime x y == isJust (1 `divide` gcd x y)
  coprime :: a -> a -> Bool

  default coprime :: a -> a -> Bool
  coprime a
x a
y = Maybe a -> Bool
forall a. Maybe a -> Bool
isJust (a
forall a. Semiring a => a
one a -> a -> Maybe a
forall a. GcdDomain a => a -> a -> Maybe a
`divide` a -> a -> a
forall a. GcdDomain a => a -> a -> a
gcd a
x a
y)

infixl 7 `divide`

-- | Informally speaking, 'Euclidean' is a superclass of 'Integral',
-- lacking 'toInteger', which allows to define division with remainder
-- for a wider range of types, e. g., complex integers
-- and polynomials with rational coefficients.
--
-- 'Euclidean' represents a
-- <https://en.wikipedia.org/wiki/Euclidean_domain Euclidean domain>
-- endowed by a given Euclidean function 'degree'.
--
-- No particular rounding behaviour is expected of 'quotRem'. E. g.,
-- it is not guaranteed to truncate towards zero or towards negative
-- infinity (cf. 'P.divMod'), and remainders are not guaranteed to be non-negative.
-- For a faithful representation of residue classes one can use
-- <http://hackage.haskell.org/package/mod mod> package instead.
class GcdDomain a => Euclidean a where
  {-# MINIMAL (quotRem | quot, rem), degree #-}
  -- | Division with remainder.
  --
  -- prop> \x y -> y == 0 || let (q, r) = x `quotRem` y in x == q * y + r
  quotRem :: a -> a -> (a, a)
  quotRem a
x a
y = (a -> a -> a
forall a. Euclidean a => a -> a -> a
quot a
x a
y, a -> a -> a
forall a. Euclidean a => a -> a -> a
rem a
x a
y)

  -- | Division. Must match its default definition:
  --
  -- prop> \x y -> quot x y == fst (quotRem x y)
  quot :: a -> a -> a
  quot a
x a
y = (a, a) -> a
forall a b. (a, b) -> a
fst (a -> a -> (a, a)
forall a. Euclidean a => a -> a -> (a, a)
quotRem a
x a
y)

  -- | Remainder. Must match its default definition:
  --
  -- prop> \x y -> rem x y == snd (quotRem x y)
  rem :: a -> a -> a
  rem a
x a
y = (a, a) -> a
forall a b. (a, b) -> b
snd (a -> a -> (a, a)
forall a. Euclidean a => a -> a -> (a, a)
quotRem a
x a
y)

  -- | Euclidean (aka degree, valuation, gauge, norm) function on @a@. Usually @'fromIntegral' '.' 'abs'@.
  --
  -- 'degree' is rarely used by itself. Its purpose
  -- is to provide an evidence of soundness of 'quotRem'
  -- by testing the following property:
  --
  -- prop> \x y -> y == 0 || let (q, r) = x `quotRem` y in (r == 0 || degree r < degree y)
  degree :: a -> Natural

infixl 7 `quot`
infixl 7 `rem`

coprimeIntegral :: Integral a => a -> a -> Bool
coprimeIntegral :: a -> a -> Bool
coprimeIntegral a
x a
y = (a -> Bool
forall a. Integral a => a -> Bool
odd a
x Bool -> Bool -> Bool
|| a -> Bool
forall a. Integral a => a -> Bool
odd a
y) Bool -> Bool -> Bool
&& a -> a -> a
forall a. Integral a => a -> a -> a
P.gcd a
x a
y a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
1

-- | Execute the extended Euclidean algorithm.
-- For elements @a@ and @b@, compute their greatest common divisor @g@
-- and the coefficient @s@ satisfying @as + bt = g@ for some @t@.
gcdExt :: (Eq a, Euclidean a, Ring a) => a -> a -> (a, a)
gcdExt :: a -> a -> (a, a)
gcdExt = a -> a -> a -> a -> (a, a)
forall t. (Eq t, Euclidean t, Ring t) => t -> t -> t -> t -> (t, t)
go a
forall a. Semiring a => a
one a
forall a. Semiring a => a
zero
  where
    go :: t -> t -> t -> t -> (t, t)
go t
s t
s' t
r t
r'
      | t
r' t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
forall a. Semiring a => a
zero = (t
r, t
s)
      | Bool
otherwise  = case t -> t -> (t, t)
forall a. Euclidean a => a -> a -> (a, a)
quotRem t
r t
r' of
        (t
q, t
r'') -> t -> t -> t -> t -> (t, t)
go t
s' (t -> t -> t
forall a. Ring a => a -> a -> a
minus t
s (t -> t -> t
forall a. Semiring a => a -> a -> a
times t
q t
s')) t
r' t
r''
{-# INLINABLE gcdExt #-}

-- | 'Field' represents a
-- <https://en.wikipedia.org/wiki/Field_(mathematics) field>,
-- a ring with a multiplicative inverse for any non-zero element.
class (Euclidean a, Ring a) => Field a

---------------------------------------------------------------------
-- Instances
---------------------------------------------------------------------

instance GcdDomain () where
  divide :: () -> () -> Maybe ()
divide  = (() -> Maybe ()) -> () -> () -> Maybe ()
forall a b. a -> b -> a
const ((() -> Maybe ()) -> () -> () -> Maybe ())
-> (() -> Maybe ()) -> () -> () -> Maybe ()
forall a b. (a -> b) -> a -> b
$ Maybe () -> () -> Maybe ()
forall a b. a -> b -> a
const (() -> Maybe ()
forall a. a -> Maybe a
Just ())
  gcd :: () -> () -> ()
gcd     = (() -> ()) -> () -> () -> ()
forall a b. a -> b -> a
const ((() -> ()) -> () -> () -> ()) -> (() -> ()) -> () -> () -> ()
forall a b. (a -> b) -> a -> b
$ () -> () -> ()
forall a b. a -> b -> a
const ()
  lcm :: () -> () -> ()
lcm     = (() -> ()) -> () -> () -> ()
forall a b. a -> b -> a
const ((() -> ()) -> () -> () -> ()) -> (() -> ()) -> () -> () -> ()
forall a b. (a -> b) -> a -> b
$ () -> () -> ()
forall a b. a -> b -> a
const ()
  coprime :: () -> () -> Bool
coprime = (() -> Bool) -> () -> () -> Bool
forall a b. a -> b -> a
const ((() -> Bool) -> () -> () -> Bool)
-> (() -> Bool) -> () -> () -> Bool
forall a b. (a -> b) -> a -> b
$ Bool -> () -> Bool
forall a b. a -> b -> a
const Bool
True

instance Euclidean () where
  degree :: () -> Natural
degree  = Natural -> () -> Natural
forall a b. a -> b -> a
const Natural
0
  quotRem :: () -> () -> ((), ())
quotRem = (() -> ((), ())) -> () -> () -> ((), ())
forall a b. a -> b -> a
const ((() -> ((), ())) -> () -> () -> ((), ()))
-> (() -> ((), ())) -> () -> () -> ((), ())
forall a b. (a -> b) -> a -> b
$ ((), ()) -> () -> ((), ())
forall a b. a -> b -> a
const ((), ())
  quot :: () -> () -> ()
quot    = (() -> ()) -> () -> () -> ()
forall a b. a -> b -> a
const ((() -> ()) -> () -> () -> ()) -> (() -> ()) -> () -> () -> ()
forall a b. (a -> b) -> a -> b
$ () -> () -> ()
forall a b. a -> b -> a
const ()
  rem :: () -> () -> ()
rem     = (() -> ()) -> () -> () -> ()
forall a b. a -> b -> a
const ((() -> ()) -> () -> () -> ()) -> (() -> ()) -> () -> () -> ()
forall a b. (a -> b) -> a -> b
$ () -> () -> ()
forall a b. a -> b -> a
const ()

instance Field ()

instance GcdDomain Mod2 where

instance Euclidean Mod2 where
  degree :: Mod2 -> Natural
degree = Natural -> Mod2 -> Natural
forall a b. a -> b -> a
const Natural
0
  quotRem :: Mod2 -> Mod2 -> (Mod2, Mod2)
quotRem Mod2
x Mod2
y
    | Mod2 -> Bool
forall a. (Eq a, Semiring a) => a -> Bool
isZero Mod2
y  = ArithException -> (Mod2, Mod2)
forall a e. Exception e => e -> a
throw ArithException
DivideByZero
    | Bool
otherwise = (Mod2
x, Mod2
forall a. Semiring a => a
zero)

instance Field Mod2

-- | Wrapper around 'Integral' with 'GcdDomain'
-- and 'Euclidean' instances.
newtype WrappedIntegral a = WrapIntegral { WrappedIntegral a -> a
unwrapIntegral :: a }
  deriving (WrappedIntegral a -> WrappedIntegral a -> Bool
(WrappedIntegral a -> WrappedIntegral a -> Bool)
-> (WrappedIntegral a -> WrappedIntegral a -> Bool)
-> Eq (WrappedIntegral a)
forall a. Eq a => WrappedIntegral a -> WrappedIntegral a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: WrappedIntegral a -> WrappedIntegral a -> Bool
$c/= :: forall a. Eq a => WrappedIntegral a -> WrappedIntegral a -> Bool
== :: WrappedIntegral a -> WrappedIntegral a -> Bool
$c== :: forall a. Eq a => WrappedIntegral a -> WrappedIntegral a -> Bool
Eq, Eq (WrappedIntegral a)
Eq (WrappedIntegral a)
-> (WrappedIntegral a -> WrappedIntegral a -> Ordering)
-> (WrappedIntegral a -> WrappedIntegral a -> Bool)
-> (WrappedIntegral a -> WrappedIntegral a -> Bool)
-> (WrappedIntegral a -> WrappedIntegral a -> Bool)
-> (WrappedIntegral a -> WrappedIntegral a -> Bool)
-> (WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a)
-> (WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a)
-> Ord (WrappedIntegral a)
WrappedIntegral a -> WrappedIntegral a -> Bool
WrappedIntegral a -> WrappedIntegral a -> Ordering
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
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 a. Ord a => Eq (WrappedIntegral a)
forall a. Ord a => WrappedIntegral a -> WrappedIntegral a -> Bool
forall a.
Ord a =>
WrappedIntegral a -> WrappedIntegral a -> Ordering
forall a.
Ord a =>
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
min :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
$cmin :: forall a.
Ord a =>
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
max :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
$cmax :: forall a.
Ord a =>
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
>= :: WrappedIntegral a -> WrappedIntegral a -> Bool
$c>= :: forall a. Ord a => WrappedIntegral a -> WrappedIntegral a -> Bool
> :: WrappedIntegral a -> WrappedIntegral a -> Bool
$c> :: forall a. Ord a => WrappedIntegral a -> WrappedIntegral a -> Bool
<= :: WrappedIntegral a -> WrappedIntegral a -> Bool
$c<= :: forall a. Ord a => WrappedIntegral a -> WrappedIntegral a -> Bool
< :: WrappedIntegral a -> WrappedIntegral a -> Bool
$c< :: forall a. Ord a => WrappedIntegral a -> WrappedIntegral a -> Bool
compare :: WrappedIntegral a -> WrappedIntegral a -> Ordering
$ccompare :: forall a.
Ord a =>
WrappedIntegral a -> WrappedIntegral a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (WrappedIntegral a)
Ord, Int -> WrappedIntegral a -> ShowS
[WrappedIntegral a] -> ShowS
WrappedIntegral a -> [Char]
(Int -> WrappedIntegral a -> ShowS)
-> (WrappedIntegral a -> [Char])
-> ([WrappedIntegral a] -> ShowS)
-> Show (WrappedIntegral a)
forall a. Show a => Int -> WrappedIntegral a -> ShowS
forall a. Show a => [WrappedIntegral a] -> ShowS
forall a. Show a => WrappedIntegral a -> [Char]
forall a.
(Int -> a -> ShowS) -> (a -> [Char]) -> ([a] -> ShowS) -> Show a
showList :: [WrappedIntegral a] -> ShowS
$cshowList :: forall a. Show a => [WrappedIntegral a] -> ShowS
show :: WrappedIntegral a -> [Char]
$cshow :: forall a. Show a => WrappedIntegral a -> [Char]
showsPrec :: Int -> WrappedIntegral a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> WrappedIntegral a -> ShowS
Show, Integer -> WrappedIntegral a
WrappedIntegral a -> WrappedIntegral a
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
(WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a)
-> (WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a)
-> (WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a)
-> (WrappedIntegral a -> WrappedIntegral a)
-> (WrappedIntegral a -> WrappedIntegral a)
-> (WrappedIntegral a -> WrappedIntegral a)
-> (Integer -> WrappedIntegral a)
-> Num (WrappedIntegral a)
forall a. Num a => Integer -> WrappedIntegral a
forall a. Num a => WrappedIntegral a -> WrappedIntegral a
forall a.
Num a =>
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
forall a.
(a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a)
-> (a -> a)
-> (a -> a)
-> (Integer -> a)
-> Num a
fromInteger :: Integer -> WrappedIntegral a
$cfromInteger :: forall a. Num a => Integer -> WrappedIntegral a
signum :: WrappedIntegral a -> WrappedIntegral a
$csignum :: forall a. Num a => WrappedIntegral a -> WrappedIntegral a
abs :: WrappedIntegral a -> WrappedIntegral a
$cabs :: forall a. Num a => WrappedIntegral a -> WrappedIntegral a
negate :: WrappedIntegral a -> WrappedIntegral a
$cnegate :: forall a. Num a => WrappedIntegral a -> WrappedIntegral a
* :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
$c* :: forall a.
Num a =>
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
- :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
$c- :: forall a.
Num a =>
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
+ :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
$c+ :: forall a.
Num a =>
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
Num, Enum (WrappedIntegral a)
Real (WrappedIntegral a)
Real (WrappedIntegral a)
-> Enum (WrappedIntegral a)
-> (WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a)
-> (WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a)
-> (WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a)
-> (WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a)
-> (WrappedIntegral a
    -> WrappedIntegral a -> (WrappedIntegral a, WrappedIntegral a))
-> (WrappedIntegral a
    -> WrappedIntegral a -> (WrappedIntegral a, WrappedIntegral a))
-> (WrappedIntegral a -> Integer)
-> Integral (WrappedIntegral a)
WrappedIntegral a -> Integer
WrappedIntegral a
-> WrappedIntegral a -> (WrappedIntegral a, WrappedIntegral a)
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
forall a. Integral a => Enum (WrappedIntegral a)
forall a. Integral a => Real (WrappedIntegral a)
forall a. Integral a => WrappedIntegral a -> Integer
forall a.
Integral a =>
WrappedIntegral a
-> WrappedIntegral a -> (WrappedIntegral a, WrappedIntegral a)
forall a.
Integral a =>
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
forall a.
Real a
-> Enum a
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> (a, a))
-> (a -> a -> (a, a))
-> (a -> Integer)
-> Integral a
toInteger :: WrappedIntegral a -> Integer
$ctoInteger :: forall a. Integral a => WrappedIntegral a -> Integer
divMod :: WrappedIntegral a
-> WrappedIntegral a -> (WrappedIntegral a, WrappedIntegral a)
$cdivMod :: forall a.
Integral a =>
WrappedIntegral a
-> WrappedIntegral a -> (WrappedIntegral a, WrappedIntegral a)
quotRem :: WrappedIntegral a
-> WrappedIntegral a -> (WrappedIntegral a, WrappedIntegral a)
$cquotRem :: forall a.
Integral a =>
WrappedIntegral a
-> WrappedIntegral a -> (WrappedIntegral a, WrappedIntegral a)
mod :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
$cmod :: forall a.
Integral a =>
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
div :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
$cdiv :: forall a.
Integral a =>
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
rem :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
$crem :: forall a.
Integral a =>
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
quot :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
$cquot :: forall a.
Integral a =>
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
$cp2Integral :: forall a. Integral a => Enum (WrappedIntegral a)
$cp1Integral :: forall a. Integral a => Real (WrappedIntegral a)
Integral, Num (WrappedIntegral a)
Ord (WrappedIntegral a)
Num (WrappedIntegral a)
-> Ord (WrappedIntegral a)
-> (WrappedIntegral a -> Rational)
-> Real (WrappedIntegral a)
WrappedIntegral a -> Rational
forall a. Num a -> Ord a -> (a -> Rational) -> Real a
forall a. Real a => Num (WrappedIntegral a)
forall a. Real a => Ord (WrappedIntegral a)
forall a. Real a => WrappedIntegral a -> Rational
toRational :: WrappedIntegral a -> Rational
$ctoRational :: forall a. Real a => WrappedIntegral a -> Rational
$cp2Real :: forall a. Real a => Ord (WrappedIntegral a)
$cp1Real :: forall a. Real a => Num (WrappedIntegral a)
Real, Int -> WrappedIntegral a
WrappedIntegral a -> Int
WrappedIntegral a -> [WrappedIntegral a]
WrappedIntegral a -> WrappedIntegral a
WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a]
WrappedIntegral a
-> WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a]
(WrappedIntegral a -> WrappedIntegral a)
-> (WrappedIntegral a -> WrappedIntegral a)
-> (Int -> WrappedIntegral a)
-> (WrappedIntegral a -> Int)
-> (WrappedIntegral a -> [WrappedIntegral a])
-> (WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a])
-> (WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a])
-> (WrappedIntegral a
    -> WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a])
-> Enum (WrappedIntegral a)
forall a. Enum a => Int -> WrappedIntegral a
forall a. Enum a => WrappedIntegral a -> Int
forall a. Enum a => WrappedIntegral a -> [WrappedIntegral a]
forall a. Enum a => WrappedIntegral a -> WrappedIntegral a
forall a.
Enum a =>
WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a]
forall a.
Enum a =>
WrappedIntegral a
-> WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a]
forall a.
(a -> a)
-> (a -> a)
-> (Int -> a)
-> (a -> Int)
-> (a -> [a])
-> (a -> a -> [a])
-> (a -> a -> [a])
-> (a -> a -> a -> [a])
-> Enum a
enumFromThenTo :: WrappedIntegral a
-> WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a]
$cenumFromThenTo :: forall a.
Enum a =>
WrappedIntegral a
-> WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a]
enumFromTo :: WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a]
$cenumFromTo :: forall a.
Enum a =>
WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a]
enumFromThen :: WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a]
$cenumFromThen :: forall a.
Enum a =>
WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a]
enumFrom :: WrappedIntegral a -> [WrappedIntegral a]
$cenumFrom :: forall a. Enum a => WrappedIntegral a -> [WrappedIntegral a]
fromEnum :: WrappedIntegral a -> Int
$cfromEnum :: forall a. Enum a => WrappedIntegral a -> Int
toEnum :: Int -> WrappedIntegral a
$ctoEnum :: forall a. Enum a => Int -> WrappedIntegral a
pred :: WrappedIntegral a -> WrappedIntegral a
$cpred :: forall a. Enum a => WrappedIntegral a -> WrappedIntegral a
succ :: WrappedIntegral a -> WrappedIntegral a
$csucc :: forall a. Enum a => WrappedIntegral a -> WrappedIntegral a
Enum, Eq (WrappedIntegral a)
WrappedIntegral a
Eq (WrappedIntegral a)
-> (WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a)
-> (WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a)
-> (WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a)
-> (WrappedIntegral a -> WrappedIntegral a)
-> (WrappedIntegral a -> Int -> WrappedIntegral a)
-> (WrappedIntegral a -> Int -> WrappedIntegral a)
-> WrappedIntegral a
-> (Int -> WrappedIntegral a)
-> (WrappedIntegral a -> Int -> WrappedIntegral a)
-> (WrappedIntegral a -> Int -> WrappedIntegral a)
-> (WrappedIntegral a -> Int -> WrappedIntegral a)
-> (WrappedIntegral a -> Int -> Bool)
-> (WrappedIntegral a -> Maybe Int)
-> (WrappedIntegral a -> Int)
-> (WrappedIntegral a -> Bool)
-> (WrappedIntegral a -> Int -> WrappedIntegral a)
-> (WrappedIntegral a -> Int -> WrappedIntegral a)
-> (WrappedIntegral a -> Int -> WrappedIntegral a)
-> (WrappedIntegral a -> Int -> WrappedIntegral a)
-> (WrappedIntegral a -> Int -> WrappedIntegral a)
-> (WrappedIntegral a -> Int -> WrappedIntegral a)
-> (WrappedIntegral a -> Int)
-> Bits (WrappedIntegral a)
Int -> WrappedIntegral a
WrappedIntegral a -> Bool
WrappedIntegral a -> Int
WrappedIntegral a -> Maybe Int
WrappedIntegral a -> WrappedIntegral a
WrappedIntegral a -> Int -> Bool
WrappedIntegral a -> Int -> WrappedIntegral a
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
forall a.
Eq a
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> a
-> (Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> Bool)
-> (a -> Maybe Int)
-> (a -> Int)
-> (a -> Bool)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int)
-> Bits a
forall a. Bits a => Eq (WrappedIntegral a)
forall a. Bits a => WrappedIntegral a
forall a. Bits a => Int -> WrappedIntegral a
forall a. Bits a => WrappedIntegral a -> Bool
forall a. Bits a => WrappedIntegral a -> Int
forall a. Bits a => WrappedIntegral a -> Maybe Int
forall a. Bits a => WrappedIntegral a -> WrappedIntegral a
forall a. Bits a => WrappedIntegral a -> Int -> Bool
forall a. Bits a => WrappedIntegral a -> Int -> WrappedIntegral a
forall a.
Bits a =>
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
popCount :: WrappedIntegral a -> Int
$cpopCount :: forall a. Bits a => WrappedIntegral a -> Int
rotateR :: WrappedIntegral a -> Int -> WrappedIntegral a
$crotateR :: forall a. Bits a => WrappedIntegral a -> Int -> WrappedIntegral a
rotateL :: WrappedIntegral a -> Int -> WrappedIntegral a
$crotateL :: forall a. Bits a => WrappedIntegral a -> Int -> WrappedIntegral a
unsafeShiftR :: WrappedIntegral a -> Int -> WrappedIntegral a
$cunsafeShiftR :: forall a. Bits a => WrappedIntegral a -> Int -> WrappedIntegral a
shiftR :: WrappedIntegral a -> Int -> WrappedIntegral a
$cshiftR :: forall a. Bits a => WrappedIntegral a -> Int -> WrappedIntegral a
unsafeShiftL :: WrappedIntegral a -> Int -> WrappedIntegral a
$cunsafeShiftL :: forall a. Bits a => WrappedIntegral a -> Int -> WrappedIntegral a
shiftL :: WrappedIntegral a -> Int -> WrappedIntegral a
$cshiftL :: forall a. Bits a => WrappedIntegral a -> Int -> WrappedIntegral a
isSigned :: WrappedIntegral a -> Bool
$cisSigned :: forall a. Bits a => WrappedIntegral a -> Bool
bitSize :: WrappedIntegral a -> Int
$cbitSize :: forall a. Bits a => WrappedIntegral a -> Int
bitSizeMaybe :: WrappedIntegral a -> Maybe Int
$cbitSizeMaybe :: forall a. Bits a => WrappedIntegral a -> Maybe Int
testBit :: WrappedIntegral a -> Int -> Bool
$ctestBit :: forall a. Bits a => WrappedIntegral a -> Int -> Bool
complementBit :: WrappedIntegral a -> Int -> WrappedIntegral a
$ccomplementBit :: forall a. Bits a => WrappedIntegral a -> Int -> WrappedIntegral a
clearBit :: WrappedIntegral a -> Int -> WrappedIntegral a
$cclearBit :: forall a. Bits a => WrappedIntegral a -> Int -> WrappedIntegral a
setBit :: WrappedIntegral a -> Int -> WrappedIntegral a
$csetBit :: forall a. Bits a => WrappedIntegral a -> Int -> WrappedIntegral a
bit :: Int -> WrappedIntegral a
$cbit :: forall a. Bits a => Int -> WrappedIntegral a
zeroBits :: WrappedIntegral a
$czeroBits :: forall a. Bits a => WrappedIntegral a
rotate :: WrappedIntegral a -> Int -> WrappedIntegral a
$crotate :: forall a. Bits a => WrappedIntegral a -> Int -> WrappedIntegral a
shift :: WrappedIntegral a -> Int -> WrappedIntegral a
$cshift :: forall a. Bits a => WrappedIntegral a -> Int -> WrappedIntegral a
complement :: WrappedIntegral a -> WrappedIntegral a
$ccomplement :: forall a. Bits a => WrappedIntegral a -> WrappedIntegral a
xor :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
$cxor :: forall a.
Bits a =>
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
.|. :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
$c.|. :: forall a.
Bits a =>
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
.&. :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
$c.&. :: forall a.
Bits a =>
WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
$cp1Bits :: forall a. Bits a => Eq (WrappedIntegral a)
Bits)

instance Num a => Semiring (WrappedIntegral a) where
  plus :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
plus  = WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
forall a. Num a => a -> a -> a
(P.+)
  zero :: WrappedIntegral a
zero  = WrappedIntegral a
0
  times :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
times = WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
forall a. Num a => a -> a -> a
(P.*)
  one :: WrappedIntegral a
one   = WrappedIntegral a
1
  fromNatural :: Natural -> WrappedIntegral a
fromNatural = Natural -> WrappedIntegral a
forall a b. (Integral a, Num b) => a -> b
P.fromIntegral

instance Num a => Ring (WrappedIntegral a) where
  negate :: WrappedIntegral a -> WrappedIntegral a
negate = WrappedIntegral a -> WrappedIntegral a
forall a. Num a => a -> a
P.negate

instance Integral a => GcdDomain (WrappedIntegral a) where
  divide :: WrappedIntegral a -> WrappedIntegral a -> Maybe (WrappedIntegral a)
divide WrappedIntegral a
x WrappedIntegral a
y = case WrappedIntegral a
x WrappedIntegral a
-> WrappedIntegral a -> (WrappedIntegral a, WrappedIntegral a)
forall a. Integral a => a -> a -> (a, a)
`P.quotRem` WrappedIntegral a
y of (WrappedIntegral a
q, WrappedIntegral a
0) -> WrappedIntegral a -> Maybe (WrappedIntegral a)
forall a. a -> Maybe a
Just WrappedIntegral a
q; (WrappedIntegral a, WrappedIntegral a)
_ -> Maybe (WrappedIntegral a)
forall a. Maybe a
Nothing
  gcd :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
gcd     = WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
forall a. Integral a => a -> a -> a
P.gcd
  lcm :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
lcm     = WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
forall a. Integral a => a -> a -> a
P.lcm
  coprime :: WrappedIntegral a -> WrappedIntegral a -> Bool
coprime = WrappedIntegral a -> WrappedIntegral a -> Bool
forall a. Integral a => a -> a -> Bool
coprimeIntegral

instance Integral a => Euclidean (WrappedIntegral a) where
  degree :: WrappedIntegral a -> Natural
degree  = a -> Natural
forall a b. (Integral a, Num b) => a -> b
P.fromIntegral (a -> Natural)
-> (WrappedIntegral a -> a) -> WrappedIntegral a -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a
forall a. Num a => a -> a
abs (a -> a) -> (WrappedIntegral a -> a) -> WrappedIntegral a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. WrappedIntegral a -> a
forall a. WrappedIntegral a -> a
unwrapIntegral
  quotRem :: WrappedIntegral a
-> WrappedIntegral a -> (WrappedIntegral a, WrappedIntegral a)
quotRem = WrappedIntegral a
-> WrappedIntegral a -> (WrappedIntegral a, WrappedIntegral a)
forall a. Integral a => a -> a -> (a, a)
P.quotRem
  quot :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
quot    = WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
forall a. Integral a => a -> a -> a
P.quot
  rem :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
rem     = WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
forall a. Integral a => a -> a -> a
P.rem

-- | Wrapper around 'Fractional'
-- with trivial 'GcdDomain'
-- and 'Euclidean' instances.
newtype WrappedFractional a = WrapFractional { WrappedFractional a -> a
unwrapFractional :: a }
  deriving (WrappedFractional a -> WrappedFractional a -> Bool
(WrappedFractional a -> WrappedFractional a -> Bool)
-> (WrappedFractional a -> WrappedFractional a -> Bool)
-> Eq (WrappedFractional a)
forall a.
Eq a =>
WrappedFractional a -> WrappedFractional a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: WrappedFractional a -> WrappedFractional a -> Bool
$c/= :: forall a.
Eq a =>
WrappedFractional a -> WrappedFractional a -> Bool
== :: WrappedFractional a -> WrappedFractional a -> Bool
$c== :: forall a.
Eq a =>
WrappedFractional a -> WrappedFractional a -> Bool
Eq, Eq (WrappedFractional a)
Eq (WrappedFractional a)
-> (WrappedFractional a -> WrappedFractional a -> Ordering)
-> (WrappedFractional a -> WrappedFractional a -> Bool)
-> (WrappedFractional a -> WrappedFractional a -> Bool)
-> (WrappedFractional a -> WrappedFractional a -> Bool)
-> (WrappedFractional a -> WrappedFractional a -> Bool)
-> (WrappedFractional a
    -> WrappedFractional a -> WrappedFractional a)
-> (WrappedFractional a
    -> WrappedFractional a -> WrappedFractional a)
-> Ord (WrappedFractional a)
WrappedFractional a -> WrappedFractional a -> Bool
WrappedFractional a -> WrappedFractional a -> Ordering
WrappedFractional a -> WrappedFractional a -> WrappedFractional a
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 a. Ord a => Eq (WrappedFractional a)
forall a.
Ord a =>
WrappedFractional a -> WrappedFractional a -> Bool
forall a.
Ord a =>
WrappedFractional a -> WrappedFractional a -> Ordering
forall a.
Ord a =>
WrappedFractional a -> WrappedFractional a -> WrappedFractional a
min :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a
$cmin :: forall a.
Ord a =>
WrappedFractional a -> WrappedFractional a -> WrappedFractional a
max :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a
$cmax :: forall a.
Ord a =>
WrappedFractional a -> WrappedFractional a -> WrappedFractional a
>= :: WrappedFractional a -> WrappedFractional a -> Bool
$c>= :: forall a.
Ord a =>
WrappedFractional a -> WrappedFractional a -> Bool
> :: WrappedFractional a -> WrappedFractional a -> Bool
$c> :: forall a.
Ord a =>
WrappedFractional a -> WrappedFractional a -> Bool
<= :: WrappedFractional a -> WrappedFractional a -> Bool
$c<= :: forall a.
Ord a =>
WrappedFractional a -> WrappedFractional a -> Bool
< :: WrappedFractional a -> WrappedFractional a -> Bool
$c< :: forall a.
Ord a =>
WrappedFractional a -> WrappedFractional a -> Bool
compare :: WrappedFractional a -> WrappedFractional a -> Ordering
$ccompare :: forall a.
Ord a =>
WrappedFractional a -> WrappedFractional a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (WrappedFractional a)
Ord, Int -> WrappedFractional a -> ShowS
[WrappedFractional a] -> ShowS
WrappedFractional a -> [Char]
(Int -> WrappedFractional a -> ShowS)
-> (WrappedFractional a -> [Char])
-> ([WrappedFractional a] -> ShowS)
-> Show (WrappedFractional a)
forall a. Show a => Int -> WrappedFractional a -> ShowS
forall a. Show a => [WrappedFractional a] -> ShowS
forall a. Show a => WrappedFractional a -> [Char]
forall a.
(Int -> a -> ShowS) -> (a -> [Char]) -> ([a] -> ShowS) -> Show a
showList :: [WrappedFractional a] -> ShowS
$cshowList :: forall a. Show a => [WrappedFractional a] -> ShowS
show :: WrappedFractional a -> [Char]
$cshow :: forall a. Show a => WrappedFractional a -> [Char]
showsPrec :: Int -> WrappedFractional a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> WrappedFractional a -> ShowS
Show, Integer -> WrappedFractional a
WrappedFractional a -> WrappedFractional a
WrappedFractional a -> WrappedFractional a -> WrappedFractional a
(WrappedFractional a -> WrappedFractional a -> WrappedFractional a)
-> (WrappedFractional a
    -> WrappedFractional a -> WrappedFractional a)
-> (WrappedFractional a
    -> WrappedFractional a -> WrappedFractional a)
-> (WrappedFractional a -> WrappedFractional a)
-> (WrappedFractional a -> WrappedFractional a)
-> (WrappedFractional a -> WrappedFractional a)
-> (Integer -> WrappedFractional a)
-> Num (WrappedFractional a)
forall a. Num a => Integer -> WrappedFractional a
forall a. Num a => WrappedFractional a -> WrappedFractional a
forall a.
Num a =>
WrappedFractional a -> WrappedFractional a -> WrappedFractional a
forall a.
(a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a)
-> (a -> a)
-> (a -> a)
-> (Integer -> a)
-> Num a
fromInteger :: Integer -> WrappedFractional a
$cfromInteger :: forall a. Num a => Integer -> WrappedFractional a
signum :: WrappedFractional a -> WrappedFractional a
$csignum :: forall a. Num a => WrappedFractional a -> WrappedFractional a
abs :: WrappedFractional a -> WrappedFractional a
$cabs :: forall a. Num a => WrappedFractional a -> WrappedFractional a
negate :: WrappedFractional a -> WrappedFractional a
$cnegate :: forall a. Num a => WrappedFractional a -> WrappedFractional a
* :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a
$c* :: forall a.
Num a =>
WrappedFractional a -> WrappedFractional a -> WrappedFractional a
- :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a
$c- :: forall a.
Num a =>
WrappedFractional a -> WrappedFractional a -> WrappedFractional a
+ :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a
$c+ :: forall a.
Num a =>
WrappedFractional a -> WrappedFractional a -> WrappedFractional a
Num, Num (WrappedFractional a)
Num (WrappedFractional a)
-> (WrappedFractional a
    -> WrappedFractional a -> WrappedFractional a)
-> (WrappedFractional a -> WrappedFractional a)
-> (Rational -> WrappedFractional a)
-> Fractional (WrappedFractional a)
Rational -> WrappedFractional a
WrappedFractional a -> WrappedFractional a
WrappedFractional a -> WrappedFractional a -> WrappedFractional a
forall a. Fractional a => Num (WrappedFractional a)
forall a. Fractional a => Rational -> WrappedFractional a
forall a.
Fractional a =>
WrappedFractional a -> WrappedFractional a
forall a.
Fractional a =>
WrappedFractional a -> WrappedFractional a -> WrappedFractional a
forall a.
Num a
-> (a -> a -> a) -> (a -> a) -> (Rational -> a) -> Fractional a
fromRational :: Rational -> WrappedFractional a
$cfromRational :: forall a. Fractional a => Rational -> WrappedFractional a
recip :: WrappedFractional a -> WrappedFractional a
$crecip :: forall a.
Fractional a =>
WrappedFractional a -> WrappedFractional a
/ :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a
$c/ :: forall a.
Fractional a =>
WrappedFractional a -> WrappedFractional a -> WrappedFractional a
$cp1Fractional :: forall a. Fractional a => Num (WrappedFractional a)
Fractional)

instance Num a => Semiring (WrappedFractional a) where
  plus :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a
plus  = WrappedFractional a -> WrappedFractional a -> WrappedFractional a
forall a. Num a => a -> a -> a
(P.+)
  zero :: WrappedFractional a
zero  = WrappedFractional a
0
  times :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a
times = WrappedFractional a -> WrappedFractional a -> WrappedFractional a
forall a. Num a => a -> a -> a
(P.*)
  one :: WrappedFractional a
one   = WrappedFractional a
1
  fromNatural :: Natural -> WrappedFractional a
fromNatural = Natural -> WrappedFractional a
forall a b. (Integral a, Num b) => a -> b
P.fromIntegral

instance Num a => Ring (WrappedFractional a) where
  negate :: WrappedFractional a -> WrappedFractional a
negate = WrappedFractional a -> WrappedFractional a
forall a. Num a => a -> a
P.negate

instance Fractional a => GcdDomain (WrappedFractional a) where
  divide :: WrappedFractional a
-> WrappedFractional a -> Maybe (WrappedFractional a)
divide WrappedFractional a
x WrappedFractional a
y = WrappedFractional a -> Maybe (WrappedFractional a)
forall a. a -> Maybe a
Just (WrappedFractional a
x WrappedFractional a -> WrappedFractional a -> WrappedFractional a
forall a. Fractional a => a -> a -> a
/ WrappedFractional a
y)
  gcd :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a
gcd        = (WrappedFractional a -> WrappedFractional a)
-> WrappedFractional a
-> WrappedFractional a
-> WrappedFractional a
forall a b. a -> b -> a
const ((WrappedFractional a -> WrappedFractional a)
 -> WrappedFractional a
 -> WrappedFractional a
 -> WrappedFractional a)
-> (WrappedFractional a -> WrappedFractional a)
-> WrappedFractional a
-> WrappedFractional a
-> WrappedFractional a
forall a b. (a -> b) -> a -> b
$ WrappedFractional a -> WrappedFractional a -> WrappedFractional a
forall a b. a -> b -> a
const WrappedFractional a
1
  lcm :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a
lcm        = (WrappedFractional a -> WrappedFractional a)
-> WrappedFractional a
-> WrappedFractional a
-> WrappedFractional a
forall a b. a -> b -> a
const ((WrappedFractional a -> WrappedFractional a)
 -> WrappedFractional a
 -> WrappedFractional a
 -> WrappedFractional a)
-> (WrappedFractional a -> WrappedFractional a)
-> WrappedFractional a
-> WrappedFractional a
-> WrappedFractional a
forall a b. (a -> b) -> a -> b
$ WrappedFractional a -> WrappedFractional a -> WrappedFractional a
forall a b. a -> b -> a
const WrappedFractional a
1
  coprime :: WrappedFractional a -> WrappedFractional a -> Bool
coprime    = (WrappedFractional a -> Bool)
-> WrappedFractional a -> WrappedFractional a -> Bool
forall a b. a -> b -> a
const ((WrappedFractional a -> Bool)
 -> WrappedFractional a -> WrappedFractional a -> Bool)
-> (WrappedFractional a -> Bool)
-> WrappedFractional a
-> WrappedFractional a
-> Bool
forall a b. (a -> b) -> a -> b
$ Bool -> WrappedFractional a -> Bool
forall a b. a -> b -> a
const Bool
True

instance Fractional a => Euclidean (WrappedFractional a) where
  degree :: WrappedFractional a -> Natural
degree      = Natural -> WrappedFractional a -> Natural
forall a b. a -> b -> a
const Natural
0
  quotRem :: WrappedFractional a
-> WrappedFractional a
-> (WrappedFractional a, WrappedFractional a)
quotRem WrappedFractional a
x WrappedFractional a
y = (WrappedFractional a
x WrappedFractional a -> WrappedFractional a -> WrappedFractional a
forall a. Fractional a => a -> a -> a
/ WrappedFractional a
y, WrappedFractional a
0)
  quot :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a
quot        = WrappedFractional a -> WrappedFractional a -> WrappedFractional a
forall a. Fractional a => a -> a -> a
(/)
  rem :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a
rem         = (WrappedFractional a -> WrappedFractional a)
-> WrappedFractional a
-> WrappedFractional a
-> WrappedFractional a
forall a b. a -> b -> a
const ((WrappedFractional a -> WrappedFractional a)
 -> WrappedFractional a
 -> WrappedFractional a
 -> WrappedFractional a)
-> (WrappedFractional a -> WrappedFractional a)
-> WrappedFractional a
-> WrappedFractional a
-> WrappedFractional a
forall a b. (a -> b) -> a -> b
$ WrappedFractional a -> WrappedFractional a -> WrappedFractional a
forall a b. a -> b -> a
const WrappedFractional a
0

instance Fractional a => Field (WrappedFractional a)

instance Integral a => GcdDomain (Ratio a) where
  divide :: Ratio a -> Ratio a -> Maybe (Ratio a)
divide Ratio a
x Ratio a
y = Ratio a -> Maybe (Ratio a)
forall a. a -> Maybe a
Just (Ratio a
x Ratio a -> Ratio a -> Ratio a
forall a. Fractional a => a -> a -> a
/ Ratio a
y)
  gcd :: Ratio a -> Ratio a -> Ratio a
gcd        = (Ratio a -> Ratio a) -> Ratio a -> Ratio a -> Ratio a
forall a b. a -> b -> a
const ((Ratio a -> Ratio a) -> Ratio a -> Ratio a -> Ratio a)
-> (Ratio a -> Ratio a) -> Ratio a -> Ratio a -> Ratio a
forall a b. (a -> b) -> a -> b
$ Ratio a -> Ratio a -> Ratio a
forall a b. a -> b -> a
const Ratio a
1
  lcm :: Ratio a -> Ratio a -> Ratio a
lcm        = (Ratio a -> Ratio a) -> Ratio a -> Ratio a -> Ratio a
forall a b. a -> b -> a
const ((Ratio a -> Ratio a) -> Ratio a -> Ratio a -> Ratio a)
-> (Ratio a -> Ratio a) -> Ratio a -> Ratio a -> Ratio a
forall a b. (a -> b) -> a -> b
$ Ratio a -> Ratio a -> Ratio a
forall a b. a -> b -> a
const Ratio a
1
  coprime :: Ratio a -> Ratio a -> Bool
coprime    = (Ratio a -> Bool) -> Ratio a -> Ratio a -> Bool
forall a b. a -> b -> a
const ((Ratio a -> Bool) -> Ratio a -> Ratio a -> Bool)
-> (Ratio a -> Bool) -> Ratio a -> Ratio a -> Bool
forall a b. (a -> b) -> a -> b
$ Bool -> Ratio a -> Bool
forall a b. a -> b -> a
const Bool
True

instance Integral a => Euclidean (Ratio a) where
  degree :: Ratio a -> Natural
degree      = Natural -> Ratio a -> Natural
forall a b. a -> b -> a
const Natural
0
  quotRem :: Ratio a -> Ratio a -> (Ratio a, Ratio a)
quotRem Ratio a
x Ratio a
y = (Ratio a
x Ratio a -> Ratio a -> Ratio a
forall a. Fractional a => a -> a -> a
/ Ratio a
y, Ratio a
0)
  quot :: Ratio a -> Ratio a -> Ratio a
quot        = Ratio a -> Ratio a -> Ratio a
forall a. Fractional a => a -> a -> a
(/)
  rem :: Ratio a -> Ratio a -> Ratio a
rem         = (Ratio a -> Ratio a) -> Ratio a -> Ratio a -> Ratio a
forall a b. a -> b -> a
const ((Ratio a -> Ratio a) -> Ratio a -> Ratio a -> Ratio a)
-> (Ratio a -> Ratio a) -> Ratio a -> Ratio a -> Ratio a
forall a b. (a -> b) -> a -> b
$ Ratio a -> Ratio a -> Ratio a
forall a b. a -> b -> a
const Ratio a
0

instance Integral a => Field (Ratio a)

instance GcdDomain Float where
  divide :: Float -> Float -> Maybe Float
divide Float
x Float
y = Float -> Maybe Float
forall a. a -> Maybe a
Just (Float
x Float -> Float -> Float
forall a. Fractional a => a -> a -> a
/ Float
y)
  gcd :: Float -> Float -> Float
gcd        = (Float -> Float) -> Float -> Float -> Float
forall a b. a -> b -> a
const ((Float -> Float) -> Float -> Float -> Float)
-> (Float -> Float) -> Float -> Float -> Float
forall a b. (a -> b) -> a -> b
$ Float -> Float -> Float
forall a b. a -> b -> a
const Float
1
  lcm :: Float -> Float -> Float
lcm        = (Float -> Float) -> Float -> Float -> Float
forall a b. a -> b -> a
const ((Float -> Float) -> Float -> Float -> Float)
-> (Float -> Float) -> Float -> Float -> Float
forall a b. (a -> b) -> a -> b
$ Float -> Float -> Float
forall a b. a -> b -> a
const Float
1
  coprime :: Float -> Float -> Bool
coprime    = (Float -> Bool) -> Float -> Float -> Bool
forall a b. a -> b -> a
const ((Float -> Bool) -> Float -> Float -> Bool)
-> (Float -> Bool) -> Float -> Float -> Bool
forall a b. (a -> b) -> a -> b
$ Bool -> Float -> Bool
forall a b. a -> b -> a
const Bool
True

instance Euclidean Float where
  degree :: Float -> Natural
degree      = Natural -> Float -> Natural
forall a b. a -> b -> a
const Natural
0
  quotRem :: Float -> Float -> (Float, Float)
quotRem Float
x Float
y = (Float
x Float -> Float -> Float
forall a. Fractional a => a -> a -> a
/ Float
y, Float
0)
  quot :: Float -> Float -> Float
quot        = Float -> Float -> Float
forall a. Fractional a => a -> a -> a
(/)
  rem :: Float -> Float -> Float
rem         = (Float -> Float) -> Float -> Float -> Float
forall a b. a -> b -> a
const ((Float -> Float) -> Float -> Float -> Float)
-> (Float -> Float) -> Float -> Float -> Float
forall a b. (a -> b) -> a -> b
$ Float -> Float -> Float
forall a b. a -> b -> a
const Float
0

instance Field Float

instance GcdDomain Double where
  divide :: Double -> Double -> Maybe Double
divide Double
x Double
y = Double -> Maybe Double
forall a. a -> Maybe a
Just (Double
x Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
y)
  gcd :: Double -> Double -> Double
gcd        = (Double -> Double) -> Double -> Double -> Double
forall a b. a -> b -> a
const ((Double -> Double) -> Double -> Double -> Double)
-> (Double -> Double) -> Double -> Double -> Double
forall a b. (a -> b) -> a -> b
$ Double -> Double -> Double
forall a b. a -> b -> a
const Double
1
  lcm :: Double -> Double -> Double
lcm        = (Double -> Double) -> Double -> Double -> Double
forall a b. a -> b -> a
const ((Double -> Double) -> Double -> Double -> Double)
-> (Double -> Double) -> Double -> Double -> Double
forall a b. (a -> b) -> a -> b
$ Double -> Double -> Double
forall a b. a -> b -> a
const Double
1
  coprime :: Double -> Double -> Bool
coprime    = (Double -> Bool) -> Double -> Double -> Bool
forall a b. a -> b -> a
const ((Double -> Bool) -> Double -> Double -> Bool)
-> (Double -> Bool) -> Double -> Double -> Bool
forall a b. (a -> b) -> a -> b
$ Bool -> Double -> Bool
forall a b. a -> b -> a
const Bool
True

instance Euclidean Double where
  degree :: Double -> Natural
degree      = Natural -> Double -> Natural
forall a b. a -> b -> a
const Natural
0
  quotRem :: Double -> Double -> (Double, Double)
quotRem Double
x Double
y = (Double
x Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/ Double
y, Double
0)
  quot :: Double -> Double -> Double
quot        = Double -> Double -> Double
forall a. Fractional a => a -> a -> a
(/)
  rem :: Double -> Double -> Double
rem         = (Double -> Double) -> Double -> Double -> Double
forall a b. a -> b -> a
const ((Double -> Double) -> Double -> Double -> Double)
-> (Double -> Double) -> Double -> Double -> Double
forall a b. (a -> b) -> a -> b
$ Double -> Double -> Double
forall a b. a -> b -> a
const Double
0

instance Field Double

instance GcdDomain CFloat where
  divide :: CFloat -> CFloat -> Maybe CFloat
divide CFloat
x CFloat
y = CFloat -> Maybe CFloat
forall a. a -> Maybe a
Just (CFloat
x CFloat -> CFloat -> CFloat
forall a. Fractional a => a -> a -> a
/ CFloat
y)
  gcd :: CFloat -> CFloat -> CFloat
gcd        = (CFloat -> CFloat) -> CFloat -> CFloat -> CFloat
forall a b. a -> b -> a
const ((CFloat -> CFloat) -> CFloat -> CFloat -> CFloat)
-> (CFloat -> CFloat) -> CFloat -> CFloat -> CFloat
forall a b. (a -> b) -> a -> b
$ CFloat -> CFloat -> CFloat
forall a b. a -> b -> a
const CFloat
1
  lcm :: CFloat -> CFloat -> CFloat
lcm        = (CFloat -> CFloat) -> CFloat -> CFloat -> CFloat
forall a b. a -> b -> a
const ((CFloat -> CFloat) -> CFloat -> CFloat -> CFloat)
-> (CFloat -> CFloat) -> CFloat -> CFloat -> CFloat
forall a b. (a -> b) -> a -> b
$ CFloat -> CFloat -> CFloat
forall a b. a -> b -> a
const CFloat
1
  coprime :: CFloat -> CFloat -> Bool
coprime    = (CFloat -> Bool) -> CFloat -> CFloat -> Bool
forall a b. a -> b -> a
const ((CFloat -> Bool) -> CFloat -> CFloat -> Bool)
-> (CFloat -> Bool) -> CFloat -> CFloat -> Bool
forall a b. (a -> b) -> a -> b
$ Bool -> CFloat -> Bool
forall a b. a -> b -> a
const Bool
True

instance Euclidean CFloat where
  degree :: CFloat -> Natural
degree      = Natural -> CFloat -> Natural
forall a b. a -> b -> a
const Natural
0
  quotRem :: CFloat -> CFloat -> (CFloat, CFloat)
quotRem CFloat
x CFloat
y = (CFloat
x CFloat -> CFloat -> CFloat
forall a. Fractional a => a -> a -> a
/ CFloat
y, CFloat
0)
  quot :: CFloat -> CFloat -> CFloat
quot        = CFloat -> CFloat -> CFloat
forall a. Fractional a => a -> a -> a
(/)
  rem :: CFloat -> CFloat -> CFloat
rem         = (CFloat -> CFloat) -> CFloat -> CFloat -> CFloat
forall a b. a -> b -> a
const ((CFloat -> CFloat) -> CFloat -> CFloat -> CFloat)
-> (CFloat -> CFloat) -> CFloat -> CFloat -> CFloat
forall a b. (a -> b) -> a -> b
$ CFloat -> CFloat -> CFloat
forall a b. a -> b -> a
const CFloat
0

instance Field CFloat

instance GcdDomain CDouble where
  divide :: CDouble -> CDouble -> Maybe CDouble
divide CDouble
x CDouble
y = CDouble -> Maybe CDouble
forall a. a -> Maybe a
Just (CDouble
x CDouble -> CDouble -> CDouble
forall a. Fractional a => a -> a -> a
/ CDouble
y)
  gcd :: CDouble -> CDouble -> CDouble
gcd        = (CDouble -> CDouble) -> CDouble -> CDouble -> CDouble
forall a b. a -> b -> a
const ((CDouble -> CDouble) -> CDouble -> CDouble -> CDouble)
-> (CDouble -> CDouble) -> CDouble -> CDouble -> CDouble
forall a b. (a -> b) -> a -> b
$ CDouble -> CDouble -> CDouble
forall a b. a -> b -> a
const CDouble
1
  lcm :: CDouble -> CDouble -> CDouble
lcm        = (CDouble -> CDouble) -> CDouble -> CDouble -> CDouble
forall a b. a -> b -> a
const ((CDouble -> CDouble) -> CDouble -> CDouble -> CDouble)
-> (CDouble -> CDouble) -> CDouble -> CDouble -> CDouble
forall a b. (a -> b) -> a -> b
$ CDouble -> CDouble -> CDouble
forall a b. a -> b -> a
const CDouble
1
  coprime :: CDouble -> CDouble -> Bool
coprime    = (CDouble -> Bool) -> CDouble -> CDouble -> Bool
forall a b. a -> b -> a
const ((CDouble -> Bool) -> CDouble -> CDouble -> Bool)
-> (CDouble -> Bool) -> CDouble -> CDouble -> Bool
forall a b. (a -> b) -> a -> b
$ Bool -> CDouble -> Bool
forall a b. a -> b -> a
const Bool
True

instance Euclidean CDouble where
  degree :: CDouble -> Natural
degree      = Natural -> CDouble -> Natural
forall a b. a -> b -> a
const Natural
0
  quotRem :: CDouble -> CDouble -> (CDouble, CDouble)
quotRem CDouble
x CDouble
y = (CDouble
x CDouble -> CDouble -> CDouble
forall a. Fractional a => a -> a -> a
/ CDouble
y, CDouble
0)
  quot :: CDouble -> CDouble -> CDouble
quot        = CDouble -> CDouble -> CDouble
forall a. Fractional a => a -> a -> a
(/)
  rem :: CDouble -> CDouble -> CDouble
rem         = (CDouble -> CDouble) -> CDouble -> CDouble -> CDouble
forall a b. a -> b -> a
const ((CDouble -> CDouble) -> CDouble -> CDouble -> CDouble)
-> (CDouble -> CDouble) -> CDouble -> CDouble -> CDouble
forall a b. (a -> b) -> a -> b
$ CDouble -> CDouble -> CDouble
forall a b. a -> b -> a
const CDouble
0

instance Field CDouble

conjQuotAbs :: Field a => Complex a -> Complex a
conjQuotAbs :: Complex a -> Complex a
conjQuotAbs (a
x :+ a
y) = a
x a -> a -> a
forall a. Euclidean a => a -> a -> a
`quot` a
norm a -> a -> Complex a
forall a. a -> a -> Complex a
:+ (a -> a
forall a. Ring a => a -> a
negate a
y) a -> a -> a
forall a. Euclidean a => a -> a -> a
`quot` a
norm
  where
    norm :: a
norm = (a
x a -> a -> a
forall a. Semiring a => a -> a -> a
`times` a
x) a -> a -> a
forall a. Semiring a => a -> a -> a
`plus` (a
y a -> a -> a
forall a. Semiring a => a -> a -> a
`times` a
y)

instance Field a => GcdDomain (Complex a) where
  divide :: Complex a -> Complex a -> Maybe (Complex a)
divide Complex a
x Complex a
y = Complex a -> Maybe (Complex a)
forall a. a -> Maybe a
Just (Complex a
x Complex a -> Complex a -> Complex a
forall a. Semiring a => a -> a -> a
`times` Complex a -> Complex a
forall a. Field a => Complex a -> Complex a
conjQuotAbs Complex a
y)
  gcd :: Complex a -> Complex a -> Complex a
gcd        = (Complex a -> Complex a) -> Complex a -> Complex a -> Complex a
forall a b. a -> b -> a
const ((Complex a -> Complex a) -> Complex a -> Complex a -> Complex a)
-> (Complex a -> Complex a) -> Complex a -> Complex a -> Complex a
forall a b. (a -> b) -> a -> b
$ Complex a -> Complex a -> Complex a
forall a b. a -> b -> a
const Complex a
forall a. Semiring a => a
one
  lcm :: Complex a -> Complex a -> Complex a
lcm        = (Complex a -> Complex a) -> Complex a -> Complex a -> Complex a
forall a b. a -> b -> a
const ((Complex a -> Complex a) -> Complex a -> Complex a -> Complex a)
-> (Complex a -> Complex a) -> Complex a -> Complex a -> Complex a
forall a b. (a -> b) -> a -> b
$ Complex a -> Complex a -> Complex a
forall a b. a -> b -> a
const Complex a
forall a. Semiring a => a
one
  coprime :: Complex a -> Complex a -> Bool
coprime    = (Complex a -> Bool) -> Complex a -> Complex a -> Bool
forall a b. a -> b -> a
const ((Complex a -> Bool) -> Complex a -> Complex a -> Bool)
-> (Complex a -> Bool) -> Complex a -> Complex a -> Bool
forall a b. (a -> b) -> a -> b
$ Bool -> Complex a -> Bool
forall a b. a -> b -> a
const Bool
True

instance Field a => Euclidean (Complex a) where
  degree :: Complex a -> Natural
degree      = Natural -> Complex a -> Natural
forall a b. a -> b -> a
const Natural
0
  quotRem :: Complex a -> Complex a -> (Complex a, Complex a)
quotRem Complex a
x Complex a
y = (Complex a -> Complex a -> Complex a
forall a. Euclidean a => a -> a -> a
quot Complex a
x Complex a
y, Complex a
forall a. Semiring a => a
zero)
  quot :: Complex a -> Complex a -> Complex a
quot Complex a
x Complex a
y    = Complex a
x Complex a -> Complex a -> Complex a
forall a. Semiring a => a -> a -> a
`times` Complex a -> Complex a
forall a. Field a => Complex a -> Complex a
conjQuotAbs Complex a
y
  rem :: Complex a -> Complex a -> Complex a
rem         = (Complex a -> Complex a) -> Complex a -> Complex a -> Complex a
forall a b. a -> b -> a
const ((Complex a -> Complex a) -> Complex a -> Complex a -> Complex a)
-> (Complex a -> Complex a) -> Complex a -> Complex a -> Complex a
forall a b. (a -> b) -> a -> b
$ Complex a -> Complex a -> Complex a
forall a b. a -> b -> a
const Complex a
forall a. Semiring a => a
zero

instance Field a => Field (Complex a)

#if MIN_VERSION_base(4,12,0)
deriving via (WrappedIntegral Int) instance GcdDomain Int
deriving via (WrappedIntegral Int8) instance GcdDomain Int8
deriving via (WrappedIntegral Int16) instance GcdDomain Int16
deriving via (WrappedIntegral Int32) instance GcdDomain Int32
deriving via (WrappedIntegral Int64) instance GcdDomain Int64
deriving via (WrappedIntegral Integer) instance GcdDomain Integer
deriving via (WrappedIntegral Word) instance GcdDomain Word
deriving via (WrappedIntegral Word8) instance GcdDomain Word8
deriving via (WrappedIntegral Word16) instance GcdDomain Word16
deriving via (WrappedIntegral Word32) instance GcdDomain Word32
deriving via (WrappedIntegral Word64) instance GcdDomain Word64
deriving via (WrappedIntegral Natural) instance GcdDomain Natural
#else
$(let
  deriveGcdDomain :: Q Type -> Q [Dec]
  deriveGcdDomain ty = [d|
      instance GcdDomain $ty where
         gcd     = P.gcd
         lcm     = P.lcm
         coprime = coprimeIntegral
      |]

  in P.concat P.<$> P.traverse deriveGcdDomain
    [[t|Int|]
    ,[t|Int8|]
    ,[t|Int16|]
    ,[t|Int32|]
    ,[t|Int64|]
    ,[t|Integer|]
    ,[t|Word|]
    ,[t|Word8|]
    ,[t|Word16|]
    ,[t|Word32|]
    ,[t|Word64|]
    ,[t|Natural|]
    ])
#endif

#if MIN_VERSION_base(4,12,0)
deriving via (WrappedIntegral Int) instance Euclidean Int
deriving via (WrappedIntegral Int8) instance Euclidean Int8
deriving via (WrappedIntegral Int16) instance Euclidean Int16
deriving via (WrappedIntegral Int32) instance Euclidean Int32
deriving via (WrappedIntegral Int64) instance Euclidean Int64
deriving via (WrappedIntegral Integer) instance Euclidean Integer
deriving via (WrappedIntegral Word) instance Euclidean Word
deriving via (WrappedIntegral Word8) instance Euclidean Word8
deriving via (WrappedIntegral Word16) instance Euclidean Word16
deriving via (WrappedIntegral Word32) instance Euclidean Word32
deriving via (WrappedIntegral Word64) instance Euclidean Word64
deriving via (WrappedIntegral Natural) instance Euclidean Natural
#else
$(let
  deriveEuclidean :: Q Type -> Q [Dec]
  deriveEuclidean ty = [d|
      instance Euclidean $ty where
         degree  = P.fromIntegral . abs
         quotRem = P.quotRem
         quot    = P.quot
         rem     = P.rem
      |]

  in P.concat P.<$> P.traverse deriveEuclidean
    [[t|Int|]
    ,[t|Int8|]
    ,[t|Int16|]
    ,[t|Int32|]
    ,[t|Int64|]
    ,[t|Integer|]
    ,[t|Word|]
    ,[t|Word8|]
    ,[t|Word16|]
    ,[t|Word32|]
    ,[t|Word64|]
    ,[t|Natural|]
    ])
#endif