应该让 clojure.lang.Range/LongRange 实现clojure.lang.Reversible吗？

Question

有时我想像 (range 100) 这样的范围逆序迭代。为此，有两种现有的选择

1) 编程者思考构建反向范围的正确开始/结束/步长，并据此构建范围，使用负步长

(range 99 -1 -1)

2) 使用 reverse 如 (reverse (range 100))

解决方案1并不理想，因为你必须改变开始/结束，因为已经反转了边界，包括/不包括边界。这将需要比我喜欢做的更多的心算，如果步长不是1。例如，快速解决如何反转 (range 23 96 7)! 答案是 (range 93 22 -7)，但是确实不愿意在脑海中做这些数学运算并将其提交到代码中，实际上你想要的是 (reverse (range 23 96 7))。例如，如果你明天还想将下界从23（包含）改为24（包含），你必须实际重新计算上界并更改代码为 (range 94 23 -7)。

如果是非整数范围，这对程序员来说将更加困难/不可能

(range 1.5 5.4 1.23)

解决方案2并不理想，因为它需要O(n)的空间和时间

(defn reverse
  "Returns a seq of the items in coll in reverse order. Not lazy."
  {:added "1.0"
   :static true}
  [coll]
    (reduce1 conj () coll))

那么怎么办呢？

可逆性

也许 clojure.lang.Range/clojure.lang.LongRange 对象可以实现 clojure.lang.Reversible，因为它们可以在O(1)的时间和空间内反转，像这样：

public ISeq rseq() {
    final Number difference = Numbers.minus(end, start);
    final Number remainder = Numbers.remainder(difference, step);
    final Number last = Numbers.isZero(remainder) ?
            Numbers.minus(end, step) : Numbers.minus(end, remainder);
    final Number reverseStep = Numbers.minus(step);
    BoundsCheck bc;
    Object newEnd;
    if (Numbers.isPos(reverseStep)) {
        newEnd = Numbers.inc(start);
        bc = positiveStep(newEnd);
    } else {
        newEnd = Numbers.dec(start);
        bc = negativeStep(newEnd);
    }
    return new Range(last, newEnd, reverseStep, bc);
}

然后可以使用clojure中的 rseq 函数执行反转

(rseq (range 10))
=> (9 8 7 6 5 4 3 2 1 0)

这种方法的缺点和/或挑战

• “空域”仍然不起作用，因为当你执行 (range 0 0) 时，你实际上会得到一个空列表（实际上不是范围对象）。因此，由于列表不是可逆的，当你尝试 rseq 它时会引发异常。这可以通过允许存在空的范围对象来解决，或者可能通过使空列表可逆来解决？无论如何，这可能是一个过于激进的变更。我实际上不认为允许空范围会有问题，对于我来说，空的范围是否必须是具体的列表并不清楚，例如，空向量不是列表，空集合/映射也不是空列表，所以看起来空范围也不会奇怪。

• 对于浮点范围，计算反向范围的算法需要更多思考，因为上述算法在反转时不会产生相同的结果。例如

(range 1.5 5.4 1.23)
=> (1.5 2.73 3.96 5.1899999999999995)
(rseq (range 1.5 5.4 1.23))
=> (5.1899999999999995 3.9599999999999995 2.7299999999999995 1.4999999999999996)

如果不是那样的话，那么也许可以使用 :reverse true 关键字参数

可能可逆性更应该在 range 函数中

(range 10 :reverse true)

等等。

无论如何，我并不是说 Clojure 是错的，只是提供了一些思考的食物。谢谢阅读！

Answer 1

编辑：抱歉我以为这会显示为一个评论而不是“答案”，现在我似乎无法删除它，对此很抱歉。

我认为另一个想法是，应该让 Range 实现接口 RandomAccess 吗？它不能实现 Indexed，因为 Indexed extends Counted 需要实现 int count();，而对于无限范围来说这不能实现。但是标记接口 RandomAccess 只承诺 get(int i) 是快速的。这可以通过在 Range 中轻松实现。

public Object get(int i) {
    if (i < 0) {
        throw new IndexOutOfBoundsException();
    }
    final Object ret = Numbers.add(start,Numbers.multiply(step,i));
    if (boundsCheck.exceededBounds(ret)) {
        throw new IndexOutOfBoundsException();
    }
    return ret;
}

然后用这个结果用于 Clojure 的 nth 函数，而不是迭代整个范围来找到第 n 个元素。

在这种情况下，同样可以针对 Repeat 说

public Object get(int i) {
    if (i < 0 || (count != INFINITE && i >= count)) {
        throw new IndexOutOfBoundsException();
    }
    return val;
}

Comments

虽然不一定反对这些做法，但我努力想弄清楚实现可逆和随机访问的功能能够解决什么问题。如果我们希望提高速度，Clojure 已经有适合快速 .get 和可逆性的结构，最显著的是向量。我不反对为此提出一个或两个请求，但我强调，最好从我们作为 Clojure 程序员从它们的缺失中所遇到的问题出发，而不仅仅是它们的缺失。