Safe Haskell | None |
---|---|

Language | Haskell98 |

- Rings
- Rings with particular elements
- Rings with particular automorphisms
- Normed rings
- Floor and ceiling
- Particular rings
- The ring ℤ₂ of integers modulo 2
- The ring
**D**of dyadic fractions - The ring ℚ of rational numbers
- The ring
*R*[√2] - The ring ℤ[√2]
- The ring
**D**[√2] - The field ℚ[√2]
- The ring
*R*[*i*] - The ring ℤ[
*i*] of Gaussian integers - The ring
**D**[*i*] - The ring ℚ[
*i*] of Gaussian rationals - The ring
**D**[√2,*i*] - The ring ℚ[√2,
*i*] - The ring ℂ of complex numbers
- The ring
*R*[ω] - The ring ℤ[ω]
- The ring
**D**[ω] - The field ℚ[ω]

- Conversion to dyadic
- Real part
- Rings of integers
- Common denominators
- Conversion to ℚ[ω]
- Parity
- Auxiliary functions

This module provides type classes for rings. It also provides
several specific instances of rings, such as the ring ℤ₂ of
integers modulo 2, the ring ℚ of rational numbers, the ring ℤ[½] of
dyadic fractions, the ring ℤ[*i*] of Gaussian integers, the ring
ℤ[√2] of quadratic integers with radix 2, and the ring ℤ[ω] of
cyclotomic integers of degree 8.

- type Ring a = Num a
- class Ring a => HalfRing a where
- class Ring a => RootTwoRing a where
- class (HalfRing a, RootTwoRing a) => RootHalfRing a where
- class Ring a => ComplexRing a where
- class Ring a => OmegaRing a where
- class Adjoint a where
- class Adjoint2 a where
- class Ring r => NormedRing r where
- class Ring r => Floor r where
- data Z2
- data Dyadic = Dyadic !Integer !Integer
- decompose_dyadic :: Dyadic -> (Integer, Integer)
- integer_of_dyadic :: Dyadic -> Integer -> Integer
- newtype Rationals = ToRationals {}
- showsPrec_rational :: (Show a, Integral a) => Int -> Ratio a -> ShowS
- fromRationals :: Fractional a => Rationals -> a
- data RootTwo a = RootTwo !a !a
- type ZRootTwo = RootTwo Integer
- zroottwo_root :: ZRootTwo -> Maybe ZRootTwo
- type DRootTwo = RootTwo Dyadic
- type QRootTwo = RootTwo Rationals
- fromQRootTwo :: (RootTwoRing a, Fractional a) => QRootTwo -> a
- data Cplx a = Cplx !a !a
- type ZComplex = Cplx Integer
- fromZComplex :: ComplexRing a => ZComplex -> a
- type DComplex = Cplx Dyadic
- fromDComplex :: (ComplexRing a, HalfRing a) => DComplex -> a
- type QComplex = Cplx Rationals
- fromQComplex :: (ComplexRing a, Fractional a) => QComplex -> a
- type DRComplex = Cplx DRootTwo
- fromDRComplex :: (RootHalfRing a, ComplexRing a) => DRComplex -> a
- type QRComplex = Cplx QRootTwo
- fromQRComplex :: (RootTwoRing a, ComplexRing a, Fractional a) => QRComplex -> a
- type CDouble = Cplx Double
- type CFloat = Cplx Float
- data Omega a = Omega !a !a !a !a
- omega_real :: Omega a -> a
- type ZOmega = Omega Integer
- fromZOmega :: OmegaRing a => ZOmega -> a
- zroottwo_of_zomega :: ZOmega -> ZRootTwo
- type DOmega = Omega Dyadic
- fromDOmega :: (OmegaRing a, HalfRing a) => DOmega -> a
- type QOmega = Omega Rationals
- fromQOmega :: (OmegaRing a, Fractional a) => QOmega -> a
- class ToDyadic a b | a -> b where
- to_dyadic :: ToDyadic a b => a -> b
- class RealPart a b | a -> b where
- class WholePart a b | a -> b where
- class DenomExp a where
- denomexp_decompose :: (WholePart a b, DenomExp a) => a -> (b, Integer)
- showsPrec_DenomExp :: (WholePart a b, Show b, DenomExp a) => Int -> a -> ShowS
- class ToQOmega a where
- class Parity a where
- lobit :: Integer -> Integer
- log2 :: Integer -> Maybe Integer
- hibit :: Integer -> Int
- intsqrt :: Integral n => n -> n

