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 SubtractiveSemigroup a = (Subtraction a a, Delta a a ~ a)

class (AdditiveMonoid a, SubtractiveSemigroup) => 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 DivisiveSemigroup 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, DivisiveSemigroup 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 homogenous 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!)