semirings-0.7: two monoids as one, in holy haskimony

Copyright | (c) 2019 Andrew Lelechenko
License | BSD3
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell | None
Language | Haskell98

Data.Euclidean

Description

Synopsis

- class GcdDomain a => Euclidean a where
  - quotRem :: a -> a -> (a, a)
  - quot :: a -> a -> a
  - rem :: a -> a -> a
  - degree :: a -> Natural
- class (Euclidean a, Ring a) => Field a
- class Semiring a => GcdDomain a where
  - divide :: a -> a -> Maybe a
  - gcd :: a -> a -> a
  - lcm :: a -> a -> a
  - coprime :: a -> a -> Bool
- newtype WrappedIntegral a = WrapIntegral {
  - unwrapIntegral :: a
  }
- newtype WrappedFractional a = WrapFractional {
  - unwrapFractional :: a
  }
- gcdExt :: (Eq a, Euclidean a, Ring a) => a -> a -> (a, a)

# Documentation

class GcdDomain a => Euclidean a where Source #

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 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. `divMod`), and remainders are not guaranteed to be non-negative. For a faithful representation of residue classes one can use mod package instead.

Minimal complete definition

(quotRem | quot, rem), degree

Methods

quotRem :: a -> a -> (a, a) Source #

Division with remainder.

    \x y -> y == 0 || let (q, r) = x `quotRem` y in x == q * y + r

quot :: a -> a -> a infixl 7 Source #

Division. Must match its default definition:

    \x y -> quot x y == fst (quotRem x y)

rem :: a -> a -> a infixl 7 Source #

Remainder. Must match its default definition:

    \x y -> rem x y == snd (quotRem x y)

degree :: a -> Natural Source #

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:

    \x y -> y == 0 || let (q, r) = x `quotRem` y in (r == 0 || degree r < degree y)

#### Instances

Instances details

