序数

我们将通过实现自定义类型序数来了解如何实现自定义比较。为简化实现,我们将重点关注这些数字的一小部分:所有序数最多但不包括ε0。我们的实施重点是简单,而不是速度; 但是,实施也不慢。

我们按照康托尔的正常形式存储序数。因为序数算术不是可交换的,所以我们将采用存储最重要术语的通用约定。

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

由于 Cantor 正规形式是唯一的,我们可以简单地通过递归相等来测试相等性:

Version >= 0.5.0

在 v0.5 版本中,有一个非常好的语法可以紧凑地执行此操作:

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

Version < 0.5.0

否则,将函数定义为更典型的:

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

要完成我们的订单,因为这种类型有一个总订单,我们应该重载 isless 函数:

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

为了测试我们的订单,我们可以创建一些方法来生成序数。当然,零是通过 Cantor 正常形式的条款获得的:

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

我们可以定义一个 expω来计算ω^α,并用它来计算 1 和ω:

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

我们现在有一个关于序数的全功能排序函数:

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])

在最后一个例子中,我们看到序数的打印可能会更好,但结果是预期的。