# Rings

A type class to denote rings. We make `Ring`

a synonym of
Haskell's `Num`

type class, so that we can use the usual notation
`+`

, `-`

, `*`

for the ring operations. This is not a perfect fit,
because Haskell's `Num`

class also contains two non-ring operations
`abs`

and `signum`

. By convention, for rings where these notions
don't make sense (or are inconvenient to define), we set `abs`

*x*
= *x* and `signum`

*x* = 1.

# Rings with particular elements

We define several classes of rings with special elements.

## Rings with ½

class Ring a => HalfRing a where Source #

A type class for rings that contain ½.

Minimal complete definition: `half`

. The default definition of
`fromDyadic`

uses the expression `a*half^n`

. However, this can give
potentially bad round-off errors for fixed-precision types where
the expression `half^n`

can underflow. For such rings, one should
provide a custom definition, for example by using `a/2^n`

instead.

The value ½.

fromDyadic :: Dyadic -> a Source #

HalfRing Double Source # | |

HalfRing Float Source # | |

HalfRing Rational Source # | |

HalfRing Rationals Source # | |

HalfRing Dyadic Source # | |

(HalfRing a, RealFloat a) => HalfRing (Complex a) Source # | |

HalfRing a => HalfRing (Omega a) Source # | |

HalfRing a => HalfRing (Cplx a) Source # | |

(Eq a, HalfRing a) => HalfRing (RootTwo a) Source # | |

(HalfRing a, Nat n) => HalfRing (Matrix n n a) Source # | |

## Rings with √2

class Ring a => RootTwoRing a where Source #

A type class for rings that contain √2.

Minimal complete definition: `roottwo`

. The default definition of
`fromZRootTwo`

uses the expression `x+roottwo*y`

. However, this can
give potentially bad round-off errors for fixed-precision types,
where the expression `roottwo*y`

can be vastly inaccurate if `y`

is
large. For such rings, one should provide a custom definition.

The square root of 2.

fromZRootTwo :: RootTwoRing a => ZRootTwo -> a Source #

The unique ring homomorphism from ℤ[√2] to any ring containing √2. This exists because ℤ[√2] is the free such ring.

RootTwoRing Double Source # | |

RootTwoRing Float Source # | |

(RootTwoRing a, RealFloat a) => RootTwoRing (Complex a) Source # | |

Ring a => RootTwoRing (Omega a) Source # | |

RootTwoRing a => RootTwoRing (Cplx a) Source # | |

(Eq a, Ring a) => RootTwoRing (RootTwo a) Source # | |

(RootTwoRing a, Nat n) => RootTwoRing (Matrix n n a) Source # | |

## Rings with 1/√2

class (HalfRing a, RootTwoRing a) => RootHalfRing a where Source #

A type class for rings that contain 1/√2.

Minimal complete definition: `roothalf`

. The default definition of
`fromDRootTwo`

uses the expression `x+roottwo*y`

. However, this can
give potentially bad round-off errors for fixed-precision types,
where the expression `roottwo*y`

can be vastly inaccurate if `y`

is
large. For such rings, one should provide a custom definition.

The square root of ½.

fromDRootTwo :: RootHalfRing a => DRootTwo -> a Source #

The unique ring homomorphism from **D**[√2] to any ring containing
1/√2. This exists because **D**[√2] = ℤ[1/√2] is the free such ring.

RootHalfRing Double Source # | |

RootHalfRing Float Source # | |

(RootHalfRing a, RealFloat a) => RootHalfRing (Complex a) Source # | |

HalfRing a => RootHalfRing (Omega a) Source # | |

RootHalfRing a => RootHalfRing (Cplx a) Source # | |