Euclidean CDouble Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: CDouble -> CDouble -> (CDouble, CDouble) Source # quot :: CDouble -> CDouble -> CDouble Source # rem :: CDouble -> CDouble -> CDouble Source # degree :: CDouble -> Natural Source #
Euclidean CFloat Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: CFloat -> CFloat -> (CFloat, CFloat) Source # quot :: CFloat -> CFloat -> CFloat Source # rem :: CFloat -> CFloat -> CFloat Source # degree :: CFloat -> Natural Source #
Euclidean Int16 Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: Int16 -> Int16 -> (Int16, Int16) Source # quot :: Int16 -> Int16 -> Int16 Source # rem :: Int16 -> Int16 -> Int16 Source # degree :: Int16 -> Natural Source #
Euclidean Int32 Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: Int32 -> Int32 -> (Int32, Int32) Source # quot :: Int32 -> Int32 -> Int32 Source # rem :: Int32 -> Int32 -> Int32 Source # degree :: Int32 -> Natural Source #
Euclidean Int64 Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: Int64 -> Int64 -> (Int64, Int64) Source # quot :: Int64 -> Int64 -> Int64 Source # rem :: Int64 -> Int64 -> Int64 Source # degree :: Int64 -> Natural Source #
Euclidean Int8 Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: Int8 -> Int8 -> (Int8, Int8) Source # quot :: Int8 -> Int8 -> Int8 Source # rem :: Int8 -> Int8 -> Int8 Source # degree :: Int8 -> Natural Source #
Euclidean Word16 Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: Word16 -> Word16 -> (Word16, Word16) Source # quot :: Word16 -> Word16 -> Word16 Source # rem :: Word16 -> Word16 -> Word16 Source # degree :: Word16 -> Natural Source #
Euclidean Word32 Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: Word32 -> Word32 -> (Word32, Word32) Source # quot :: Word32 -> Word32 -> Word32 Source # rem :: Word32 -> Word32 -> Word32 Source # degree :: Word32 -> Natural Source #
Euclidean Word64 Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: Word64 -> Word64 -> (Word64, Word64) Source # quot :: Word64 -> Word64 -> Word64 Source # rem :: Word64 -> Word64 -> Word64 Source # degree :: Word64 -> Natural Source #
Euclidean Word8 Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: Word8 -> Word8 -> (Word8, Word8) Source # quot :: Word8 -> Word8 -> Word8 Source # rem :: Word8 -> Word8 -> Word8 Source # degree :: Word8 -> Natural Source #
Euclidean Mod2 Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: Mod2 -> Mod2 -> (Mod2, Mod2) Source # quot :: Mod2 -> Mod2 -> Mod2 Source # rem :: Mod2 -> Mod2 -> Mod2 Source # degree :: Mod2 -> Natural Source #
Euclidean Integer Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: Integer -> Integer -> (Integer, Integer) Source # quot :: Integer -> Integer -> Integer Source # rem :: Integer -> Integer -> Integer Source # degree :: Integer -> Natural Source #
Euclidean Natural Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: Natural -> Natural -> (Natural, Natural) Source # quot :: Natural -> Natural -> Natural Source # rem :: Natural -> Natural -> Natural Source # degree :: Natural -> Natural Source #
Euclidean () Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: () -> () -> ((), ()) Source # quot :: () -> () -> () Source # rem :: () -> () -> () Source # degree :: () -> Natural Source #
Euclidean Double Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: Double -> Double -> (Double, Double) Source # quot :: Double -> Double -> Double Source # rem :: Double -> Double -> Double Source # degree :: Double -> Natural Source #
Euclidean Float Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: Float -> Float -> (Float, Float) Source # quot :: Float -> Float -> Float Source # rem :: Float -> Float -> Float Source # degree :: Float -> Natural Source #
Euclidean Int Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: Int -> Int -> (Int, Int) Source # quot :: Int -> Int -> Int Source # rem :: Int -> Int -> Int Source # degree :: Int -> Natural Source #
Euclidean Word Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: Word -> Word -> (Word, Word) Source # quot :: Word -> Word -> Word Source # rem :: Word -> Word -> Word Source # degree :: Word -> Natural Source #
Field a => Euclidean (Complex a) Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: Complex a -> Complex a -> (Complex a, Complex a) Source # quot :: Complex a -> Complex a -> Complex a Source # rem :: Complex a -> Complex a -> Complex a Source # degree :: Complex a -> Natural Source #
Integral a => Euclidean (Ratio a) Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: Ratio a -> Ratio a -> (Ratio a, Ratio a) Source # quot :: Ratio a -> Ratio a -> Ratio a Source # rem :: Ratio a -> Ratio a -> Ratio a Source # degree :: Ratio a -> Natural Source #
Fractional a => Euclidean (WrappedFractional a) Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: WrappedFractional a -> WrappedFractional a -> (WrappedFractional a, WrappedFractional a) Source # quot :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a Source # rem :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a Source # degree :: WrappedFractional a -> Natural Source #
Integral a => Euclidean (WrappedIntegral a) Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: WrappedIntegral a -> WrappedIntegral a -> (WrappedIntegral a, WrappedIntegral a) Source # quot :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source # rem :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source # degree :: WrappedIntegral a -> Natural Source #

class (Euclidean a, Ring a) => Field a Source #

`Field` represents a field, a ring with a multiplicative inverse for any non-zero element.

#### Instances

Instances details

Field CDouble Source # |
Instance details Defined in Data.Euclidean
Field CFloat Source # |
Instance details Defined in Data.Euclidean
Field Mod2 Source # |
Instance details Defined in Data.Euclidean
Field () Source # |
Instance details Defined in Data.Euclidean
Field Double Source # |
Instance details Defined in Data.Euclidean
Field Float Source # |
Instance details Defined in Data.Euclidean
Field a => Field (Complex a) Source # |
Instance details Defined in Data.Euclidean
Integral a => Field (Ratio a) Source # |
Instance details Defined in Data.Euclidean
Fractional a => Field (WrappedFractional a) Source # |
Instance details Defined in Data.Euclidean

class Semiring a => GcdDomain a where Source #

`GcdDomain` represents a 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  = ...

Minimal complete definition

Nothing

Methods

divide :: a -> a -> Maybe a infixl 7 Source #

Division without remainder.

    \x y -> (x * y) `divide` y == Just x

    \x y -> maybe True (\z -> x == z * y) (x `divide` y)

default divide :: (Eq a, Euclidean a) => a -> a -> Maybe a Source #

gcd :: a -> a -> a Source #

Greatest common divisor. Must satisfy

    \x y -> isJust (x `divide` gcd x y) && isJust (y `divide` gcd x y)

    \x y z -> isJust (gcd (x * z) (y * z) `divide` z)

