Quantum.Synthesis.Ring

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.

Rings

class Num a => Ring a

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.

Instances

Num a => Ring a

Rings with particular elements

We define several classes of rings with special elements.

Rings with ½

class Ring a => HalfRing a where

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.

Minimal complete definition

half

Methods

half :: a

The value ½.

fromDyadic :: Dyadic -> a

The unique ring homomorphism from ℤ[½] to any HalfRing. This exists because ℤ[½] is the free HalfRing.

Instances

HalfRing Double

Methods

half :: Double

fromDyadic :: Dyadic -> Double

HalfRing Float

Methods

half :: Float

fromDyadic :: Dyadic -> Float

HalfRing Rational

Methods

half :: Rational

fromDyadic :: Dyadic -> Rational

HalfRing Rationals

Methods

half :: Rationals

fromDyadic :: Dyadic -> Rationals

HalfRing Dyadic

Methods

half :: Dyadic

fromDyadic :: Dyadic -> Dyadic

(HalfRing a, RealFloat a) => HalfRing (Complex a)

Methods

half :: Complex a

fromDyadic :: Dyadic -> Complex a

HalfRing a => HalfRing (Omega a)

Methods

half :: Omega a

fromDyadic :: Dyadic -> Omega a

HalfRing a => HalfRing (Cplx a)

Methods

half :: Cplx a

fromDyadic :: Dyadic -> Cplx a

(Eq a, HalfRing a) => HalfRing (RootTwo a)

Methods

half :: RootTwo a

fromDyadic :: Dyadic -> RootTwo a

(HalfRing a, Nat n) => HalfRing (Matrix n n a)

Methods

half :: Matrix n n a

fromDyadic :: Dyadic -> Matrix n n a

Rings with √2

class Ring a => RootTwoRing a where

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.

Minimal complete definition

roottwo

Methods

roottwo :: a

The square root of 2.

fromZRootTwo :: RootTwoRing a => ZRootTwo -> a

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

Instances

RootTwoRing Double

Methods

roottwo :: Double

fromZRootTwo :: ZRootTwo -> Double

RootTwoRing Float

Methods

roottwo :: Float

fromZRootTwo :: ZRootTwo -> Float

(RootTwoRing a, RealFloat a) => RootTwoRing (Complex a)

Methods

roottwo :: Complex a

fromZRootTwo :: ZRootTwo -> Complex a

Ring a => RootTwoRing (Omega a)

Methods

roottwo :: Omega a

fromZRootTwo :: ZRootTwo -> Omega a

RootTwoRing a => RootTwoRing (Cplx a)

Methods

roottwo :: Cplx a

fromZRootTwo :: ZRootTwo -> Cplx a

(Eq a, Ring a) => RootTwoRing (RootTwo a)

Methods

roottwo :: RootTwo a

fromZRootTwo :: ZRootTwo -> RootTwo a

(RootTwoRing a, Nat n) => RootTwoRing (Matrix n n a)

Methods

roottwo :: Matrix n n a

fromZRootTwo :: ZRootTwo -> Matrix n n a

Rings with 1/√2

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

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.

Minimal complete definition

roothalf

Methods

roothalf :: a

The square root of ½.

fromDRootTwo :: RootHalfRing a => DRootTwo -> a

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.

Instances

RootHalfRing Double

Methods

roothalf :: Double

fromDRootTwo :: DRootTwo -> Double

RootHalfRing Float

Methods

roothalf :: Float

fromDRootTwo :: DRootTwo -> Float

(RootHalfRing a, RealFloat a) => RootHalfRing (Complex a)

Methods

roothalf :: Complex a

fromDRootTwo :: DRootTwo -> Complex a

HalfRing a => RootHalfRing (Omega a)

Methods

roothalf :: Omega a

fromDRootTwo :: DRootTwo -> Omega a

RootHalfRing a => RootHalfRing (Cplx a)

Methods

roothalf :: Cplx a

fromDRootTwo :: DRootTwo -> Cplx a

(Eq a, HalfRing a) => RootHalfRing (RootTwo a)

Methods

roothalf :: RootTwo a

fromDRootTwo :: DRootTwo -> RootTwo a

(RootHalfRing a, Nat n) => RootHalfRing (Matrix n n a)

Methods

roothalf :: Matrix n n a

fromDRootTwo :: DRootTwo -> Matrix n n a

Rings with i

class Ring a => ComplexRing a where

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

Minimal complete definition

i

Methods

i :: a

The complex unit.

Instances

(Ring a, RealFloat a) => ComplexRing (Complex a)

Methods

i :: Complex a

Ring a => ComplexRing (Omega a)

Methods

i :: Omega a

Ring a => ComplexRing (Cplx a)

Methods

i :: Cplx a

(Eq a, ComplexRing a) => ComplexRing (RootTwo a)

Methods

i :: RootTwo a

(ComplexRing a, Nat n) => ComplexRing (Matrix n n a)

