Julia Language Comparisons 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.