default gcd :: (Eq a, Euclidean a) => a -> a -> a Source #

lcm :: a -> a -> a Source #

Lowest common multiple. Must satisfy

    \x y -> isJust (lcm x y `divide` x) && isJust (lcm x y `divide` y)

    \x y z -> isNothing (z `divide` x) || isNothing (z `divide` y) || isJust (z `divide` lcm x y)

default lcm :: Eq a => a -> a -> a Source #

coprime :: a -> a -> Bool Source #

Test whether two arguments are coprime. Must match its default definition:

    \x y -> coprime x y == isJust (1 `divide` gcd x y)

default coprime :: a -> a -> Bool Source #

#### Instances

Instances details

GcdDomain CDouble Source # |
Instance details Defined in Data.Euclidean Methods divide :: CDouble -> CDouble -> Maybe CDouble Source # gcd :: CDouble -> CDouble -> CDouble Source # lcm :: CDouble -> CDouble -> CDouble Source # coprime :: CDouble -> CDouble -> Bool Source #
GcdDomain CFloat Source # |
Instance details Defined in Data.Euclidean Methods divide :: CFloat -> CFloat -> Maybe CFloat Source # gcd :: CFloat -> CFloat -> CFloat Source # lcm :: CFloat -> CFloat -> CFloat Source # coprime :: CFloat -> CFloat -> Bool Source #
GcdDomain Int16 Source # |
Instance details Defined in Data.Euclidean Methods divide :: Int16 -> Int16 -> Maybe Int16 Source # gcd :: Int16 -> Int16 -> Int16 Source # lcm :: Int16 -> Int16 -> Int16 Source # coprime :: Int16 -> Int16 -> Bool Source #
GcdDomain Int32 Source # |
Instance details Defined in Data.Euclidean Methods divide :: Int32 -> Int32 -> Maybe Int32 Source # gcd :: Int32 -> Int32 -> Int32 Source # lcm :: Int32 -> Int32 -> Int32 Source # coprime :: Int32 -> Int32 -> Bool Source #
GcdDomain Int64 Source # |
Instance details Defined in Data.Euclidean Methods divide :: Int64 -> Int64 -> Maybe Int64 Source # gcd :: Int64 -> Int64 -> Int64 Source # lcm :: Int64 -> Int64 -> Int64 Source # coprime :: Int64 -> Int64 -> Bool Source #
GcdDomain Int8 Source # |
Instance details Defined in Data.Euclidean Methods divide :: Int8 -> Int8 -> Maybe Int8 Source # gcd :: Int8 -> Int8 -> Int8 Source # lcm :: Int8 -> Int8 -> Int8 Source # coprime :: Int8 -> Int8 -> Bool Source #
GcdDomain Word16 Source # |
Instance details Defined in Data.Euclidean Methods divide :: Word16 -> Word16 -> Maybe Word16 Source # gcd :: Word16 -> Word16 -> Word16 Source # lcm :: Word16 -> Word16 -> Word16 Source # coprime :: Word16 -> Word16 -> Bool Source #
GcdDomain Word32 Source # |
Instance details Defined in Data.Euclidean Methods divide :: Word32 -> Word32 -> Maybe Word32 Source # gcd :: Word32 -> Word32 -> Word32 Source # lcm :: Word32 -> Word32 -> Word32 Source # coprime :: Word32 -> Word32 -> Bool Source #
GcdDomain Word64 Source # |
Instance details Defined in Data.Euclidean Methods divide :: Word64 -> Word64 -> Maybe Word64 Source # gcd :: Word64 -> Word64 -> Word64 Source # lcm :: Word64 -> Word64 -> Word64 Source # coprime :: Word64 -> Word64 -> Bool Source #
GcdDomain Word8 Source # |
Instance details Defined in Data.Euclidean Methods divide :: Word8 -> Word8 -> Maybe Word8 Source # gcd :: Word8 -> Word8 -> Word8 Source # lcm :: Word8 -> Word8 -> Word8 Source # coprime :: Word8 -> Word8 -> Bool Source #
GcdDomain Mod2 Source # |
Instance details Defined in Data.Euclidean Methods divide :: Mod2 -> Mod2 -> Maybe Mod2 Source # gcd :: Mod2 -> Mod2 -> Mod2 Source # lcm :: Mod2 -> Mod2 -> Mod2 Source # coprime :: Mod2 -> Mod2 -> Bool Source #
GcdDomain Integer Source # |
Instance details Defined in Data.Euclidean Methods divide :: Integer -> Integer -> Maybe Integer Source # gcd :: Integer -> Integer -> Integer Source # lcm :: Integer -> Integer -> Integer Source # coprime :: Integer -> Integer -> Bool Source #
GcdDomain Natural Source # |
Instance details Defined in Data.Euclidean Methods divide :: Natural -> Natural -> Maybe Natural Source # gcd :: Natural -> Natural -> Natural Source # lcm :: Natural -> Natural -> Natural Source # coprime :: Natural -> Natural -> Bool Source #
GcdDomain () Source # |
Instance details Defined in Data.Euclidean Methods divide :: () -> () -> Maybe () Source # gcd :: () -> () -> () Source # lcm :: () -> () -> () Source # coprime :: () -> () -> Bool Source #
GcdDomain Double Source # |
Instance details Defined in Data.Euclidean Methods divide :: Double -> Double -> Maybe Double Source # gcd :: Double -> Double -> Double Source # lcm :: Double -> Double -> Double Source # coprime :: Double -> Double -> Bool Source #
GcdDomain Float Source # |
Instance details Defined in Data.Euclidean Methods divide :: Float -> Float -> Maybe Float Source # gcd :: Float -> Float -> Float Source # lcm :: Float -> Float -> Float Source # coprime :: Float -> Float -> Bool Source #
GcdDomain Int Source # |
Instance details Defined in Data.Euclidean Methods divide :: Int -> Int -> Maybe Int Source # gcd :: Int -> Int -> Int Source # lcm :: Int -> Int -> Int Source # coprime :: Int -> Int -> Bool Source #
GcdDomain Word Source # |
Instance details Defined in Data.Euclidean Methods divide :: Word -> Word -> Maybe Word Source # gcd :: Word -> Word -> Word Source # lcm :: Word -> Word -> Word Source # coprime :: Word -> Word -> Bool Source #
Field a => GcdDomain (Complex a) Source # |
Instance details Defined in Data.Euclidean Methods divide :: Complex a -> Complex a -> Maybe (Complex a) Source # gcd :: Complex a -> Complex a -> Complex a Source # lcm :: Complex a -> Complex a -> Complex a Source # coprime :: Complex a -> Complex a -> Bool Source #
Integral a => GcdDomain (Ratio a) Source # |
Instance details Defined in Data.Euclidean Methods divide :: Ratio a -> Ratio a -> Maybe (Ratio a) Source # gcd :: Ratio a -> Ratio a -> Ratio a Source # lcm :: Ratio a -> Ratio a -> Ratio a Source # coprime :: Ratio a -> Ratio a -> Bool Source #
Fractional a => GcdDomain (WrappedFractional a) Source # |
Instance details Defined in Data.Euclidean Methods divide :: WrappedFractional a -> WrappedFractional a -> Maybe (WrappedFractional a) Source # gcd :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a Source # lcm :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a Source # coprime :: WrappedFractional a -> WrappedFractional a -> Bool Source #
Integral a => GcdDomain (WrappedIntegral a) Source # |
Instance details Defined in Data.Euclidean Methods divide :: WrappedIntegral a -> WrappedIntegral a -> Maybe (WrappedIntegral a) Source # gcd :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source # lcm :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source # coprime :: WrappedIntegral a -> WrappedIntegral a -> Bool Source #

