Should clojure.lang.Range/LongRange be made to implement clojure.lang.Reversible?

Question

Sometimes I want to iterate through a range like (range 100), but in reverse order. For this, there are two existing choices:

1) The programmer thinks about the would be the right start/end/step to construct the reversed range, and constructs the range accordingly, with a negative step:

(range 99 -1 -1)

2) Use reverse as in (reverse (range 100))

Solution 1 is not great since well it is harder to think about because you have to change the start/end because of the reversed bounds inclusive/exclusive bounds on the start and end. It would also require more mental math than I like to do, in the case where step is not 1. For instance, quickly solve how to reverse (range 23 96 7)! The answer is (range 93 22 -7), but it's not ideal to have to do this math in your head and to commit it to code when really what you meant was (reverse (range 23 96 7)). For instance, if you tomorrow want to change the lower bound from 23 inclusive to 24 inclusive, you have to actually recompute the upper bound and change the code to (range 94 23 -7).

This would get even more difficult/impossible for the programmer if they're using non-integer ranges:

(range 1.5 5.4 1.23)

Solution 2 is not great since it takes O(n) space and time:

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

So then what?

Reversible

Maybe the clojure.lang.Range/clojure.lang.LongRange objects could implement clojure.lang.Reversible, since they can be reversed in O(1) time and space, with something like:

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);
}

And then the reversing could be done in clojure using the rseq function

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

Problems with this approach and/or challenges:

• Still doesn't work on "empty ranges" because when you do (range 0 0) you actually get an empty list (not a Range object actually). So since lists aren't Reversible, you'd get an exception when you try to rseq it. This could be fixed by allowing there to be an empty Range object, or perhaps by making empty lists Reversible? Anyways probably too aggressive of a change. I actually don't think there should be a problem with allowing an empty Range, it's not clear to me if it's important that empty ranges are specifically lists, but for instance it isn't the case that the empty Vector is a list, or that the empty Set/Map are the empty list, so it doesn't seem to be bizarre that there would be an empty Range.

• some more thought would have to go into the algorithm to compute the reverse range in the case of floating point ranges, since the above algorithm doesn't produce the exact same result in reverse. For instance:

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

If not that, then maybe :reverse true keyword arg

Maybe the reversibility belongs more in the range function:

(range 10 :reverse true)

or similar.

Anyways I am not saying Clojure's wrong or anything, just submitting some food for thought. Thanks for reading!

Answer 1

Edit: Sorry I thought this would show up as a comment in the thread not as an "Answer", and now I don't seem to be able to delete it sorry about that.

I think an other idea is, should Range be made to implement RandomAccess? It cannot be made to implement Indexed, because Indexed extends Counted which requires an implementation of int count(); which cannot be implemented for infinite Range's. But the marker interface RandomAccess just promises that get(int i) is fast. This could be implemented in Range easily enough:

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;
}

This would then be used by Clojure's nth function rather than iterating through the range to find the nth element.

For that matter, the same could be said for Repeat:

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

Comments

While not necessarily opposed to such things, I'm struggling to understand what problems implementing either or both of Reversible and RandomAccess serves. If we're hoping to gain speed then Clojure already has structures that are better suited for fast .get and reversibility, most notably vectors. I wouldn't mind a ticket for one or both of these for considerations but I stress that it would be most helpful to frame them in terms of the problems that we as Clojure programmers experience from their absence, independent of their mere absence.