Methods

i :: Matrix n n a

Rings with ω

class Ring a => OmegaRing a where

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

Minimal complete definition

omega

Methods

omega :: a

The square root of i.

Instances

(ComplexRing a, RootHalfRing a) => OmegaRing a

Methods

omega :: a

OmegaRing ZOmega

Methods

omega :: ZOmega

OmegaRing (Omega Z2)

Methods

omega :: Omega Z2

Rings with particular automorphisms

Rings with complex conjugation

class Adjoint a where

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.

Minimal complete definition

adj

Methods

adj :: a -> a

Compute the adjoint (complex conjugate transpose).

Instances

Adjoint Double

Methods

adj :: Double -> Double

Adjoint Float

Methods

adj :: Float -> Float

Adjoint Int

Methods

adj :: Int -> Int

Adjoint Integer

Methods

adj :: Integer -> Integer

Adjoint Rational

Methods

adj :: Rational -> Rational

Adjoint Rationals

Methods

adj :: Rationals -> Rationals

Adjoint Dyadic

Methods

adj :: Dyadic -> Dyadic

Adjoint Z2

Methods

adj :: Z2 -> Z2

(Adjoint a, Ring a) => Adjoint (Complex a)

Methods

adj :: Complex a -> Complex a

(Adjoint a, Ring a) => Adjoint (Omega a)

Methods

adj :: Omega a -> Omega a

(Adjoint a, Ring a) => Adjoint (Cplx a)

Methods

adj :: Cplx a -> Cplx a

Adjoint a => Adjoint (RootTwo a)

Methods

adj :: RootTwo a -> RootTwo a

(Nat n, Adjoint a) => Adjoint (Matrix n n a)

Methods

adj :: Matrix n n a -> Matrix n n a

Rings with √2-conjugation

class Adjoint2 a where

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.

Minimal complete definition

adj2

Methods

adj2 :: a -> a

Compute the adjoint, mapping a + b√2 to a −b√2.

Instances

Adjoint2 Int

Methods

adj2 :: Int -> Int

Adjoint2 Integer

Methods

adj2 :: Integer -> Integer

Adjoint2 Rational

Methods

adj2 :: Rational -> Rational

Adjoint2 Rationals

Methods

adj2 :: Rationals -> Rationals

Adjoint2 Dyadic

Methods

adj2 :: Dyadic -> Dyadic

Adjoint2 Z2

Methods

adj2 :: Z2 -> Z2

(Adjoint2 a, Ring a) => Adjoint2 (Omega a)

Methods

adj2 :: Omega a -> Omega a

(Adjoint2 a, Ring a) => Adjoint2 (Cplx a)

Methods

adj2 :: Cplx a -> Cplx a

(Adjoint2 a, Num a) => Adjoint2 (RootTwo a)

Methods

adj2 :: RootTwo a -> RootTwo a

(Nat n, Adjoint2 a) => Adjoint2 (Matrix n n a)

Methods

adj2 :: Matrix n n a -> Matrix n n a

Normed rings

class Ring r => NormedRing r where

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.

Minimal complete definition

norm

Methods

norm :: r -> Integer

Instances

NormedRing Integer

Methods

norm :: Integer -> Integer

NormedRing a => NormedRing (Omega a)

Methods

norm :: Omega a -> Integer

NormedRing a => NormedRing (Cplx a)

Methods

norm :: Cplx a -> Integer

(Eq a, NormedRing a) => NormedRing (RootTwo a)

Methods

norm :: RootTwo a -> Integer

Floor and ceiling

class Ring r => Floor r where

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.

Methods

floor_of :: r -> Integer

Compute the floor of x, i.e., the greatest integer n such that n ≤ x.

ceiling_of :: r -> Integer

Compute the ceiling of x, i.e., the least integer n such that x ≤ n.

Instances

Floor Double

Methods

floor_of :: Double -> Integer

ceiling_of :: Double -> Integer

Floor Float

Methods

floor_of :: Float -> Integer

ceiling_of :: Float -> Integer

Floor Integer

Methods

floor_of :: Integer -> Integer

ceiling_of :: Integer -> Integer

Floor Rational

Methods

floor_of :: Rational -> Integer

ceiling_of :: Rational -> Integer

Floor QRootTwo

Methods

floor_of :: QRootTwo -> Integer

ceiling_of :: QRootTwo -> Integer

Floor Rationals

Methods

floor_of :: Rationals -> Integer

ceiling_of :: Rationals -> Integer

Particular rings

The ring ℤ₂ of integers modulo 2

data Z2

The ring ℤ₂ of integers modulo 2.

Constructors

Even

Odd

Instances

Eq Z2

Methods

(==) :: Z2 -> Z2 -> Bool

(/=) :: Z2 -> Z2 -> Bool

Num Z2

Methods

(+) :: Z2 -> Z2 -> Z2

