HORIZON HASKELLDocslts/ghc-9.10.xc74966e2026-09-27Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · c74966e · 2026-09-27

Modulesemirings-0.7Haskell98

Data.Euclidean

  • 2 types
  • 3 classes
  • 1 value
  • Packagesemirings-0.7
  • Exports6
  • LanguageHaskell98
  • LicenceBSD-3-Clause
  • SourceEuclidean.hs
classclass GcdDomain a => Euclidean a where
#

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.

Methods

  • quotRem :: a -> a -> (a, a)

    Division with remainder.

    Property
    \x y -> y == 0 || let (q, r) = x `quotRem` y in x == q * y + r
  • quot :: a -> a -> ainfixl 7

    Division. Must match its default definition:

    Property
    \x y -> quot x y == fst (quotRem x y)
  • rem :: a -> a -> ainfixl 7

    Remainder. Must match its default definition:

    Property
    \x y -> rem x y == snd (quotRem x y)
  • degree :: a -> Natural

    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:

    Property
    \x y -> y == 0 || let (q, r) = x `quotRem` y in (r == 0 || degree r < degree y)
Instances22Euclidean, …
classclass (Euclidean a, Ring a) => Field a
#

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

Instances9Field, …
classclass Semiring a => GcdDomain a where
#

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

Methods

  • divide :: a -> a -> Maybe ainfixl 7

    Division without remainder.

    Property
    \x y -> (x * y) `divide` y == Just x
    Property
    \x y -> maybe True (\z -> x == z * y) (x `divide` y)
  • gcd :: a -> a -> a

    Greatest common divisor. Must satisfy

    Property
    \x y -> isJust (x `divide` gcd x y) && isJust (y `divide` gcd x y)
    Property
    \x y z -> isJust (gcd (x * z) (y * z) `divide` z)
  • lcm :: a -> a -> a

    Lowest common multiple. Must satisfy

    Property
    \x y -> isJust (lcm x y `divide` x) && isJust (lcm x y `divide` y)
    Property
    \x y z -> isNothing (z `divide` x) || isNothing (z `divide` y) || isJust (z `divide` lcm x y)
  • coprime :: a -> a -> Bool

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

    Property
    \x y -> coprime x y == isJust (1 `divide` gcd x y)
Instances22GcdDomain, …
newtypenewtype WrappedIntegral a
#

Wrapper around Integral with GcdDomain and Euclidean instances.

Constructors

Instances12Enum, Eq, Integral, Num, Ord, Real, …
newtypenewtype WrappedFractional a
#

Wrapper around Fractional with trivial GcdDomain and Euclidean instances.

Constructors

Instances10Eq, Fractional, Num, Ord, Show, Euclidean, …
valuegcdExt :: (Eq a, Euclidean a, Ring a) => a -> a -> (a, a)
#

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.