Julia Language Ordinal Numbers


Example

We will look at how to implement custom comparisons by implementing a custom type, ordinal numbers. To simplify the implementation, we will focus on a small subset of these numbers: all ordinal numbers up to but not including ε₀. Our implementation is focused on simplicity, not speed; however, the implementation is not slow either.

We store ordinal numbers by their Cantor normal form. Because ordinal arithmetic is not commutative, we will take the common convention of storing most significant terms first.

immutable OrdinalNumber <: Number
    βs::Vector{OrdinalNumber}
    cs::Vector{Int}
end

Since the Cantor normal form is unique, we may test equality simply through recursive equality:

0.5.0

In version v0.5, there is a very nice syntax for doing this compactly:

import Base: ==
α::OrdinalNumber == β::OrdinalNumber = α.βs == β.βs && α.cs == β.cs
0.5.0

Otherwise, define the function as is more typical:

import Base: ==
==(α::OrdinalNumber, β::OrdinalNumber) = α.βs == β.βs && α.cs == β.cs

To finish our order, because this type has a total order, we should overload the isless function:

import Base: isless
function isless(α::OrdinalNumber, β::OrdinalNumber)
    for i in 1:min(length(α.cs), length(β.cs))
        if α.βs[i] < β.βs[i]
            return true
        elseif α.βs[i] == β.βs[i] && α.cs[i] < β.cs[i]
            return true
        end
    end
    return length(α.cs) < length(β.cs)
end

To test our order, we can create some methods to make ordinal numbers. Zero, of course, is obtained by having no terms in the Cantor normal form:

const ORDINAL_ZERO = OrdinalNumber([], [])
Base.zero(::Type{OrdinalNumber}) = ORDINAL_ZERO

We can defined an expω to compute ω^α, and use that to compute 1 and ω:

expω(α) = OrdinalNumber([α], [1])
const ORDINAL_ONE = expω(ORDINAL_ZERO)
Base.one(::Type{OrdinalNumber}) = ORDINAL_ONE
const ω = expω(ORDINAL_ONE)

We now have a fully functional ordering function on ordinal numbers:

julia> ORDINAL_ZERO < ORDINAL_ONE < ω < expω(ω)
true

julia> ORDINAL_ONE > ORDINAL_ZERO
true

julia> sort([ORDINAL_ONE, ω, expω(ω), ORDINAL_ZERO])

4-element Array{OrdinalNumber,1}:
                                                                                                       OrdinalNumber(OrdinalNumber[],Int64[])
                                                                     OrdinalNumber(OrdinalNumber[OrdinalNumber(OrdinalNumber[],Int64[])],[1])
                                   OrdinalNumber(OrdinalNumber[OrdinalNumber(OrdinalNumber[OrdinalNumber(OrdinalNumber[],Int64[])],[1])],[1])
 OrdinalNumber(OrdinalNumber[OrdinalNumber(OrdinalNumber[OrdinalNumber(OrdinalNumber[OrdinalNumber(OrdinalNumber[],Int64[])],[1])],[1])],[1])

In the last example, we see that the printing of ordinal numbers could be better, but the result is as expected.