|
|
|
|
|
|
|
|
|
|
|
# Numeric Classes
|
|
|
|
|
|
|
|
|
|
|
|
The Haskell 98 numeric classes were designed to classify the operations
|
|
|
supported by the Haskell 98 types, `Integer`, `Int`, `Float`, `Double`,
|
|
|
`Complex` and `Ratio`. However they are not suitable for other mathematical
|
|
|
objects.
|
|
|
|
|
|
|
|
|
|
|
|
If the Haskell 98 classes were retained for backwards compatibility, but with a more refined class hierarchy, the change would impact mostly on those defining instances (and these are the people inconvenienced by the current system).
|
|
|
Clients of the classes would notice only some more general types.
|
|
|
|
|
|
|
|
|
## References
|
|
|
|
|
|
- other [Issues with Standard Classes](standard-classes)
|
|
|
|
|
|
- [ Standard Haskell Classes](http://www.haskell.org/onlinereport/basic.html#sect6.3) of Haskell 98
|
|
|
- [ Standard Prelude](http://www.haskell.org/onlinereport/standard-prelude.html) of Haskell 98
|
|
|
- [ Basic Algebra Proposal](ftp://ftp.botik.ru/pub/local/Mechveliani/basAlgPropos/)
|
|
|
- [ DoCon the Algebraic Domain Constructor](http://www.haskell.org/docon/)
|
|
|
- [ Numeric prelude project](http://www.haskell.org/communities/06-2006/html/report.html#numericprelude)
|
|
|
|
|
|
### Some standard algebraic structures
|
|
|
|
|
|
|
|
|
|
|
|
This is a partial list of common structures from abstract algebra.
|
|
|
Structures further down and/or to the right are special cases of those further up and/or to the left:
|
|
|
|
|
|
<table><tr><th>[ Monoid](http://en.wikipedia.org/wiki/Monoid)</th>
|
|
|
|
|
|
<table><tr><th> [ Monoid](http://en.wikipedia.org/wiki/Monoid) </th>
|
|
|
<th> Commutative monoid
|
|
|
</th>
|
|
|
<th></th></tr>
|
|
|
<tr><th>[ Group](http://en.wikipedia.org/wiki/Group_%28mathematics%29)</th>
|
|
|
<th>[ Abelian group](http://en.wikipedia.org/wiki/Abelian_group)</th>
|
|
|
<tr><th> [ Group](http://en.wikipedia.org/wiki/Group) </th>
|
|
|
<th> [ Abelian group](http://en.wikipedia.org/wiki/Abelian_group)
|
|
|
</th>
|
|
|
<th></th></tr>
|
|
|
<tr><th></th>
|
|
|
<th>[ Ring](http://en.wikipedia.org/wiki/Ring_%28mathematics%29)</th>
|
|
|
<th>[ Commutative ring](http://en.wikipedia.org/wiki/Commutative_ring)</th></tr>
|
|
|
<tr><th></th>
|
|
|
<th>[ Domain](http://en.wikipedia.org/wiki/Domain_%28ring_theory%29)</th>
|
|
|
<th>[ Integral domain](http://en.wikipedia.org/wiki/Integral_domain)</th></tr>
|
|
|
<tr><th></th>
|
|
|
<th></th>
|
|
|
<th>[ Unique factorization domain](http://en.wikipedia.org/wiki/Unique_factorization_domain)</th></tr>
|
|
|
<tr><th></th>
|
|
|
<th></th>
|
|
|
<th>[ Principal ideal domain](http://en.wikipedia.org/wiki/Principal_ideal_domain)</th></tr>
|
|
|
<tr><th></th>
|
|
|
<th></th>
|
|
|
<th>[ Euclidean domain](http://en.wikipedia.org/wiki/Euclidean_domain)</th></tr>
|
|
|
<tr><th></th>
|
|
|
<th>[ Division ring](http://en.wikipedia.org/wiki/Division_ring)</th>
|
|
|
<th>[ Field](http://en.wikipedia.org/wiki/Field_%28mathematics%29)</th></tr></table>
|
|
|
|
|
|
|
|
|
See also [ Semiring](http://en.wikipedia.org/wiki/Semiring), which also lies between commutative monoid and ring.
|
|
|
<tr><th> </th>
|
|
|
<th> [ Ring](http://en.wikipedia.org/wiki/Ring) </th>
|
|
|
<th> [ Commutative ring](http://en.wikipedia.org/wiki/Commutative_ring)
|
|
|
</th></tr>
|
|
|
<tr><th> </th>
|
|
|
<th> [ Domain](http://en.wikipedia.org/wiki/Domain) </th>
|
|
|
<th> [ Integral domain](http://en.wikipedia.org/wiki/Integral_domain)
|
|
|
</th></tr>
|
|
|
<tr><th> </th>
|
|
|
<th> </th>
|
|
|
<th> [ Unique factorization domain](http://en.wikipedia.org/wiki/Unique_factorization_domain)
|
|
|
</th></tr>
|
|
|
<tr><th> </th>
|
|
|
<th> </th>
|
|
|
<th> [ Principal ideal domain](http://en.wikipedia.org/wiki/Principal_ideal_domain)
|
|
|
</th></tr>
|
|
|
<tr><th> </th>
|
|
|
<th> </th>
|
|
|
<th> [ Euclidean domain](http://en.wikipedia.org/wiki/Euclidean_domain)
|
|
|
</th></tr>
|
|
|
<tr><th> </th>
|
|
|
<th> [ Division ring](http://en.wikipedia.org/wiki/Division_ring) </th>
|
|
|
<th> [ Field](http://en.wikipedia.org/wiki/Field)
|
|
|
</th></tr></table>
|
|
|
|
|
|
|
|
|
## The Num class
|
|
|
|
|
|
|
|
|
|
|
|
Issues:
|
|
|
|
|
|
|
|
|
- `Eq` and `Show` don't make sense for functions under lifting.
|
|
|
- `(*)` doesn't make sense for vectors.
|
|
|
- `abs` and `signum` don't make sense for `Complex Integer` (Gaussian integers), vectors, matrices, etc.
|
... | ... | @@ -66,6 +81,7 @@ Issues: |
|
|
|
|
|
Proposals:
|
|
|
|
|
|
|
|
|
- A group-like class with `zero`, `(+)` and `negate`/`(-)`.
|
|
|
- (Could be further split with a monoid sub-class.)
|
|
|
- A ring-like subclass adding `(*)` and `one`/`fromInteger`, with the existing `Num` class as a further subclass.
|
... | ... | @@ -75,56 +91,62 @@ Proposals: |
|
|
Note that the `Float` and `Double` instances will not satisfy the usual axioms for these structures.
|
|
|
|
|
|
|
|
|
|
|
|
Proposed new classes:
|
|
|
|
|
|
|
|
|
```wiki
|
|
|
class AbelianGroup a where -- could also factor out Monoid
|
|
|
zero :: a
|
|
|
(+), (-) :: a -> a -> a
|
|
|
negate :: a -> a
|
|
|
zero :: a
|
|
|
(+), (-) :: a -> a -> a
|
|
|
negate :: a -> a
|
|
|
|
|
|
-- Minimal complete definition:
|
|
|
-- zero, (+) and (negate or (-))
|
|
|
negate x = zero - x
|
|
|
x - y = x + negate y
|
|
|
-- Minimal complete definition:
|
|
|
-- zero, (+) and (negate or (-))
|
|
|
negate x = zero - x
|
|
|
x - y = x + negate y
|
|
|
|
|
|
class AbelianGroup a => Ring a where
|
|
|
(*) :: a -> a -> a
|
|
|
one :: a
|
|
|
fromInteger :: Integer -> a
|
|
|
|
|
|
-- Minimal complete definition:
|
|
|
-- (*) and (one or fromInteger)
|
|
|
one = fromInteger 1
|
|
|
fromInteger n
|
|
|
| n < 0 = negate (fi (negate n))
|
|
|
| otherwise = fi n
|
|
|
where fi 0 = zero
|
|
|
fi 1 = one
|
|
|
fi n
|
|
|
| even n = fin + fin
|
|
|
| otherwise = fin + fin + one
|
|
|
where fin = fi (n `div` 2)
|
|
|
(*) :: a -> a -> a
|
|
|
one :: a
|
|
|
fromInteger :: Integer -> a
|
|
|
|
|
|
-- Minimal complete definition:
|
|
|
-- (*) and (one or fromInteger)
|
|
|
one = fromInteger 1
|
|
|
fromInteger n
|
|
|
| n < 0 = negate (fi (negate n))
|
|
|
| otherwise = fi n
|
|
|
where fi 0 = zero
|
|
|
fi 1 = one
|
|
|
fi n
|
|
|
| even n = fin + fin
|
|
|
| otherwise = fin + fin + one
|
|
|
where fin = fi (n `div` 2)
|
|
|
```
|
|
|
|
|
|
|
|
|
Haskell 98 compatibility class:
|
|
|
|
|
|
|
|
|
```wiki
|
|
|
class (Eq a, Show a, Ring a) => Num a where
|
|
|
abs, signum :: a -> a
|
|
|
abs, signum :: a -> a
|
|
|
```
|
|
|
|
|
|
## The Fractional class
|
|
|
|
|
|
|
|
|
|
|
|
Issues:
|
|
|
|
|
|
|
|
|
- `(/)`, `recip` and `fromRational` can be lifted to functions, but many of the pre-requisites can't be defined for these.
|
|
|
|
|
|
|
|
|
Proposals:
|
|
|
|
|
|
|
|
|
- Add a division ring-like superclass adding these operations to the ring-like class.
|
|
|
(A division ring has the same operations as a field, but does not assume commutative multiplication, allowing structures such as quaternions.)
|
|
|
- Add default
|
... | ... | @@ -138,18 +160,19 @@ Proposals: |
|
|
|
|
|
Proposed new classes:
|
|
|
|
|
|
|
|
|
```wiki
|
|
|
class Ring a => DivisionRing a where
|
|
|
(/) :: a -> a -> a
|
|
|
recip :: a -> a
|
|
|
fromRational :: Rational -> a
|
|
|
(/) :: a -> a -> a
|
|
|
recip :: a -> a
|
|
|
fromRational :: Rational -> a
|
|
|
|
|
|
-- Minimal complete definition:
|
|
|
-- recip or (/)
|
|
|
recip x = one / x
|
|
|
x / y = x * recip y
|
|
|
fromRational x = fromInteger (numerator x) /
|
|
|
fromInteger (denominator x)
|
|
|
-- Minimal complete definition:
|
|
|
-- recip or (/)
|
|
|
recip x = one / x
|
|
|
x / y = x * recip y
|
|
|
fromRational x = fromInteger (numerator x) /
|
|
|
fromInteger (denominator x)
|
|
|
|
|
|
class DivisionRing a => Field a
|
|
|
```
|
... | ... | @@ -157,6 +180,7 @@ class DivisionRing a => Field a |
|
|
|
|
|
Haskell 98 compatibility class:
|
|
|
|
|
|
|
|
|
```wiki
|
|
|
class (Num a, Field a) => Fractional a
|
|
|
```
|
... | ... | @@ -164,100 +188,86 @@ class (Num a, Field a) => Fractional a |
|
|
## The Real class
|
|
|
|
|
|
|
|
|
|
|
|
Issues:
|
|
|
|
|
|
|
|
|
- The class assumes a mapping to `Rational`, but this cannot be defined for structures intermediate between the rationals and reals even though the operations of subclasses make sense for them, e.g. surds, computable reals.
|
|
|
|
|
|
|
|
|
Proposal:
|
|
|
|
|
|
|
|
|
- Retain the class for backward compatibility only.
|
|
|
|
|
|
## The Integral class
|
|
|
|
|
|
|
|
|
|
|
|
Issues:
|
|
|
|
|
|
|
|
|
- Division with remainder also makes sense for polynomials and Gaussian
|
|
|
integers, but not `Enum`, `toInteger`, `Ord`, `Num(abs, signum)` or
|
|
|
`toRational`. Provided any non-zero remainder is "smaller" than
|
|
|
the divisor, in some well-founded sense, Euclid's algorithm terminates.
|
|
|
- Defining `Ratio` also requires a canonical factorization of any
|
|
|
element as *x* as *y*`*`*u* where *u* is an invertible element
|
|
|
element as *x* as *u*`*`*y* where *u* is an invertible element
|
|
|
(or *unit*). Any such *y* is called an *associate* of *x*.
|
|
|
For integral types (but not others), this is similar to `signum` and
|
|
|
`abs`, but the general idea makes sense for any integral domain.
|
|
|
- These could be combined in a class of Euclidean domains, or there could be
|
|
|
an intermediate class of integral domains. In the latter case division
|
|
|
would not be available for defining defaults.
|
|
|
- In algebra, each field is trivially a Euclidean domain, with the remainder
|
|
|
always zero. However this would break backwards compatibility, as well as
|
|
|
the programming languages convention of distinguishing integer division.
|
|
|
|
|
|
|
|
|
Proposal:
|
|
|
|
|
|
- Add a Euclidean domain class, with canonical factorization satisfying
|
|
|
|
|
|
```wiki
|
|
|
stdAssociate x * stdUnit x = x
|
|
|
stdUnit (x*y) = stdUnit x * stdUnit y
|
|
|
stdUnit x * (one `div` stdUnit x) = x
|
|
|
x*y = one => stdUnit x = x
|
|
|
```
|
|
|
|
|
|
and either `divMod` or `quotRem`.
|
|
|
- (Could be further split by placing canonical factorization in an integral
|
|
|
domain class, but division would not be available for default definitions,
|
|
|
and would also need to supply the reciprocal of `stdUnit x`.)
|
|
|
|
|
|
|
|
|
Proposed new class:
|
|
|
|
|
|
|
|
|
```wiki
|
|
|
class Ring a => EuclideanDomain a where
|
|
|
stdAssociate :: a -> a
|
|
|
stdUnit :: a -> a
|
|
|
normalize :: a -> (a, a)
|
|
|
|
|
|
div, mod :: a -> a -> a
|
|
|
divMod :: a -> a -> (a,a)
|
|
|
|
|
|
-- Minimal complete definition:
|
|
|
-- (stdUnit or normalize) and (divMod or (div and mod))
|
|
|
stdAssociate x = x `div` stdUnit x
|
|
|
stdUnit x = snd (normalize x)
|
|
|
normalize x = (stdAssociate x, stdUnit x)
|
|
|
|
|
|
n `divMod` d = (n `div` d, n `mod` d)
|
|
|
n `div` d = q where (q,r) = divMod n d
|
|
|
n `mod` d = r where (q,r) = divMod n d
|
|
|
div, mod :: a -> a -> a
|
|
|
divMod :: a -> a -> (a,a)
|
|
|
|
|
|
stdAssociate :: a -> a
|
|
|
stdUnit :: a -> a
|
|
|
|
|
|
-- Minimal complete definition:
|
|
|
-- (divMod or (div and mod)) and stdUnit
|
|
|
n `divMod` d = (n `div` d, n `mod` d)
|
|
|
n `div` d = q where (q,r) = divMod n d
|
|
|
n `mod` d = r where (q,r) = divMod n d
|
|
|
|
|
|
stdAssociate x = x `div` stdUnit x
|
|
|
```
|
|
|
|
|
|
|
|
|
Haskell 98 compatibility class:
|
|
|
|
|
|
|
|
|
```wiki
|
|
|
class (Real a, Enum a, EuclideanDomain a) => Integral a where
|
|
|
quot, rem :: a -> a -> a
|
|
|
quotRem :: a -> a -> (a,a)
|
|
|
toInteger :: a -> Integer
|
|
|
|
|
|
-- Minimal complete definition:
|
|
|
-- toInteger
|
|
|
n `quot` d = q where (q,r) = quotRem n d
|
|
|
n `rem` d = r where (q,r) = quotRem n d
|
|
|
quotRem n d = if signum r == - signum d then (q+one, r-d) else qr
|
|
|
where qr@(q,r) = divMod n d
|
|
|
quot, rem :: a -> a -> a
|
|
|
quotRem :: a -> a -> (a,a)
|
|
|
toInteger :: a -> Integer
|
|
|
|
|
|
-- Minimal complete definition:
|
|
|
-- toInteger
|
|
|
n `quot` d = q where (q,r) = quotRem n d
|
|
|
n `rem` d = r where (q,r) = quotRem n d
|
|
|
quotRem n d = if signum r == - signum d then (q+one, r-d) else qr
|
|
|
where qr@(q,r) = divMod n d
|
|
|
```
|
|
|
|
|
|
## The RealFloat class
|
|
|
|
|
|
|
|
|
|
|
|
Issues:
|
|
|
|
|
|
|
|
|
- The class groups together the trigonometric operation `atan2` with
|
|
|
operations on the components of floating-point numbers. |
|
|
|
|
|
## Proposals
|
|
|
|
|
|
1. add new subclasses for groups, rings, division rings and Euclidean domains, as above.
|
|
|
1. as 1, plus additional subclasses that do not assume negation (monoid, semiring, etc).
|
|
|
This would make most sense if we had [natural numbers](natural). |