(-) :: Z2 -> Z2 -> Z2

(*) :: Z2 -> Z2 -> Z2

negate :: Z2 -> Z2

abs :: Z2 -> Z2

signum :: Z2 -> Z2

fromInteger :: Integer -> Z2

Show Z2

Methods

showsPrec :: Int -> Z2 -> ShowS

show :: Z2 -> String

showList :: [Z2] -> ShowS

Adjoint2 Z2

Methods

adj2 :: Z2 -> Z2

Adjoint Z2

Methods

adj :: Z2 -> Z2

Residue Integer Z2

Methods

residue :: Integer -> Z2

OmegaRing (Omega Z2)

Methods

omega :: Omega Z2

ShowLaTeX (Omega Z2)

Methods

showlatex :: Omega Z2 -> String

showlatex_p :: Int -> Omega Z2 -> ShowS

The ring D of dyadic fractions

data Dyadic

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

Constructors

Dyadic !Integer !Integer

Instances

Eq Dyadic

Methods

(==) :: Dyadic -> Dyadic -> Bool

(/=) :: Dyadic -> Dyadic -> Bool

Num Dyadic

Methods

(+) :: Dyadic -> Dyadic -> Dyadic

(-) :: Dyadic -> Dyadic -> Dyadic

(*) :: Dyadic -> Dyadic -> Dyadic

negate :: Dyadic -> Dyadic

abs :: Dyadic -> Dyadic

signum :: Dyadic -> Dyadic

fromInteger :: Integer -> Dyadic

Ord Dyadic

Methods

compare :: Dyadic -> Dyadic -> Ordering

(<) :: Dyadic -> Dyadic -> Bool

(<=) :: Dyadic -> Dyadic -> Bool

(>) :: Dyadic -> Dyadic -> Bool

(>=) :: Dyadic -> Dyadic -> Bool

max :: Dyadic -> Dyadic -> Dyadic

min :: Dyadic -> Dyadic -> Dyadic

Real Dyadic

Methods

toRational :: Dyadic -> Rational

Show DOmega

Methods

showsPrec :: Int -> DOmega -> ShowS

show :: DOmega -> String

showList :: [DOmega] -> ShowS

Show DRComplex

Methods

showsPrec :: Int -> DRComplex -> ShowS

show :: DRComplex -> String

showList :: [DRComplex] -> ShowS

Show Dyadic

Methods

showsPrec :: Int -> Dyadic -> ShowS

show :: Dyadic -> String

showList :: [Dyadic] -> ShowS

ToQOmega Dyadic

Methods

toQOmega :: Dyadic -> QOmega

DenomExp DOmega

Methods

denomexp :: DOmega -> Integer

denomexp_factor :: DOmega -> Integer -> DOmega

DenomExp DRootTwo

Methods

denomexp :: DRootTwo -> Integer

denomexp_factor :: DRootTwo -> Integer -> DRootTwo

Adjoint2 Dyadic

Methods

adj2 :: Dyadic -> Dyadic

Adjoint Dyadic

Methods

adj :: Dyadic -> Dyadic

HalfRing Dyadic

Methods

half :: Dyadic

fromDyadic :: Dyadic -> Dyadic

ShowLaTeX DOmega

Methods

showlatex :: DOmega -> String

showlatex_p :: Int -> DOmega -> ShowS

ShowLaTeX Dyadic

Methods

showlatex :: Dyadic -> String

showlatex_p :: Int -> Dyadic -> ShowS

WholePart DOmega ZOmega

Methods

from_whole :: ZOmega -> DOmega

to_whole :: DOmega -> ZOmega

WholePart DRootTwo ZRootTwo

Methods

from_whole :: ZRootTwo -> DRootTwo

to_whole :: DRootTwo -> ZRootTwo

WholePart Dyadic Integer

Methods

from_whole :: Integer -> Dyadic

to_whole :: Dyadic -> Integer

ToDyadic Rational Dyadic

Methods

maybe_dyadic :: Rational -> Maybe Dyadic

ToDyadic Rationals Dyadic

Methods

maybe_dyadic :: Rationals -> Maybe Dyadic

ToDyadic Dyadic Dyadic

Methods

maybe_dyadic :: Dyadic -> Maybe Dyadic

Nat m => Show (Matrix m n DOmega)

Methods

showsPrec :: Int -> Matrix m n DOmega -> ShowS

show :: Matrix m n DOmega -> String

showList :: [Matrix m n DOmega] -> ShowS

Nat m => Show (Matrix m n DRComplex)

Methods

showsPrec :: Int -> Matrix m n DRComplex -> ShowS

show :: Matrix m n DRComplex -> String

showList :: [Matrix m n DRComplex] -> ShowS

Nat m => Show (Matrix m n DRootTwo)

Methods

showsPrec :: Int -> Matrix m n DRootTwo -> ShowS

show :: Matrix m n DRootTwo -> String

showList :: [Matrix m n DRootTwo] -> ShowS