newtype WrappedIntegral a Source #

Wrapper around `Integral` with `GcdDomain` and `Euclidean` instances.

Constructors

WrapIntegral |

Fields

- unwrapIntegral :: a

#### Instances

Instances details

Bits a => Bits (WrappedIntegral a) Source # |

Instance details

Defined in Data.Euclidean

Methods

(.&.) :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source #

(.|.) :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source #

xor :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source #

complement :: WrappedIntegral a -> WrappedIntegral a Source #

shift :: WrappedIntegral a -> Int -> WrappedIntegral a Source #

rotate :: WrappedIntegral a -> Int -> WrappedIntegral a Source #

zeroBits :: WrappedIntegral a Source #

bit :: Int -> WrappedIntegral a Source #

setBit :: WrappedIntegral a -> Int -> WrappedIntegral a Source #

clearBit :: WrappedIntegral a -> Int -> WrappedIntegral a Source #

complementBit :: WrappedIntegral a -> Int -> WrappedIntegral a Source #

testBit :: WrappedIntegral a -> Int -> Bool Source #

bitSizeMaybe :: WrappedIntegral a -> Maybe Int Source #

bitSize :: WrappedIntegral a -> Int Source #

isSigned :: WrappedIntegral a -> Bool Source #

shiftL :: WrappedIntegral a -> Int -> WrappedIntegral a Source #

