-- |
-- 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) = forall a. Euclidean a => a -> a -> (a, a)
quotRem a
x a
y in
    if forall a. (Eq a, Semiring a) => a -> Bool
isZero a
r then forall a. a -> Maybe a
Just a
q else 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
    | forall a. (Eq a, Semiring a) => a -> Bool
isZero a
b  = a
a
    | Bool
otherwise = forall a. GcdDomain a => a -> a -> a
gcd a
b (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
    | forall a. (Eq a, Semiring a) => a -> Bool
isZero a
a Bool -> Bool -> Bool
|| forall a. (Eq a, Semiring a) => a -> Bool
isZero a
b = forall a. Semiring a => a
zero
    | Bool
otherwise = case a
a forall a. GcdDomain a => a -> a -> Maybe a
`divide` forall a. GcdDomain a => a -> a -> a
gcd a
a a
b of
      Maybe a
Nothing -> forall a. HasCallStack => [Char] -> a
error [Char]
"lcm: violated gcd invariant"
      Just a
c  -> a
c 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 = 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 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 = (forall a. Euclidean a => a -> a -> a
quot a
x a
y, 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 = forall a b. (a, b) -> a
fst (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 = forall a b. (a, b) -> b
snd (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 :: forall a. Integral a => a -> a -> Bool
coprimeIntegral a
x a
y = (forall a. Integral a => a -> Bool
odd a
x Bool -> Bool -> Bool
|| forall a. Integral a => a -> Bool
odd a
y) Bool -> Bool -> Bool
&& forall a. Integral a => a -> a -> a
P.gcd a
x a
y 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 :: forall a. (Eq a, Euclidean a, Ring a) => a -> a -> (a, a)
gcdExt = forall {t}.
(Eq t, Euclidean t, Ring t) =>
t -> t -> t -> t -> (t, t)
go forall a. Semiring a => a
one 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' forall a. Eq a => a -> a -> Bool
== forall a. Semiring a => a
zero = (t
r, t
s)
      | Bool
otherwise  = case 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' (forall a. Ring a => a -> a -> a
minus t
s (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  = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const (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 = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const Bool
True

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

instance Field Mod2

-- | Wrapper around 'Integral' with 'GcdDomain'
-- and 'Euclidean' instances.
newtype WrappedIntegral a = WrapIntegral { forall a. WrappedIntegral a -> a
unwrapIntegral :: a }
  deriving (WrappedIntegral a -> WrappedIntegral a -> Bool
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, 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
Ord, Int -> WrappedIntegral a -> ShowS
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
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, 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
Integral, 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
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]
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, 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
Bits)

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

instance Num a => Ring (WrappedIntegral a) where
  negate :: WrappedIntegral a -> WrappedIntegral a
negate = 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 forall a. Integral a => a -> a -> (a, a)
`P.quotRem` WrappedIntegral a
y of (WrappedIntegral a
q, WrappedIntegral a
0) -> forall a. a -> Maybe a
Just WrappedIntegral a
q; (WrappedIntegral a, WrappedIntegral a)
_ -> forall a. Maybe a
Nothing
  gcd :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
gcd     = forall a. Integral a => a -> a -> a
P.gcd
  lcm :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a
lcm     = forall a. Integral a => a -> a -> a
P.lcm
  coprime :: WrappedIntegral a -> WrappedIntegral a -> Bool
coprime = forall a. Integral a => a -> a -> Bool
coprimeIntegral

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

-- | Wrapper around 'Fractional'
-- with trivial 'GcdDomain'
-- and 'Euclidean' instances.
newtype WrappedFractional a = WrapFractional { forall a. WrappedFractional a -> a
unwrapFractional :: a }
  deriving (WrappedFractional a -> WrappedFractional a -> Bool
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, 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
Ord, Int -> WrappedFractional a -> ShowS
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
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, 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
Fractional)

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

instance Num a => Ring (WrappedFractional a) where
  negate :: WrappedFractional a -> WrappedFractional a
negate = 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 = forall a. a -> Maybe a
Just (WrappedFractional a
x forall a. Fractional a => a -> a -> a
/ WrappedFractional a
y)
  gcd :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a
gcd        = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const WrappedFractional a
1
  lcm :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a
lcm        = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const WrappedFractional a
1
  coprime :: WrappedFractional a -> WrappedFractional a -> Bool
coprime    = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const Bool
True

instance Fractional a => Euclidean (WrappedFractional a) where
  degree :: WrappedFractional a -> Natural
degree      = 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 forall a. Fractional a => a -> a -> a
/ WrappedFractional a
y, WrappedFractional a
0)
  quot :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a
quot        = forall a. Fractional a => a -> a -> a
(/)
  rem :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a
rem         = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ 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 = forall a. a -> Maybe a
Just (Ratio a
x forall a. Fractional a => a -> a -> a
/ Ratio a
y)
  gcd :: Ratio a -> Ratio a -> Ratio a
gcd        = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const Ratio a
1
  lcm :: Ratio a -> Ratio a -> Ratio a
lcm        = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const Ratio a
1
  coprime :: Ratio a -> Ratio a -> Bool
coprime    = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const Bool
True

instance Integral a => Euclidean (Ratio a) where
  degree :: Ratio a -> Natural
degree      = 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 forall a. Fractional a => a -> a -> a
/ Ratio a
y, Ratio a
0)
  quot :: Ratio a -> Ratio a -> Ratio a
quot        = forall a. Fractional a => a -> a -> a
(/)
  rem :: Ratio a -> Ratio a -> Ratio a
rem         = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ 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 = forall a. a -> Maybe a
Just (Float
x forall a. Fractional a => a -> a -> a
/ Float
y)
  gcd :: Float -> Float -> Float
gcd        = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const Float
1
  lcm :: Float -> Float -> Float
lcm        = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const Float
1
  coprime :: Float -> Float -> Bool
coprime    = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const Bool
True

instance Euclidean Float where
  degree :: Float -> Natural
degree      = forall a b. a -> b -> a
const Natural
0
  quotRem :: Float -> Float -> (Float, Float)
quotRem Float
x Float
y = (Float
x forall a. Fractional a => a -> a -> a
/ Float
y, Float
0)
  quot :: Float -> Float -> Float
quot        = forall a. Fractional a => a -> a -> a
(/)
  rem :: Float -> Float -> Float
rem         = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ 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 = forall a. a -> Maybe a
Just (Double
x forall a. Fractional a => a -> a -> a
/ Double
y)
  gcd :: Double -> Double -> Double
gcd        = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const Double
1
  lcm :: Double -> Double -> Double
lcm        = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const Double
1
  coprime :: Double -> Double -> Bool
coprime    = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const Bool
True

instance Euclidean Double where
  degree :: Double -> Natural
degree      = forall a b. a -> b -> a
const Natural
0
  quotRem :: Double -> Double -> (Double, Double)
quotRem Double
x Double
y = (Double
x forall a. Fractional a => a -> a -> a
/ Double
y, Double
0)
  quot :: Double -> Double -> Double
quot        = forall a. Fractional a => a -> a -> a
(/)
  rem :: Double -> Double -> Double
rem         = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ 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 = forall a. a -> Maybe a
Just (CFloat
x forall a. Fractional a => a -> a -> a
/ CFloat
y)
  gcd :: CFloat -> CFloat -> CFloat
gcd        = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const CFloat
1
  lcm :: CFloat -> CFloat -> CFloat
lcm        = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const CFloat
1
  coprime :: CFloat -> CFloat -> Bool
coprime    = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const Bool
True

instance Euclidean CFloat where
  degree :: CFloat -> Natural
degree      = forall a b. a -> b -> a
const Natural
0
  quotRem :: CFloat -> CFloat -> (CFloat, CFloat)
quotRem CFloat
x CFloat
y = (CFloat
x forall a. Fractional a => a -> a -> a
/ CFloat
y, CFloat
0)
  quot :: CFloat -> CFloat -> CFloat
quot        = forall a. Fractional a => a -> a -> a
(/)
  rem :: CFloat -> CFloat -> CFloat
rem         = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ 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 = forall a. a -> Maybe a
Just (CDouble
x forall a. Fractional a => a -> a -> a
/ CDouble
y)
  gcd :: CDouble -> CDouble -> CDouble
gcd        = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const CDouble
1
  lcm :: CDouble -> CDouble -> CDouble
lcm        = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const CDouble
1
  coprime :: CDouble -> CDouble -> Bool
coprime    = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const Bool
True

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

instance Field CDouble

conjQuotAbs :: Field a => Complex a -> Complex a
conjQuotAbs :: forall a. Field a => Complex a -> Complex a
conjQuotAbs (a
x :+ a
y) = a
x forall a. Euclidean a => a -> a -> a
`quot` a
norm forall a. a -> a -> Complex a
:+ (forall a. Ring a => a -> a
negate a
y) forall a. Euclidean a => a -> a -> a
`quot` a
norm
  where
    norm :: a
norm = (a
x forall a. Semiring a => a -> a -> a
`times` a
x) forall a. Semiring a => a -> a -> a
`plus` (a
y 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 = forall a. a -> Maybe a
Just (Complex a
x forall a. Semiring a => a -> a -> a
`times` forall a. Field a => Complex a -> Complex a
conjQuotAbs Complex a
y)
  gcd :: Complex a -> Complex a -> Complex a
gcd        = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const forall a. Semiring a => a
one
  lcm :: Complex a -> Complex a -> Complex a
lcm        = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const forall a. Semiring a => a
one
  coprime :: Complex a -> Complex a -> Bool
coprime    = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const Bool
True

instance Field a => Euclidean (Complex a) where
  degree :: Complex a -> Natural
degree      = 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 = (forall a. Euclidean a => a -> a -> a
quot Complex a
x Complex a
y, forall a. Semiring a => a
zero)
  quot :: Complex a -> Complex a -> Complex a
quot Complex a
x Complex a
y    = Complex a
x forall a. Semiring a => a -> a -> a
`times` forall a. Field a => Complex a -> Complex a
conjQuotAbs Complex a
y
  rem :: Complex a -> Complex a -> Complex a
rem         = forall a b. a -> b -> a
const forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const 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