Nat n => ShowLaTeX (Matrix n m DRComplex)

Methods

showlatex :: Matrix n m DRComplex -> String

showlatex_p :: Int -> Matrix n m DRComplex -> ShowS

Nat n => ShowLaTeX (Matrix n m DOmega)

Methods

showlatex :: Matrix n m DOmega -> String

showlatex_p :: Int -> Matrix n m DOmega -> ShowS

decompose_dyadic :: Dyadic -> (Integer, Integer)

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

integer_of_dyadic :: Dyadic -> Integer -> Integer

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

The ring ℚ of rational numbers

newtype Rationals

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.

Constructors

ToRationals

Fields

• unRationals :: Rational

Instances

Eq Rationals

Methods

(==) :: Rationals -> Rationals -> Bool

(/=) :: Rationals -> Rationals -> Bool

Fractional Rationals

Methods

(/) :: Rationals -> Rationals -> Rationals

recip :: Rationals -> Rationals

fromRational :: Rational -> Rationals

Num Rationals

Methods

(+) :: Rationals -> Rationals -> Rationals

(-) :: Rationals -> Rationals -> Rationals

(*) :: Rationals -> Rationals -> Rationals

negate :: Rationals -> Rationals

abs :: Rationals -> Rationals

signum :: Rationals -> Rationals

fromInteger :: Integer -> Rationals

Ord Rationals

Methods

compare :: Rationals -> Rationals -> Ordering

(<) :: Rationals -> Rationals -> Bool

(<=) :: Rationals -> Rationals -> Bool

(>) :: Rationals -> Rationals -> Bool

(>=) :: Rationals -> Rationals -> Bool

max :: Rationals -> Rationals -> Rationals

min :: Rationals -> Rationals -> Rationals

Real Rationals

Methods

toRational :: Rationals -> Rational

RealFrac Rationals

Methods

properFraction :: Integral b => Rationals -> (b, Rationals)

truncate :: Integral b => Rationals -> b

round :: Integral b => Rationals -> b

ceiling :: Integral b => Rationals -> b

floor :: Integral b => Rationals -> b

Show Rationals

Methods

showsPrec :: Int -> Rationals -> ShowS

show :: Rationals -> String

showList :: [Rationals] -> ShowS

ToQOmega Rationals

Methods

toQOmega :: Rationals -> QOmega

Floor QRootTwo

Methods

floor_of :: QRootTwo -> Integer

ceiling_of :: QRootTwo -> Integer

Floor Rationals

Methods

floor_of :: Rationals -> Integer

ceiling_of :: Rationals -> Integer

Adjoint2 Rationals

Methods

adj2 :: Rationals -> Rationals

Adjoint Rationals

Methods

adj :: Rationals -> Rationals

HalfRing Rationals

Methods

half :: Rationals

fromDyadic :: Dyadic -> Rationals

ToDyadic Rationals Dyadic

Methods

maybe_dyadic :: Rationals -> Maybe Dyadic

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

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

fromRationals :: Fractional a => Rationals -> a

Conversion from Rationals to any Fractional type.

The ring R[√2]

data RootTwo a

The ring R[√2], where R is any ring. The value RootTwo a b represents a + b √2.

Constructors

RootTwo !a !a

Instances

Show DRComplex

Methods

showsPrec :: Int -> DRComplex -> ShowS

show :: DRComplex -> String

showList :: [DRComplex] -> ShowS

Parity ZRootTwo

Methods

parity :: ZRootTwo -> Z2

DenomExp DRootTwo

Methods

denomexp :: DRootTwo -> Integer

denomexp_factor :: DRootTwo -> Integer -> DRootTwo

Floor QRootTwo

Methods

floor_of :: QRootTwo -> Integer

ceiling_of :: QRootTwo -> Integer

EuclideanDomain ZRootTwo

Methods

rank :: ZRootTwo -> Integer

divmod :: ZRootTwo -> ZRootTwo -> (ZRootTwo, ZRootTwo)

WholePart DRootTwo ZRootTwo

Methods

from_whole :: ZRootTwo -> DRootTwo

to_whole :: DRootTwo -> ZRootTwo

Eq a => Eq (RootTwo a)

Methods

(==) :: RootTwo a -> RootTwo a -> Bool

(/=) :: RootTwo a -> RootTwo a -> Bool

(Eq a, Fractional a) => Fractional (RootTwo a)

Methods

(/) :: RootTwo a -> RootTwo a -> RootTwo a

recip :: RootTwo a -> RootTwo a

fromRational :: Rational -> RootTwo a

(Eq a, Num a) => Num (RootTwo a)

Methods

(+) :: RootTwo a -> RootTwo a -> RootTwo a

(-) :: RootTwo a -> RootTwo a -> RootTwo a

(*) :: RootTwo a -> RootTwo a -> RootTwo a

negate :: RootTwo a -> RootTwo a