unsafeShiftL :: WrappedIntegral a -> Int -> WrappedIntegral a Source #

shiftR :: WrappedIntegral a -> Int -> WrappedIntegral a Source #

unsafeShiftR :: WrappedIntegral a -> Int -> WrappedIntegral a Source #

rotateL :: WrappedIntegral a -> Int -> WrappedIntegral a Source #

rotateR :: WrappedIntegral a -> Int -> WrappedIntegral a Source #

popCount :: WrappedIntegral a -> Int Source #

Enum a => Enum (WrappedIntegral a) Source # |

Instance details

Defined in Data.Euclidean

Methods

succ :: WrappedIntegral a -> WrappedIntegral a Source #

pred :: WrappedIntegral a -> WrappedIntegral a Source #

toEnum :: Int -> WrappedIntegral a Source #

fromEnum :: WrappedIntegral a -> Int Source #

enumFrom :: WrappedIntegral a -> [WrappedIntegral a] Source #

enumFromThen :: WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a] Source #

enumFromTo :: WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a] Source #

enumFromThenTo :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a] Source #

Num a => Num (WrappedIntegral a) Source # |

Instance details

Defined in Data.Euclidean

Methods

(+) :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source #

(-) :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source #

(*) :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source #

negate :: WrappedIntegral a -> WrappedIntegral a Source #

abs :: WrappedIntegral a -> WrappedIntegral a Source #

signum :: WrappedIntegral a -> WrappedIntegral a Source #

fromInteger :: Integer -> WrappedIntegral a Source #

Integral a => Integral (WrappedIntegral a) Source # |

Instance details

Defined in Data.Euclidean

Methods

quot :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source #

rem :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source #

div :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source #

mod :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source #

quotRem :: WrappedIntegral a -> WrappedIntegral a -> (WrappedIntegral a, WrappedIntegral a) Source #

divMod :: WrappedIntegral a -> WrappedIntegral a -> (WrappedIntegral a, WrappedIntegral a) Source #

toInteger :: WrappedIntegral a -> Integer Source #

Real a => Real (WrappedIntegral a) Source # |
Instance details Defined in Data.Euclidean Methods toRational :: WrappedIntegral a -> Rational Source #
Show a => Show (WrappedIntegral a) Source # |
Instance details Defined in Data.Euclidean Methods showsPrec :: Int -> WrappedIntegral a -> ShowS Source # show :: WrappedIntegral a -> String Source # showList :: [WrappedIntegral a] -> ShowS Source #
Eq a => Eq (WrappedIntegral a) Source # |
Instance details Defined in Data.Euclidean Methods (==) :: WrappedIntegral a -> WrappedIntegral a -> Bool Source # (/=) :: WrappedIntegral a -> WrappedIntegral a -> Bool Source #
Ord a => Ord (WrappedIntegral a) Source # |

Instance details

Defined in Data.Euclidean

Methods

compare :: WrappedIntegral a -> WrappedIntegral a -> Ordering Source #

(<) :: WrappedIntegral a -> WrappedIntegral a -> Bool Source #

(<=) :: WrappedIntegral a -> WrappedIntegral a -> Bool Source #

(>) :: WrappedIntegral a -> WrappedIntegral a -> Bool Source #

(>=) :: WrappedIntegral a -> WrappedIntegral a -> Bool Source #

max :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source #

min :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source #