(Eq a, HalfRing a) => RootHalfRing (RootTwo a) Source # | |

(RootHalfRing a, Nat n) => RootHalfRing (Matrix n n a) Source # | |

## Rings with *i*

class Ring a => ComplexRing a where Source #

A type class for rings that contain a square root of -1.

(Ring a, RealFloat a) => ComplexRing (Complex a) Source # | |

Ring a => ComplexRing (Omega a) Source # | |

Ring a => ComplexRing (Cplx a) Source # | |

(Eq a, ComplexRing a) => ComplexRing (RootTwo a) Source # | |

(ComplexRing a, Nat n) => ComplexRing (Matrix n n a) Source # | |

## Rings with ω

class Ring a => OmegaRing a where Source #

A type class for rings that contain a square root of *i*, or
equivalently, a fourth root of −1.

# Rings with particular automorphisms

## Rings with complex conjugation

class Adjoint a where Source #

A type class for rings with complex conjugation, i.e., an
automorphism mapping *i* to −*i*.

When instances of this type class are vectors or matrices, the conjugation also exchanges the roles of rows and columns (in other words, it is the adjoint).

For rings that are not complex, the conjugation can be defined to be the identity function.

Adjoint Double Source # | |

Adjoint Float Source # | |

Adjoint Int Source # | |

Adjoint Integer Source # | |

Adjoint Rational Source # | |

Adjoint Rationals Source # | |

Adjoint Dyadic Source # | |

Adjoint Z2 Source # | |

(Adjoint a, Ring a) => Adjoint (Complex a) Source # | |

(Adjoint a, Ring a) => Adjoint (Omega a) Source # | |

(Adjoint a, Ring a) => Adjoint (Cplx a) Source # | |

Adjoint a => Adjoint (RootTwo a) Source # | |

(Nat n, Adjoint a) => Adjoint (Matrix n n a) Source # | |

## Rings with √2-conjugation

class Adjoint2 a where Source #

A type class for rings with a √2-conjugation, i.e., an automorphism mapping √2 to −√2.

When instances of this type class are vectors or matrices, the
√2-conjugation does *not* exchange the roles of rows and columns.

For rings that have no √2, the conjugation can be defined to be the identity function.

Adjoint2 Int Source # | |

Adjoint2 Integer Source # | |

Adjoint2 Rational Source # | |

Adjoint2 Rationals Source # | |

Adjoint2 Dyadic Source # | |

Adjoint2 Z2 Source # | |

(Adjoint2 a, Ring a) => Adjoint2 (Omega a) Source # | |

(Adjoint2 a, Ring a) => Adjoint2 (Cplx a) Source # | |

(Adjoint2 a, Num a) => Adjoint2 (RootTwo a) Source # | |

(Nat n, Adjoint2 a) => Adjoint2 (Matrix n n a) Source # | |

# Normed rings

class Ring r => NormedRing r where Source #

A (number-theoretic) *norm* on a ring *R* is a function *N* : *R*
→ ℤ such that *N*(*rs*) = *N*(*r*)*N*(*s*), for all *r*, *s* ∈ *R*.
The norm also satisfies *N*(*r*) = 0 iff *r* = 0, and *N*(*r*) = ±1
iff *r* is a unit of the ring.

NormedRing Integer Source # | |

NormedRing a => NormedRing (Omega a) Source # | |

NormedRing a => NormedRing (Cplx a) Source # | |

(Eq a, NormedRing a) => NormedRing (RootTwo a) Source # | |

# Floor and ceiling

class Ring r => Floor r where Source #

The `floor`

and `ceiling`

functions provided by the standard
Haskell libraries are predicated on many unnecessary assumptions.
This type class provides an alternative.

Minimal complete definition: `floor_of`

or `ceiling_of`

.

# Particular rings

## The ring ℤ₂ of integers modulo 2

The ring ℤ₂ of integers modulo 2.

## The ring **D** of dyadic fractions

A dyadic fraction is a rational number whose denominator is a
power of 2. We denote the dyadic fractions by **D** = ℤ[½].