abs :: RootTwo a -> RootTwo a

signum :: RootTwo a -> RootTwo a

fromInteger :: Integer -> RootTwo a

(Eq a, Ring a) => Ord (RootTwo a)

Methods

compare :: RootTwo a -> RootTwo a -> Ordering

(<) :: RootTwo a -> RootTwo a -> Bool

(<=) :: RootTwo a -> RootTwo a -> Bool

(>) :: RootTwo a -> RootTwo a -> Bool

(>=) :: RootTwo a -> RootTwo a -> Bool

max :: RootTwo a -> RootTwo a -> RootTwo a

min :: RootTwo a -> RootTwo a -> RootTwo a

(Show a, Eq a, Ring a) => Show (RootTwo a)

Methods

showsPrec :: Int -> RootTwo a -> ShowS

show :: RootTwo a -> String

showList :: [RootTwo a] -> ShowS

ToQOmega a => ToQOmega (RootTwo a)

Methods

toQOmega :: RootTwo a -> QOmega

(Eq a, NormedRing a) => NormedRing (RootTwo a)

Methods

norm :: RootTwo a -> Integer

(Adjoint2 a, Num a) => Adjoint2 (RootTwo a)

Methods

adj2 :: RootTwo a -> RootTwo a

Adjoint a => Adjoint (RootTwo a)

Methods

adj :: RootTwo a -> RootTwo a

(Eq a, ComplexRing a) => ComplexRing (RootTwo a)

Methods

i :: RootTwo a

(Eq a, HalfRing a) => RootHalfRing (RootTwo a)

Methods

roothalf :: RootTwo a

fromDRootTwo :: DRootTwo -> RootTwo a

(Eq a, Ring a) => RootTwoRing (RootTwo a)

Methods

roottwo :: RootTwo a

fromZRootTwo :: ZRootTwo -> RootTwo a

(Eq a, HalfRing a) => HalfRing (RootTwo a)

Methods

half :: RootTwo a

fromDyadic :: Dyadic -> RootTwo a

(ShowLaTeX a, Eq a, Ring a) => ShowLaTeX (RootTwo a)

Methods

showlatex :: RootTwo a -> String

showlatex_p :: Int -> RootTwo a -> ShowS

HalfRing a => RealPart (Omega a) (RootTwo a)

Methods

real :: Omega a -> RootTwo a

ToDyadic a b => ToDyadic (RootTwo a) (RootTwo b)

Methods

maybe_dyadic :: RootTwo a -> Maybe (RootTwo b)

Residue a b => Residue (RootTwo a) (RootTwo b)

Methods

residue :: RootTwo a -> RootTwo b

Nat m => Show (Matrix m n DRComplex)

Methods

showsPrec :: Int -> Matrix m n DRComplex -> ShowS

show :: Matrix m n DRComplex -> String

showList :: [Matrix m n DRComplex] -> ShowS

Nat m => Show (Matrix m n DRootTwo)

Methods

showsPrec :: Int -> Matrix m n DRootTwo -> ShowS

show :: Matrix m n DRootTwo -> String

showList :: [Matrix m n DRootTwo] -> ShowS

Nat n => ShowLaTeX (Matrix n m DRComplex)

Methods

showlatex :: Matrix n m DRComplex -> String

showlatex_p :: Int -> Matrix n m DRComplex -> ShowS

The ring ℤ[√2]

type ZRootTwo = RootTwo Integer

The ring ℤ[√2].

zroottwo_root :: ZRootTwo -> Maybe ZRootTwo

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

The ring D[√2]

type DRootTwo = RootTwo Dyadic

The ring D[√2] = ℤ[1/√2].

The field ℚ[√2]

type QRootTwo = RootTwo Rationals

The field ℚ[√2].

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

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]

data Cplx a

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.

Constructors

Cplx !a !a

Instances

Show DRComplex

Methods

showsPrec :: Int -> DRComplex -> ShowS

show :: DRComplex -> String

showList :: [DRComplex] -> ShowS

EuclideanDomain ZComplex

Methods

rank :: ZComplex -> Integer

divmod :: ZComplex -> ZComplex -> (ZComplex, ZComplex)

Eq a => Eq (Cplx a)

Methods

(==) :: Cplx a -> Cplx a -> Bool

(/=) :: Cplx a -> Cplx a -> Bool

Fractional a => Fractional (Cplx a)

Methods

(/) :: Cplx a -> Cplx a -> Cplx a

recip :: Cplx a -> Cplx a

fromRational :: Rational -> Cplx a

Num a => Num (Cplx a)

Methods

(+) :: Cplx a -> Cplx a -> Cplx a

(-) :: Cplx a -> Cplx a -> Cplx a

(*) :: Cplx a -> Cplx a -> Cplx a

negate :: Cplx a -> Cplx a

abs :: Cplx a -> Cplx a

signum :: Cplx a -> Cplx a

