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

Data.Euclidean

Description

Synopsis

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

Minimal complete definition

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
 Source # Instance detailsDefined in Data.Euclidean MethodsquotRem :: Double -> Double -> (Double, Double) Source # Source # Instance detailsDefined in Data.Euclidean MethodsquotRem :: Float -> Float -> (Float, Float) Source # Source # Instance detailsDefined in Data.Euclidean MethodsquotRem :: Int -> Int -> (Int, Int) Source #quot :: Int -> Int -> Int Source #rem :: Int -> Int -> Int Source # Source # Instance detailsDefined in Data.Euclidean Methods Source # Instance detailsDefined in Data.Euclidean Methods Source # Instance detailsDefined in Data.Euclidean MethodsquotRem :: Word -> Word -> (Word, Word) Source #quot :: Word -> Word -> Word Source #rem :: Word -> Word -> Word Source # Source # Instance detailsDefined in Data.Euclidean MethodsquotRem :: () -> () -> ((), ()) Source #quot :: () -> () -> () Source #rem :: () -> () -> () Source #degree :: () -> Natural Source # Source # Instance detailsDefined in Data.Euclidean MethodsquotRem :: CFloat -> CFloat -> (CFloat, CFloat) Source # Source # Instance detailsDefined in Data.Euclidean Methods Integral a => Euclidean (Ratio a) Source # Instance detailsDefined in Data.Euclidean MethodsquotRem :: 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 # Field a => Euclidean (Complex a) Source # Instance detailsDefined in Data.Euclidean MethodsquotRem :: 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 # Source # Instance detailsDefined in Data.Euclidean Methods Source # Instance detailsDefined in Data.Euclidean Methods

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

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

Instances
 Source # Instance detailsDefined in Data.Euclidean Source # Instance detailsDefined in Data.Euclidean Field () Source # Instance detailsDefined in Data.Euclidean Source # Instance detailsDefined in Data.Euclidean Source # Instance detailsDefined in Data.Euclidean Integral a => Field (Ratio a) Source # Instance detailsDefined in Data.Euclidean Field a => Field (Complex a) Source # Instance detailsDefined in Data.Euclidean Source # Instance detailsDefined 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)

divide :: (Eq a, Euclidean a) => 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)

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)

gcd :: (Eq a, Euclidean a) => 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)

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)

lcm :: Eq a => 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)

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)

coprime :: Eq a => 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)
Instances
 Source # Instance detailsDefined in Data.Euclidean Methods Source # Instance detailsDefined in Data.Euclidean Methods Source # Instance detailsDefined in Data.Euclidean Methodsgcd :: Int -> Int -> Int Source #lcm :: Int -> Int -> Int Source #coprime :: Int -> Int -> Bool Source # Source # Instance detailsDefined in Data.Euclidean Methods Source # Instance detailsDefined in Data.Euclidean Methods Source # Instance detailsDefined in Data.Euclidean Methodsgcd :: Word -> Word -> Word Source #lcm :: Word -> Word -> Word Source # Source # Instance detailsDefined in Data.Euclidean Methodsdivide :: () -> () -> Maybe () Source #gcd :: () -> () -> () Source #lcm :: () -> () -> () Source #coprime :: () -> () -> Bool Source # Source # Instance detailsDefined in Data.Euclidean Methods Source # Instance detailsDefined in Data.Euclidean Methods Integral a => GcdDomain (Ratio a) Source # Instance detailsDefined in Data.Euclidean Methodsdivide :: 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 # Field a => GcdDomain (Complex a) Source # Instance detailsDefined in Data.Euclidean Methodsdivide :: 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 # Source # Instance detailsDefined in Data.Euclidean Methods Source # Instance detailsDefined in Data.Euclidean Methods

newtype WrappedIntegral a Source #

Wrapper around Integral with GcdDomain and Euclidean instances.

Constructors

 WrapIntegral FieldsunwrapIntegral :: a
Instances
 Enum a => Enum (WrappedIntegral a) Source # Instance detailsDefined in Data.Euclidean MethodsenumFrom :: WrappedIntegral a -> [WrappedIntegral a] #enumFromTo :: WrappedIntegral a -> WrappedIntegral a -> [WrappedIntegral a] # Eq a => Eq (WrappedIntegral a) Source # Instance detailsDefined in Data.Euclidean Methods(==) :: WrappedIntegral a -> WrappedIntegral a -> Bool #(/=) :: WrappedIntegral a -> WrappedIntegral a -> Bool # Source # Instance detailsDefined in Data.Euclidean Methods Num a => Num (WrappedIntegral a) Source # Instance detailsDefined in Data.Euclidean Methods Ord a => Ord (WrappedIntegral a) Source # Instance detailsDefined in Data.Euclidean Methods(<) :: WrappedIntegral a -> WrappedIntegral a -> Bool #(<=) :: WrappedIntegral a -> WrappedIntegral a -> Bool #(>) :: WrappedIntegral a -> WrappedIntegral a -> Bool #(>=) :: WrappedIntegral a -> WrappedIntegral a -> Bool # Real a => Real (WrappedIntegral a) Source # Instance detailsDefined in Data.Euclidean Methods Show a => Show (WrappedIntegral a) Source # Instance detailsDefined in Data.Euclidean MethodsshowList :: [WrappedIntegral a] -> ShowS # Bits a => Bits (WrappedIntegral a) Source # Instance detailsDefined in Data.Euclidean MethodstestBit :: WrappedIntegral a -> Int -> Bool # Num a => Ring (WrappedIntegral a) Source # Instance detailsDefined in Data.Euclidean Methods Num a => Semiring (WrappedIntegral a) Source # Instance detailsDefined in Data.Euclidean Methods Source # Instance detailsDefined in Data.Euclidean Methods Source # Instance detailsDefined in Data.Euclidean Methods

newtype WrappedFractional a Source #

Wrapper around Fractional with trivial GcdDomain and Euclidean instances.

Constructors

 WrapFractional FieldsunwrapFractional :: a
Instances
 Eq a => Eq (WrappedFractional a) Source # Instance detailsDefined in Data.Euclidean Methods Source # Instance detailsDefined in Data.Euclidean Methods Num a => Num (WrappedFractional a) Source # Instance detailsDefined in Data.Euclidean Methods Ord a => Ord (WrappedFractional a) Source # Instance detailsDefined in Data.Euclidean Methods Show a => Show (WrappedFractional a) Source # Instance detailsDefined in Data.Euclidean MethodsshowList :: [WrappedFractional a] -> ShowS # Num a => Ring (WrappedFractional a) Source # Instance detailsDefined in Data.Euclidean Methods Num a => Semiring (WrappedFractional a) Source # Instance detailsDefined in Data.Euclidean Methods Source # Instance detailsDefined in Data.Euclidean Source # Instance detailsDefined in Data.Euclidean Methods Source # Instance detailsDefined in Data.Euclidean Methods