We internally represent a dyadic fraction *a*/2^{n} as a pair
(*a*,*n*). Note that this representation is not unique. When it is
necessary to choose a canonical representative, we choose the least
possible *n*≥0.

Eq Dyadic Source # | |

Num Dyadic Source # | |

Ord Dyadic Source # | |

Real Dyadic Source # | |

Show DOmega Source # | |

Show DRComplex Source # | |

Show Dyadic Source # | |

ToQOmega Dyadic Source # | |

DenomExp DOmega Source # | |

DenomExp DRootTwo Source # | |

Adjoint2 Dyadic Source # | |

Adjoint Dyadic Source # | |

HalfRing Dyadic Source # | |

ShowLaTeX DOmega Source # | |

ShowLaTeX Dyadic Source # | |

WholePart DOmega ZOmega Source # | |

WholePart DRootTwo ZRootTwo Source # | |

WholePart Dyadic Integer Source # | |

ToDyadic Rational Dyadic Source # | |

ToDyadic Rationals Dyadic Source # | |

ToDyadic Dyadic Dyadic Source # | |

Nat m => Show (Matrix m n DOmega) # | |

Nat m => Show (Matrix m n DRComplex) # | |

Nat m => Show (Matrix m n DRootTwo) # | |

Nat n => ShowLaTeX (Matrix n m DRComplex) Source # | |

Nat n => ShowLaTeX (Matrix n m DOmega) Source # | |

decompose_dyadic :: Dyadic -> (Integer, Integer) Source #

Given a dyadic fraction *r*, return (*a*,*n*) such that *r* =
*a*/2^{n}, where *n*≥0 is chosen as small as possible.

integer_of_dyadic :: Dyadic -> Integer -> Integer Source #

Given a dyadic fraction *r* and an integer *k*≥0, such that *a* =
*r*2^{k} is an integer, return *a*. If *a* is not an integer,
the behavior is undefined.

## The ring ℚ of rational numbers

We define our own variant of the rational numbers, which is an
identical copy of the type `Rational`

from the standard Haskell
library, except that it has a more sensible `Show`

instance.

showsPrec_rational :: (Show a, Integral a) => Int -> Ratio a -> ShowS Source #

An auxiliary function for printing rational numbers, using correct precedences, and omitting denominators of 1.

fromRationals :: Fractional a => Rationals -> a Source #

Conversion from `Rationals`

to any `Fractional`

type.

## The ring *R*[√2]

The ring *R*[√2], where *R* is any ring. The value `RootTwo`

*a*
*b* represents *a* + *b* √2.

RootTwo !a !a |

## The ring ℤ[√2]

zroottwo_root :: ZRootTwo -> Maybe ZRootTwo Source #

Return a square root of an element of ℤ[√2], if such a square
root exists, or else `Nothing`

.

## The ring **D**[√2]

## The field ℚ[√2]

fromQRootTwo :: (RootTwoRing a, Fractional a) => QRootTwo -> a Source #

The unique ring homomorphism from ℚ[√2] to any ring containing the rational numbers and √2. This exists because ℚ[√2] is the free such ring.

## The ring *R*[*i*]

The ring *R*[*i*], where *R* is any ring. The reason we do not
use the `Complex`

*a* type from the standard Haskell libraries is
that it assumes too much, for example, it assumes *a* is a member
of the `RealFloat`

class. Also, this allows us to define a more
sensible `Show`

instance.

Cplx !a !a |

## The ring ℤ[*i*] of Gaussian integers

fromZComplex :: ComplexRing a => ZComplex -> a Source #

The unique ring homomorphism from ℤ[*i*] to any ring containing
*i*. This exists because ℤ[*i*] is the free such ring.

## The ring **D**[*i*]

fromDComplex :: (ComplexRing a, HalfRing a) => DComplex -> a Source #

The unique ring homomorphism from **D**[*i*] to any ring containing
½ and *i*. This exists because **D**[*i*] is the free such ring.

## The ring ℚ[*i*] of Gaussian rationals

fromQComplex :: (ComplexRing a, Fractional a) => QComplex -> a Source #