fromInteger :: Integer -> Cplx a

(Eq a, Show a, Num a) => Show (Cplx a)

Methods

showsPrec :: Int -> Cplx a -> ShowS

show :: Cplx a -> String

showList :: [Cplx a] -> ShowS

ToQOmega a => ToQOmega (Cplx a)

Methods

toQOmega :: Cplx a -> QOmega

DenomExp a => DenomExp (Cplx a)

Methods

denomexp :: Cplx a -> Integer

denomexp_factor :: Cplx a -> Integer -> Cplx a

NormedRing a => NormedRing (Cplx a)

Methods

norm :: Cplx a -> Integer

(Adjoint2 a, Ring a) => Adjoint2 (Cplx a)

Methods

adj2 :: Cplx a -> Cplx a

(Adjoint a, Ring a) => Adjoint (Cplx a)

Methods

adj :: Cplx a -> Cplx a

Ring a => ComplexRing (Cplx a)

Methods

i :: Cplx a

RootHalfRing a => RootHalfRing (Cplx a)

Methods

roothalf :: Cplx a

fromDRootTwo :: DRootTwo -> Cplx a

RootTwoRing a => RootTwoRing (Cplx a)

Methods

roottwo :: Cplx a

fromZRootTwo :: ZRootTwo -> Cplx a

HalfRing a => HalfRing (Cplx a)

Methods

half :: Cplx a

fromDyadic :: Dyadic -> Cplx a

(ShowLaTeX a, Ring a, Eq a) => ShowLaTeX (Cplx a)

Methods

showlatex :: Cplx a -> String

showlatex_p :: Int -> Cplx a -> ShowS

RealPart (Cplx a) a

Methods

real :: Cplx a -> a

WholePart a b => WholePart (Cplx a) (Cplx b)

Methods

from_whole :: Cplx b -> Cplx a

to_whole :: Cplx a -> Cplx b

ToDyadic a b => ToDyadic (Cplx a) (Cplx b)

Methods

maybe_dyadic :: Cplx a -> Maybe (Cplx b)

Residue a b => Residue (Cplx a) (Cplx b)

Methods

residue :: Cplx a -> Cplx b

Nat m => Show (Matrix m n DRComplex)

Methods

showsPrec :: Int -> Matrix m n DRComplex -> ShowS

show :: Matrix m n DRComplex -> String

showList :: [Matrix m n DRComplex] -> ShowS

Nat n => ShowLaTeX (Matrix n m DRComplex)

Methods

showlatex :: Matrix n m DRComplex -> String

showlatex_p :: Int -> Matrix n m DRComplex -> ShowS

The ring ℤ[i] of Gaussian integers

type ZComplex = Cplx Integer

The ring ℤ[i] of Gaussian integers.

fromZComplex :: ComplexRing a => ZComplex -> a

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

The ring D[i]

type DComplex = Cplx Dyadic

The ring D[i] = ℤ[½, i] of Gaussian dyadic fractions.

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

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

type QComplex = Cplx Rationals

The ring ℚ[i] of Gaussian rationals.

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

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]

type DRComplex = Cplx DRootTwo

The ring D[√2, i] = ℤ[1/√2, i].

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

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]

type QRComplex = Cplx QRootTwo

The field ℚ[√2, i].

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

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.

type CDouble = Cplx Double

Double precision complex floating point numbers.

type CFloat = Cplx Float

Single precision complex floating point numbers.

The ring R[ω]

data Omega a

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ω³+bω²+cω+d.

Constructors

Omega !a !a !a !a

Instances

Show DOmega

Methods

showsPrec :: Int -> DOmega -> ShowS

show :: DOmega -> String

showList :: [DOmega] -> ShowS

DenomExp DOmega

Methods

denomexp :: DOmega -> Integer

denomexp_factor :: DOmega -> Integer -> DOmega

OmegaRing ZOmega

Methods

omega :: ZOmega

EuclideanDomain ZOmega

Methods

rank :: ZOmega -> Integer

divmod :: ZOmega -> ZOmega -> (ZOmega, ZOmega)

ShowLaTeX DOmega

Methods

showlatex :: DOmega -> String

showlatex_p :: Int -> DOmega -> ShowS

ShowLaTeX ZOmega

Methods

showlatex :: ZOmega -> String

showlatex_p :: Int -> ZOmega -> ShowS

WholePart DOmega ZOmega

Methods

from_whole :: ZOmega -> DOmega

to_whole :: DOmega -> ZOmega

Eq a => Eq (Omega a)

Methods

(==) :: Omega a -> Omega a -> Bool

(/=) :: Omega a -> Omega a -> Bool

Fractional a => Fractional (Omega a)

Methods

(/) :: Omega a -> Omega a -> Omega a

recip :: Omega a -> Omega a

fromRational :: Rational -> Omega a

Num a => Num (Omega a)

Methods

(+) :: Omega a -> Omega a -> Omega a