Integral a => Euclidean (WrappedIntegral a) Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: WrappedIntegral a -> WrappedIntegral a -> (WrappedIntegral a, WrappedIntegral a) Source # quot :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source # rem :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source # degree :: WrappedIntegral a -> Natural Source #
Integral a => GcdDomain (WrappedIntegral a) Source # |
Instance details Defined in Data.Euclidean Methods divide :: WrappedIntegral a -> WrappedIntegral a -> Maybe (WrappedIntegral a) Source # gcd :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source # lcm :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source # coprime :: WrappedIntegral a -> WrappedIntegral a -> Bool Source #
Num a => Ring (WrappedIntegral a) Source # |
Instance details Defined in Data.Euclidean Methods negate :: WrappedIntegral a -> WrappedIntegral a Source #
Num a => Semiring (WrappedIntegral a) Source # |
Instance details Defined in Data.Euclidean Methods plus :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source # zero :: WrappedIntegral a Source # times :: WrappedIntegral a -> WrappedIntegral a -> WrappedIntegral a Source # one :: WrappedIntegral a Source # fromNatural :: Natural -> WrappedIntegral a Source #

newtype WrappedFractional a Source #

Wrapper around `Fractional` with trivial `GcdDomain` and `Euclidean` instances.

Constructors

WrapFractional |

Fields

- unwrapFractional :: a

#### Instances

Instances details

Num a => Num (WrappedFractional a) Source # |

Instance details

Defined in Data.Euclidean

Methods

(+) :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a Source #

(-) :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a Source #

(*) :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a Source #

negate :: WrappedFractional a -> WrappedFractional a Source #

abs :: WrappedFractional a -> WrappedFractional a Source #

signum :: WrappedFractional a -> WrappedFractional a Source #

fromInteger :: Integer -> WrappedFractional a Source #

Fractional a => Fractional (WrappedFractional a) Source # |
Instance details Defined in Data.Euclidean Methods (/) :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a Source # recip :: WrappedFractional a -> WrappedFractional a Source # fromRational :: Rational -> WrappedFractional a Source #
Show a => Show (WrappedFractional a) Source # |
Instance details Defined in Data.Euclidean Methods showsPrec :: Int -> WrappedFractional a -> ShowS Source # show :: WrappedFractional a -> String Source # showList :: [WrappedFractional a] -> ShowS Source #
Eq a => Eq (WrappedFractional a) Source # |
Instance details Defined in Data.Euclidean Methods (==) :: WrappedFractional a -> WrappedFractional a -> Bool Source # (/=) :: WrappedFractional a -> WrappedFractional a -> Bool Source #
Ord a => Ord (WrappedFractional a) Source # |

Instance details

Defined in Data.Euclidean

Methods

compare :: WrappedFractional a -> WrappedFractional a -> Ordering Source #

(<) :: WrappedFractional a -> WrappedFractional a -> Bool Source #

(<=) :: WrappedFractional a -> WrappedFractional a -> Bool Source #

(>) :: WrappedFractional a -> WrappedFractional a -> Bool Source #

(>=) :: WrappedFractional a -> WrappedFractional a -> Bool Source #

max :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a Source #

min :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a Source #

Fractional a => Euclidean (WrappedFractional a) Source # |
Instance details Defined in Data.Euclidean Methods quotRem :: WrappedFractional a -> WrappedFractional a -> (WrappedFractional a, WrappedFractional a) Source # quot :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a Source # rem :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a Source # degree :: WrappedFractional a -> Natural Source #
Fractional a => Field (WrappedFractional a) Source # |
Instance details Defined in Data.Euclidean
Fractional a => GcdDomain (WrappedFractional a) Source # |
Instance details Defined in Data.Euclidean Methods divide :: WrappedFractional a -> WrappedFractional a -> Maybe (WrappedFractional a) Source # gcd :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a Source # lcm :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a Source # coprime :: WrappedFractional a -> WrappedFractional a -> Bool Source #
Num a => Ring (WrappedFractional a) Source # |
Instance details Defined in Data.Euclidean Methods negate :: WrappedFractional a -> WrappedFractional a Source #
Num a => Semiring (WrappedFractional a) Source # |
Instance details Defined in Data.Euclidean Methods plus :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a Source # zero :: WrappedFractional a Source # times :: WrappedFractional a -> WrappedFractional a -> WrappedFractional a Source # one :: WrappedFractional a Source # fromNatural :: Natural -> WrappedFractional a Source #

gcdExt :: (Eq a, Euclidean a, Ring a) => a -> a -> (a, a) Source #

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`.