Infinite Closed Ranges in Ruby

There was a question today in ruby-talk about whether Range#length could be defined by subtracting its endpoints.

The short answer is that such a definition is not guaranteed to work because objects in ranges are not required to respond to #-. Objects in ranges must respond to #<=> and #succ, and so you could in principle define Range#length iterating over the elements from the left endpoint to the right endpoint via #succ.

For completeness, I then noted that indeed those methods do not guarantee finite ranges (theoretically, real computers have physical constraints) and some discussion followed because, after Rick DeNatale asked for it, I gave a demonstration that used Q in a strange way (strange for people not exposed to this kind of math anyway). What surprises is that I define #succ in Q ∩ [0, 1], and albeit the logical steps are there, people believe the rationals per se are dense and so no #succ is possibly definable. That's not the case.

Density is a property of a set together with some order. Sets are orderable in different manners, sets are just collections of elements with no other property. If you define what does to be less than means in a given set, you are defining an order in that set. The definition is arbitrary, it is enough that it satisfies some properties. In Set Theory an order is just a subset of S × S that satisfies a few constraints, so it is something very generic. It models stuff we are used to, like the order in integers, but it is abstract.

OK, I claimed you could define suitables #<=> and #succ to enumerate the rationals in [0, 1] in a way that the Range 0 .. 1 is a well-defined infinite range.

The non-constructive proof uses a quite standard technique: Let f be a bijection between the rationals in the open interval (0, 1) and N. Such an f exists because Q is countable. For f(n) = q we define q.succ to be f(n + 1). And given f(n) = q, and f(m) = p we define q <=> p iff n <=> m.

Now, define C to be the class N, with ordinary order, together with those rationals with that order, and extend <=> among elements of both sets in the natural way. Let 0.succ be f(0), and n.succ be n + 1 for n in N, n > 0. The objects of class C implement the required interface, and 0 .. 1 is an infinite Range. You've got a #succ in the rationals of [0, 1]. You see, the rationals are not dense themselves, they are only dense with the ordinary way we order them.

I have somewhere in my notes from the faculty an explicit bijection between the rationals and the naturals (that was 1992, I indeed proved the bijection as an extra exercise), so a (again, theoretically) computable f could be indeed programmed in Ruby.

I think a much simpler example could be constructed taking N and a few infinities.

Update: The interface #<=> and #succ is required in the docs and in the Pickaxe, worded as as long as and must respond to respectively. David Black said there's enough evidence to say the docs are wrong. The idea is that you'd document instead that succ is required only if you are going to iterate over the range.