(-) :: Omega a -> Omega a -> Omega a

(*) :: Omega a -> Omega a -> Omega a

negate :: Omega a -> Omega a

abs :: Omega a -> Omega a

signum :: Omega a -> Omega a

fromInteger :: Integer -> Omega a

(Show a, Ring a) => Show (Omega a)

Methods

showsPrec :: Int -> Omega a -> ShowS

show :: Omega a -> String

showList :: [Omega a] -> ShowS

ToQOmega a => ToQOmega (Omega a)

Methods

toQOmega :: Omega a -> QOmega

NormedRing a => NormedRing (Omega a)

Methods

norm :: Omega a -> Integer

(Adjoint2 a, Ring a) => Adjoint2 (Omega a)

Methods

adj2 :: Omega a -> Omega a

(Adjoint a, Ring a) => Adjoint (Omega a)

Methods

adj :: Omega a -> Omega a

OmegaRing (Omega Z2)

Methods

omega :: Omega Z2

Ring a => ComplexRing (Omega a)

Methods

i :: Omega a

HalfRing a => RootHalfRing (Omega a)

Methods

roothalf :: Omega a

fromDRootTwo :: DRootTwo -> Omega a

Ring a => RootTwoRing (Omega a)

Methods

roottwo :: Omega a

fromZRootTwo :: ZRootTwo -> Omega a

HalfRing a => HalfRing (Omega a)

Methods

half :: Omega a

fromDyadic :: Dyadic -> Omega a

ShowLaTeX (Omega Z2)

Methods

showlatex :: Omega Z2 -> String

showlatex_p :: Int -> Omega Z2 -> ShowS

HalfRing a => RealPart (Omega a) (RootTwo a)

Methods

real :: Omega a -> RootTwo a

ToDyadic a b => ToDyadic (Omega a) (Omega b)

Methods

maybe_dyadic :: Omega a -> Maybe (Omega b)

Residue a b => Residue (Omega a) (Omega b)

Methods

residue :: Omega a -> Omega b

Nat m => Show (Matrix m n DOmega)

Methods

showsPrec :: Int -> Matrix m n DOmega -> ShowS

show :: Matrix m n DOmega -> String

showList :: [Matrix m n DOmega] -> ShowS

Nat n => ShowLaTeX (Matrix n m DOmega)

Methods

showlatex :: Matrix n m DOmega -> String

showlatex_p :: Int -> Matrix n m DOmega -> ShowS

omega_real :: Omega a -> a

An inverse to the embedding R ↦ R[ω]: return the "real rational" part. In other words, map aω³+bω²+cω+d to d.

The ring ℤ[ω]

type ZOmega = Omega Integer

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

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

zroottwo_of_zomega :: ZOmega -> ZRootTwo

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

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 :: (RootHalfRing a, ComplexRing a) => DOmega -> a

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

The field ℚ[ω]

type QOmega = Omega Rationals

The field ℚ[ω] of cyclotomic rationals of degree 8.

fromQOmega :: (RootHalfRing a, ComplexRing a, Fractional a) => QOmega -> a

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

Conversion to dyadic

class ToDyadic a b | a -> b where

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

Minimal complete definition

maybe_dyadic

Methods

maybe_dyadic :: a -> Maybe b

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

Instances

ToDyadic Rational Dyadic

Methods

maybe_dyadic :: Rational -> Maybe Dyadic

ToDyadic Rationals Dyadic

Methods

maybe_dyadic :: Rationals -> Maybe Dyadic

ToDyadic Dyadic Dyadic

Methods

maybe_dyadic :: Dyadic -> Maybe Dyadic

ToDyadic a b => ToDyadic (Omega a) (Omega b)

Methods

maybe_dyadic :: Omega a -> Maybe (Omega b)

ToDyadic a b => ToDyadic (Cplx a) (Cplx b)

Methods

maybe_dyadic :: Cplx a -> Maybe (Cplx b)

ToDyadic a b => ToDyadic (RootTwo a) (RootTwo b)

Methods

maybe_dyadic :: RootTwo a -> Maybe (RootTwo b)

ToDyadic a b => ToDyadic (Vector n a) (Vector n b)

Methods

maybe_dyadic :: Vector n a -> Maybe (Vector n b)

ToDyadic a b => ToDyadic (Matrix m n a) (Matrix m n b)

Methods

maybe_dyadic :: Matrix m n a -> Maybe (Matrix m n b)

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

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

Real part

class RealPart a b | a -> b where

A type class for rings that have a "real" component. A typical instance is a = DRComplex with b = DRootTwo.

Minimal complete definition

real

Methods

real :: a -> b

Take the real part.

Instances

RealPart (Cplx a) a

Methods

real :: Cplx a -> a

HalfRing a => RealPart (Omega a) (RootTwo a)

Methods

real :: Omega a -> RootTwo a

Rings of integers

class WholePart a b | a -> b where

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.

