Fixing the Num hierarchy for Great Good
The Haskell numerical hierarchy is now dust, scattered to the winds.
It should come as no surprise to anyone following my work, that if I am complaining about something, it is probably because I am working on fixing it. There is very little point to moaning about something if you aren’t willing to do something about it. One of the things that I have complained about most, is the Num hierarchy, and so *snap*.
The deconstruction of the Bits class such that it butts up against the bottom of the Num hierarchy just begs for unification, and the game engine that I am slowly but inevitably building with all of these things (math, memory, cryptography) requires a level mathematical precision that the base does not allow. If you’ve seen my postings about not just Boolean but Logic and Lattice, well, this is where that has been leading.
Here goes: I am giving Haskell the math library that it deserves.
The problem
It has always bothered me that Haskell, supposedly one of the best programming languages, has what is hands-down almost objectively one of the worst built-in math libraries.
Take, for example, that:
- syntactic operators are defined as part of critical typeclass definitions
- Literal support and conversion requires full arithmetic implementations
- we have three different power operators -
^,^^, and** - the definition of Num / Fractional fundamentally disallow instances for vectors and polynomials and etc
- It is impossible to support things like symbolic math
This causes heaps of problems, ranging from subtle things like having partial Num implementations just to access fromInteger, to more obviously destructive effects, such as the explosion of operators in libraries like linear. Implementing things is a pain in the arse - have you memorized the hierarchy, can you tell me what class fromRational is defined in?
There are two major distinct issues that cause most of these problems, and they can be solved with the same resolution - they are the primary causes of the issues in the Num hierarchy, with most other effects being secondary to one of them:
- Literal syntactic support being tied to numeric / ring behavior
- The implicit assumption of homogenous operations in a field (hah) that is often heterogenous
The former is an issue because I shouldn’t have to implement (+), (-), (*), negate, abs, signum just to get access to fromInteger for a type that is representable as an integer but fundamentally isn’t one, eg bit flags and mask enums, and the latter because it ignores heterogenous math like vector-scalar operations, and how exponentiation actually results in complex numbers (remind me, what is the square root of -1 again?).
Now, there is a explanation for all of this - the numerical hierarchy was one of the first things written, way back in the before times, and everything depends on it - it literally predates the modern type system capabilities. But an explanation isn’t a valid reason to not to improve things, so I’ve gone and done something about that.
It’s not finished yet, but it is time for a sneak peek at the new mathematical hierarchy, that allows for heterogenous math and the consolidation of a great number of many operators into single symbols.
Literal expressions
To start, literals have been separated from actual numeric requirements, to allow for numeric literals to be used for other things, and to eg allow for symbolic math, bit flags, things that can be represented as a number, but don’t support addition or multiplication or such.
-- Integer literals
class ExpressibleByIntegerLiteral a where
fromIntegerLiteral :: Integer -> a
class
( ExpressibleByIntegerLiteral a
) => ConvertibleToIntegerLiteral a where
toIntegerLiteral :: a -> Integer
-- Rational literals
class ExpressibleByRationalLiteral a where
fromRationalLiteral :: Rational -> a
class
( ExpressibleByRationalLiteral a
) => ConvertibleToRationalLiteral a where
toRationalLiteral :: a -> Rational
-- String literals
class ExpressibleByStringLiteral a where
fromStringLiteral :: String -> a
class
( ExpressibleByStringLiteral a
) => ConvertibleToStringLiteral a where
toStringLiteral :: a -> String
-- List literals TBD
These will be used with RebindableSyntax later.
Arithmetic
Arithmetic operations have been split off, and follow a specific sub-hierarchy:
HeterogenousOperation =>
OperativeSemigroup =>
OperativeMonoid =>
OperativeGroup
One of the key things I have instituted is that the heterogenous operations have more colloquial names, and the homogenous operatives with associated properties have the more mathematical nomenclature - this pattern is followed library-wide
Addition and subtraction
class Addition a b where
type Sum a b :: Type
plus :: a -> b -> Sum a b
class (Addition a a, Sum a a ~ a) => AdditiveSemigroup a where
add :: a -> a -> a
add = plus
class AdditiveSemigroup a => AdditiveMonoid a where
zero :: a
class Subtraction a b where
type Delta a b :: Type
minus :: a -> b -> Delta a b
type SubtractiveMagma a = (Subtraction a a, Delta a a ~ a)
class (AdditiveMonoid a, SubtractiveMagma => AdditiveGroup a where
neg :: a -> a
sub :: a -> a -> a
sub = minus
Multiplication and division
Note that euclidean division is separate from fractional division, and that idiv is differentiated from div, although div may be implemented as idiv for eg Integrals.
class Multiplication a b where
type Product a b :: Type
times :: a -> b -> Product a b
class Division a b where
type Ratio a b :: Type
divides :: a -> b -> Ratio a b
type DivisiveMagma a = (Division a a, Ratio a a ~ a)
-- NOTE: Am probably going to make this heterogenous too
class (Division a a) => EuclideanDivision a where
type Quotient a :: Type
type Remainder a :: Type
quotRem :: a -> a -> (Quotient a, Remainder a)
quot :: a -> a -> Quotient a
rem :: a -> a -> Remainder a
idivMod :: a -> a -> (Quotient a, Remainder a)
idiv :: a -> a -> Quotient a
mod :: a -> a -> Remainder a
class (Multiplication a a, Product a a ~ a) => MultiplicativeSemigroup a where
mul :: a -> a -> a
mul = times
class MultiplicativeSemigroup a => MultiplicativeMonoid a where
one :: a
class (MultiplicativeMonoid a, DivisiveMagma a) => MultiplicativeGroup a where
recip :: a -> a
div :: a -> a -> a
div = divides
Exponentiation, Logarithms, and Radication
These are currently in-progress due to the complicated nature of exponentiation being an arithmetic operation but logarithms being a transcendental operation. There is a subtle difference between ‘exponentiation’ and ‘exponential fields’.
class Exponentiation a b where
type Power a b :: Type
pow :: a -> b -> Power a b
class (Exponentiation a b, Power a b ~ a, Integral b) => IntegralPower a b where
ipow :: a -> b -> Power a b
class (Floating a, Exponentiation a a, Power a a ~ a) => FloatingPower a where
fpow :: a -> a -> Power a a
-- TBD - radication as the arithmetic
Rebindable syntax
You will probably want to use RebindableSyntax with this library, and to import the respective module that provides:
import Prelude (Eq(..), Ord(..), (>>=), (>>), fail)
fromInteger :: ExpressibleByIntegerLiteral a => Integer -> a
fromInteger = fromIntegerLiteral
fromRational :: ExpressibleByRationalLiteral a => Rational -> a
fromRational = fromRationalLiteral
fromString :: ExpressibleByStringLiteral a => String -> a
fromString = fromStringLiteral
negate :: (AdditiveGroup a) => a -> a
negate = neg
{-# INLINE negate #-}
ifThenElse :: Bool -> a -> a -> a
ifThenElse c t f = if c then t else f
{-# INLINE ifThenElse #-}
This module is incredibly useful, as we begin hijacking Haskell’s syntax to shim our own classes, thus making 0 :: Int call fromIntegerLiteral from our ExpressibleByIntegerLiteral classes, bypassing Num entirely.
Operators
Operators have been defined in their own module to allow for ease of selection.
Suites of both heterogenous and homogenous operators are provided - here are the heterogenous operators for example:
infixr 8 ^
infixl 7 *, /
infixl 6 +, -
(+) :: (Addition a b) => a -> b -> Sum a b
a + b = plus a b
(-) :: (Subtraction a b) => a -> b -> Delta a b
a - b = minus a b
(*) :: (Multiplication a b) => a -> b -> Product a b
a * b = times a b
(/) :: (Division a b) => a -> b -> Ratio a b
a / b = divides a b
(^) :: (Exponentiation a b) => a -> b -> Power a b
a ^ b = pow a b
Between rebindable syntax and operators, we can now use standard x + y syntax. Now, type families do inhibit type inference, and so the heterogenous operators do not play well with un-typed literals eg x + 0 will probably complain that it doesn’t know what type 0 is since heterogenous math means it can’t infer it from x - but if that is a problem, you can use the homogenous operators, which are a lot better in that regard
Rings and Fields
These are just convenient type aliases that really help make constraint declarations smaller.
-- Proper naturals (lacking zero) are only semirings
type Semiring a = (AdditiveSemigroup a, MultiplicativeSemigroup a)
-- Integers are only rings
type Ring a = (AdditiveGroup a, MultiplicativeMonoid a)
-- Reals are a field
-- Technically, a skew field or division ring - apparently there is very little
-- difference, and are the exact same thing for finite rings / fields
type NonZero a = a -- A hack for now
type Field a = (Ring a, MultiplicativeGroup (NonZero a))
-- TODO: Include OrderedField, etc
Logarithmic
Logarithms / the exponential field is part of the transcendentals
-- NOTE: I may split into Exponential and Logarithmic
class (Field a, FloatingPower a) => Exponential a where
exp :: a -> a
log :: a -> a
logBase :: a -> a -> a
logBase b x = div (log x) (log b)
Trigonometry
Also part of the transcendentals.
class (Field a) => Trigonometric a where
pi :: a
sin :: a -> a
cos :: a -> a
tan :: a -> a
asin :: a -> a
acos :: a -> a
atan :: a -> a
atan2 :: a -> a -> a
Epsilon
class Epsilon a where
epsilon :: a
-- Near with absolute error
nearEq :: a -> a -> Bool
-- Near with relative error
near :: a -> a -> Bool
Signs for number lines
These are prequisites for defining our numeric types.
The ‘signed’ class is as close a definition to the ‘reals’ as I can get, when combined with IsReal later down the line.
class (Ord a) => Signed a where
type Sign a :: Type -- eg Pos | Zero | Neg, but extendable
-- See: UniversalSign
sign :: a -> Sign a
abs :: a -> a
signum :: a -> a
isNegative :: a -> Bool
isZero :: a -> Bool
isPositive :: a -> Bool
-- NOTE: This are here instead of in their respective classes, to allow for
-- the classes to support the actual values
isEpsilon :: a -> Bool
isInfinite :: a -> Bool
isNegativeZero :: (Signed a) => a -> Bool
isPositiveZero :: (Signed a) => a -> Bool
isNegativeInfinite :: (Signed a) => a -> Bool
isPositiveInfinite :: (Signed a) => a -> Bool
isNegativeEpsilon :: (Signed a) => a -> Bool
isPositiveEpsilon :: (Signed a) => a -> Bool
data SimpleSign = Pos | Zero | Neg
data UniversalSign
= NegativeInfinity | Negative | NegativeEpsilon
| NegativeZero | NeutralZero | PositiveZero
| PositiveEpsilon | Positive | PositiveInfinity
-- NOTE: These have to be classes because you can have signed numbers with
-- unsigned infinity
-- Projectively extended reals
class (Signed a) => Infinity a where
infinity :: a
-- Hyperreals
-- NOTE: Infinitesimals are implicitly signed due to their definition as being
-- in the range between -epsilon and +epsilon
class (Signed a) => Infinitesimal a where
infinitesimal :: a
negativeInfinitesimal :: a
-- Extended reals if + Infinitesimal
class (Infinity a) => SignedInfinity a where
positiveInfinity :: a
positiveInfinity = infinity
negativeInfinity :: a
type Surreal a = (SignedInfinity a, Infinitesimal a)
-- Don't forget your NaN!
class NaN a where
isNaN :: a -> Bool
Yeah, you read that right - this library is powerful enough to support hyperreals and extended reals without any special requirements.
Rounding
Ironically, also a prequisite for defining our numeric tpyes
-- TBD - some sort of `Integral (Whole a)` constraint probably
class ProperFraction a where
type Whole a :: Type
-- TODO: Maybe Fraction a?
properFraction :: a -> (Whole a, {- Fraction -} a)
whole :: a -> Whole a
whole = fst . properFraction
fraction :: a -> a
fraction = snd . properFraction
class (ProperFraction a) => Rounded a where
truncate :: a -> Whole a -- Towards zero
round :: a -> Whole a -- Towards nearest whole
class (Rounded a) => DirectedRounded a where
ceiling :: a -> Whole a -- Towards positive infinity
floor :: a -> Whole a -- Towards negative infinity
Finally, Numbers
We now get to define the original hierarchy, stripped of non-essentials, with minor nomenclatural differences.
class (Signed a, Semiring a) => IsNumber a where
fromInteger :: Integer -> a
-- NOTE: If we rename this to IsRational, Signed can be renamed Real?
class (IsNumber a, Ord a) => IsReal a where
toRational :: a -> Rational
-- NOTE: No IsWhole class
class (IsReal a) => IsNatural a where
fromNatural :: Natural -> a
class (IsNatural a, Ring a) => IsIntegral a where
toInteger :: a -> Integer
class (IsNumber a, Field a) => IsFractional a where
fromRational :: Rational -> a
-- I am still pondering these two things:
-- class (IsIntegral a, IsFractional a) => IsRational a where
type IsRealFrac a = (IsReal a, DirectedRounded a {- , ProperFraction a -})
-- NOTE: This could be cleaned up further but it is not critical
-- NOTE: NaN, infinites negative zeroes are now handled by Signed
class (IsRealFrac a, Floating a) => IsFloating a where
floatRadix :: a -> Integer
floatDigits :: a -> Int
floatRange :: a -> (Int, Int)
decodeFloat :: a -> (Integer, Int)
encodeFloat :: Integer -> Int -> a
exponent :: a -> Int
significand :: a -> a
scaleFloat :: Int -> a -> a
isDenormalized :: a -> Bool
isIEEE :: a -> Bool
But why?
So I can do this:
class
( AdditiveGroup v
, Field (Scalar v)
) => VectorSpace v where
type Scalar v :: Type
scale :: Scalar v -> v -> v
default scale :: (VectorScalarMul v) => Scalar v -> v -> v
scale = flip times
mulS :: (VectorSpace v, VectorScalarMul v) => v -> Scalar v -> v
mulS = times
divS :: (VectorSpace v, VectorScalarDiv v) => v -> Scalar v -> v
divS = divides
type VectorScalarAdd v =
(Addition v (Scalar v), Sum v (Scalar v) ~ v)
type VectorScalarSub v =
(Subtraction v (Scalar v), Delta v (Scalar v) ~ v)
type VectorScalarMul v =
(Multiplication v (Scalar v), Product v (Scalar v) ~ v)
type VectorScalarDiv v =
(Division v (Scalar v), Ratio v (Scalar v) ~ v)
Oh! OH! Now I can do V3 1 2 3 * 4, but 1 * 2 still works, with the same operator, due to our heterogenous math. This is a massive improvement over libraries like linear that require using the following operators (and most other vector libraries follow similar conventions):
- (^+^)
- (^-^)
- (^*)
- (*^)
- (^/)
- (.-.)
- (.+^)
- (.-^)
Do you know what these do off the top of your head? I don’t! But we don’t have to - we get to use +, -, *, /, and ^.
Not only that, but because we defined heterogenous operations, it is also trivial to make instances for addition and subtraction of affine points with vectors, which is ALSO heterogenous.
Again, we just use plus and minus and stuff:
class
( VectorSpace (Diff p)
) => AffineSpace p where
type Diff p :: Type
translate :: p -> Diff p -> p -- alt name: offset
default translate :: (Addition p (Diff p), Sum p (Diff p) ~ p) => p -> Diff p -> p
translate = plus
diff :: p -> p -> Diff p
default diff :: (Subtraction p p, Delta p p ~ Diff p) => p -> p -> Diff p
diff = minus
Coming Soon: The Full Geometric Suite
What I have described so far, is only about half of what is coming down the pipeline; I have a full implementation of geometric algebra, with support for quadratic, inner, normed exterior, dual, projective, and conformal spaces, including grades blades and multivectors, all of which is only made possible by the deconstruction of the original numerical hierarchy.
I know this has been a huge code splat with very little context, so if you are still with me, thank you for reading! I’ll try to get an actual library pushed out sooner rather than later (I need it for memalloc, which I need for botan, which I need for my game engine! Vroom!)
for comparison, to learn from, and to help make sure I am covering all of the necessary concepts; putting this all together in an ergonomic format has been a challenge, and I can imagine this difficulty might have contributed to 
but I think I prefer my own foundation lain on heterogenous math, and its totally a personal opinion but I still consider defining symbol operators as part of typeclasses to be a crime against interoperability.