1

我正在研究一个可以改进的事件处理框架，如果我有一种有效的方法来使用序数进行计算。

在 Java 语法中，我正在寻找：

class Ordinal {
    static int compare(Ordinal o1, Ordinal o2) { }
    static Ordinal suc(Ordinal o) { }
    static Ordinal add(Ordinal o1, Ordinal o2) { }
    static Ordinal mul(Ordinal o1, Ordinal o2) { }
    static Ordinal pow(Ordinal o1, Ordinal o2) { }
    static Ordinal omega() { }
    static Ordinal zero() { }
}

到目前为止，我想到的唯一方法是将可能的操作逐字表示为数据，这很像将整数表示为链表，因此感觉不太好。

有谁知道这样的事情？

更多信息：

序 数是一个数学概念，通常侧重于良序集的概念，但我希望将它们用作产生“不断变大”的数字的一种方式。

例如，1, 2, 3 ... 都小于 ω。那么 ω + 1, ω + 2, .... 都小于 2ω, 小于 3ω, ... 都小于 ω², 小于 ω³ ... 都小于 ω^ω, 等等上。这就是为什么有效地表示它们似乎很棘手......简单的位置值表示很快就会用完，然后一次又一次地用完。

我认为我想在我的代码中使用序数的原因是它们可以作为一种限制递归计算深度的方法，递归计算可以变得非常深、无限深和“超越”（如in，大于 ω)。考虑一个递归函数列表，其中第 i 个函数的深度为 i，然后是一个对列表进行折叠的函数......它的深度是 ω，但是我们可以再增加一个步骤，然后再增加一个步骤，得到 ω + k，因此另一个折叠得到 2ω，我们可以将此过程推广到所需的 ω²，依此类推。

现在，我想用序数计算的原因是，如果你用既尊重拓扑顺序又尊重深度的序数来标记 DAG 的节点，你可能想要做的一件事是执行一种访问节点的图搜索按其序号标签的递增顺序。我不能 100% 确定这就是我希望我的代码工作的方式，但这是我正在考虑的一种方法，所以我想看看走这条路是否合理。它看起来越来越像我应该重新考虑我的方法，在这种情况下，这个问题可能没有实际意义，但对于好奇心来说仍然很有趣。

4

2 回答 2

0

尽管这与语言无关，但我可以自由地展示如何在 Java 中执行此操作的建议，应该可以轻松地转移到任何具有对象标识概念的语言。

class Ordinal {
    private BigInteger value;   // invariant: value is positive
    // this is only used to construct omega once
    private Ordinal() { value = BigInteger.ONE.negate(); }            
    public final static Ordinal omega = new Ordinal();

    public Omega(BigInteger v) {
        if (v.compareTo(BigInteger.ZERO) < 0) throw new IllegalArgumentException();
        value = v;
    }
    public BigInteger value() {
        if (this == omega) // .... throw exception?
        else return value;
    }
    // example implementation of suc
    // note that it'll never equal omega
    // because omega is initialized with (-1)
    // In addition, there is one and only one, non copyable omega.
    public static Ordinal suc(Ordinal o) {
        if (o==omega) then return omega;
        else return new Ordinal(BigInteger.ONE.plus(o.value));
    }
}

这个想法是有一个不可复制的单例对象omega，它的值不等于也不能等于任何其他值。函数的实现需要识别omega，这就像引用相等检查一样简单。例如，在suc我们让suc omegabeomega否则加 1。

于 2013-08-12T15:15:02.117 回答
0

看起来Agda 已经在这个主题上做了一些工作。

我还没有深入了解它是实际可用还是主要是理论上的。

于 2016-06-14T21:18:33.137 回答