Minimal complete definition

from_whole, to_whole

Methods

from_whole :: b -> a

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

to_whole :: a -> b

The inverse of from_whole. Throws an error if the given element is not actually an integer in the ring.

Instances

WholePart () ()

Methods

from_whole :: () -> ()

to_whole :: () -> ()

WholePart DOmega ZOmega

Methods

from_whole :: ZOmega -> DOmega

to_whole :: DOmega -> ZOmega

WholePart DRootTwo ZRootTwo

Methods

from_whole :: ZRootTwo -> DRootTwo

to_whole :: DRootTwo -> ZRootTwo

WholePart Dyadic Integer

Methods

from_whole :: Integer -> Dyadic

to_whole :: Dyadic -> Integer

WholePart a b => WholePart [a] [b]

Methods

from_whole :: [b] -> [a]

to_whole :: [a] -> [b]

WholePart a b => WholePart (Cplx a) (Cplx b)

Methods

from_whole :: Cplx b -> Cplx a

to_whole :: Cplx a -> Cplx b

(WholePart a a', WholePart b b') => WholePart (a, b) (a', b')

Methods

from_whole :: (a', b') -> (a, b)

to_whole :: (a, b) -> (a', b')

WholePart a b => WholePart (Vector n a) (Vector n b)

Methods

from_whole :: Vector n b -> Vector n a

to_whole :: Vector n a -> Vector n b

WholePart a b => WholePart (Matrix m n a) (Matrix m n b)

Methods

from_whole :: Matrix m n b -> Matrix m n a

to_whole :: Matrix m n a -> Matrix m n b

Common denominators

class DenomExp a where

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.

Minimal complete definition

denomexp, denomexp_factor

Methods

denomexp :: a -> Integer

Calculate the least denominator exponent k of a. Returns the smallest k≥0 such that a = b/√2^k for some integral b.

denomexp_factor :: a -> Integer -> a

Factor out a kth power of 1/√2 from a. In other words, calculate a√2^k.

Instances

DenomExp ()

Methods

denomexp :: () -> Integer

denomexp_factor :: () -> Integer -> ()

DenomExp DOmega

Methods

denomexp :: DOmega -> Integer

denomexp_factor :: DOmega -> Integer -> DOmega

DenomExp DRootTwo

Methods

denomexp :: DRootTwo -> Integer

denomexp_factor :: DRootTwo -> Integer -> DRootTwo

DenomExp a => DenomExp [a]

Methods

denomexp :: [a] -> Integer

denomexp_factor :: [a] -> Integer -> [a]

DenomExp a => DenomExp (Cplx a)

Methods

denomexp :: Cplx a -> Integer

denomexp_factor :: Cplx a -> Integer -> Cplx a

(DenomExp a, DenomExp b) => DenomExp (a, b)

Methods

denomexp :: (a, b) -> Integer

denomexp_factor :: (a, b) -> Integer -> (a, b)

DenomExp a => DenomExp (Vector n a)

Methods

denomexp :: Vector n a -> Integer

denomexp_factor :: Vector n a -> Integer -> Vector n a

DenomExp a => DenomExp (Matrix m n a)

Methods

denomexp :: Matrix m n a -> Integer

denomexp_factor :: Matrix m n a -> Integer -> Matrix m n a

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

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

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.

class ToQOmega a where

A type class for things that can be exactly converted to ℚ[ω].

Minimal complete definition

toQOmega

Methods

toQOmega :: a -> QOmega

Conversion to QOmega.

Instances

ToQOmega Integer

Methods

toQOmega :: Integer -> QOmega

ToQOmega Rational

Methods

toQOmega :: Rational -> QOmega

ToQOmega Rationals

Methods

toQOmega :: Rationals -> QOmega

ToQOmega Dyadic

Methods

toQOmega :: Dyadic -> QOmega

ToQOmega a => ToQOmega (Omega a)

Methods

toQOmega :: Omega a -> QOmega

ToQOmega a => ToQOmega (Cplx a)

Methods

toQOmega :: Cplx a -> QOmega

ToQOmega a => ToQOmega (RootTwo a)

Methods

toQOmega :: RootTwo a -> QOmega

Parity

class Parity a where

A type class for things that have parity.

Minimal complete definition

parity

Methods

parity :: a -> Z2

Return the parity of something.

Instances

Integral a => Parity a

Methods

parity :: a -> Z2

Parity ZRootTwo

Methods

parity :: ZRootTwo -> Z2

Auxiliary functions

lobit :: Integer -> Integer

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

If n is of the form 2^k, return k. Otherwise, return Nothing.

hibit :: Integer -> Int

Return 1 + the position of the leftmost "1" bit of a non-negative Integer. Do this in time O(n log n), where n is the size of the integer (in digits).

intsqrt :: Integral n => n -> n

For n ≥ 0, return the floor of the square root of n. This is done using integer arithmetic, so there are no rounding errors.