The unique ring homomorphism from ℚ[*i*] to any ring containing
the rational numbers and *i*. This exists because ℚ[*i*] is the
free such ring.

## The ring **D**[√2, *i*]

fromDRComplex :: (RootHalfRing a, ComplexRing a) => DRComplex -> a Source #

The unique ring homomorphism from **D**[√2, *i*] to any ring
containing 1/√2 and *i*. This exists because **D**[√2, *i*] =
ℤ[1/√2, *i*] is the free such ring.

## The ring ℚ[√2, *i*]

fromQRComplex :: (RootTwoRing a, ComplexRing a, Fractional a) => QRComplex -> a Source #

The unique ring homomorphism from ℚ[√2, *i*] to any ring
containing the rational numbers, √2, and *i*. This exists because
ℚ[√2, *i*] is the free such ring.

## The ring ℂ of complex numbers

We provide two versions of the complex numbers using floating point arithmetic.

## The ring *R*[ω]

The ring *R*[ω], where *R* is any ring, and ω = *e*^{iπ/4} is an
8th root of unity. The value `Omega`

*a* *b* *c* *d* represents
*a*ω^{3}+*b*ω^{2}+*c*ω+*d*.

Omega !a !a !a !a |

Show DOmega Source # | |

DenomExp DOmega Source # | |

EuclideanDomain ZOmega Source # | |

ShowLaTeX DOmega Source # | |

ShowLaTeX ZOmega Source # | |

WholePart DOmega ZOmega Source # | |

Eq a => Eq (Omega a) Source # | |

Fractional a => Fractional (Omega a) Source # | |

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

(Show a, Ring a) => Show (Omega a) Source # | |

ToQOmega a => ToQOmega (Omega a) Source # | |

NormedRing a => NormedRing (Omega a) Source # | |

(Adjoint2 a, Ring a) => Adjoint2 (Omega a) Source # | |

(Adjoint a, Ring a) => Adjoint (Omega a) Source # | |

Ring a => OmegaRing (Omega a) Source # | |

Ring a => ComplexRing (Omega a) Source # | |

HalfRing a => RootHalfRing (Omega a) Source # | |

Ring a => RootTwoRing (Omega a) Source # | |

HalfRing a => HalfRing (Omega a) Source # | |

ShowLaTeX (Omega Z2) Source # | |

HalfRing a => RealPart (Omega a) (RootTwo a) Source # | |

ToDyadic a b => ToDyadic (Omega a) (Omega b) Source # | |

Residue a b => Residue (Omega a) (Omega b) Source # | |

Nat m => Show (Matrix m n DOmega) # | |

Nat n => ShowLaTeX (Matrix n m DOmega) Source # | |

omega_real :: Omega a -> a Source #

An inverse to the embedding *R* ↦ *R*[ω]: return the "real
rational" part.
In other words, map *a*ω^{3}+*b*ω^{2}+*c*ω+*d* to *d*.

## The ring ℤ[ω]

type ZOmega = Omega Integer Source #

The ring ℤ[ω] of *cyclotomic integers* of degree 8. Such rings
were first studied by Kummer around 1840, and used in his proof of
special cases of Fermat's Last Theorem. See also:

- http://fermatslasttheorem.blogspot.com/2006/05/basic-properties-of-cyclotomic.html
- http://fermatslasttheorem.blogspot.com/2006/02/cyclotomic-integers.html
- Harold M. Edwards, "Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory".

fromZOmega :: OmegaRing a => ZOmega -> a Source #

The unique ring homomorphism from ℤ[ω] to any ring containing ω. This exists because ℤ[ω] is the free such ring.

zroottwo_of_zomega :: ZOmega -> ZRootTwo Source #

Inverse of the embedding ℤ[√2] → ℤ[ω]. Note that ℤ[√2] = ℤ[ω] ∩ ℝ. This function takes an element of ℤ[ω] that is real, and converts it to an element of ℤ[√2]. It throws an error if the input is not real.

## The ring **D**[ω]

type DOmega = Omega Dyadic Source #

