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