The ring **D**[ω]. Here **D**=ℤ[½] is the ring of dyadic
fractions. In fact, **D**[ω] is isomorphic to the ring **D**[√2,
i], but they have different `Show`

instances.

fromDOmega :: (OmegaRing a, HalfRing a) => DOmega -> a Source #

The unique ring homomorphism from **D**[ω] to any ring containing
ω and 1/2. This exists because **D**[ω] is the free such ring.

## The field ℚ[ω]

fromQOmega :: (OmegaRing a, Fractional a) => QOmega -> a Source #

The unique ring homomorphism from ℚ[ω] to any ring containing the rational numbers and ω. This exists because ℚ[ω] is the free such ring.

# Conversion to dyadic

class ToDyadic a b | a -> b where Source #

A type class relating "rational" types to their dyadic counterparts.

maybe_dyadic :: a -> Maybe b Source #

Convert a "rational" value to a "dyadic" value, if the
denominator is a power of 2. Otherwise, return `Nothing`

.

ToDyadic Rational Dyadic Source # | |

ToDyadic Rationals Dyadic Source # | |

ToDyadic Dyadic Dyadic Source # | |

ToDyadic a b => ToDyadic (Omega a) (Omega b) Source # | |

ToDyadic a b => ToDyadic (Cplx a) (Cplx b) Source # | |

ToDyadic a b => ToDyadic (RootTwo a) (RootTwo b) Source # | |

ToDyadic a b => ToDyadic (Vector n a) (Vector n b) Source # | |

ToDyadic a b => ToDyadic (Matrix m n a) (Matrix m n b) Source # | |

to_dyadic :: ToDyadic a b => a -> b Source #

Convert a "rational" value to a "dyadic" value, if the denominator is a power of 2. Otherwise, throw an error.

# Real part

# Rings of integers

class WholePart a b | a -> b where Source #

A type class for rings that have a distinguished subring "of
integers". A typical instance is *a* = `DRootTwo`

, which has *b* =
`ZRootTwo`

as its ring of integers.

from_whole :: b -> a Source #

The embedding of the ring of integers into the larger ring.

The inverse of `from_whole`

. Throws an error if the given
element is not actually an integer in the ring.

WholePart () () Source # | |

WholePart DOmega ZOmega Source # | |

WholePart DRootTwo ZRootTwo Source # | |

WholePart Dyadic Integer Source # | |

WholePart a b => WholePart [a] [b] Source # | |

WholePart a b => WholePart (Cplx a) (Cplx b) Source # | |

(WholePart a a', WholePart b b') => WholePart (a, b) (a', b') Source # | |

WholePart a b => WholePart (Vector n a) (Vector n b) Source # | |

WholePart a b => WholePart (Matrix m n a) (Matrix m n b) Source # | |

# Common denominators

class DenomExp a where Source #

A type class for things from which a common power of 1/√2 (a
least denominator exponent) can be factored out. Typical instances
are `DRootTwo`

, `DRComplex`

, as well as tuples, lists, vectors, and
matrices thereof.

denomexp_decompose :: (WholePart a b, DenomExp a) => a -> (b, Integer) Source #

Calculate and factor out the least denominator exponent *k* of
*a*. Return (*b*,*k*), where *a* = *b*/(√2)^{k} and *k*≥0.

showsPrec_DenomExp :: (WholePart a b, Show b, DenomExp a) => Int -> a -> ShowS Source #

Generic `show`

-like method that factors out a common denominator
exponent.

# Conversion to ℚ[ω]

`QOmega`

is the largest one of our "exact" arithmetic types. We
define a `toQOmega`

family of functions for converting just about
anything to `QOmega`

.

# Parity

A type class for things that have parity.

# Auxiliary functions

lobit :: Integer -> Integer Source #

Return the position of the rightmost "1" bit of an Integer, or
-1 if none. Do this in time O(*n* log *n*), where *n* is the size
of the integer (in digits).

log2 :: Integer -> Maybe Integer Source #

If *n* is of the form 2^{k}, return *k*. Otherwise, return
`Nothing`

.