Idiomatic Ruby for Array#extract / Range#length?

ruby-talk
21

Hi --

Xavier Noria wrote:

So, in what sense succ is not required?

You can have a range of objects that don't have succ. You just can't iterate
over that range.

You are saying that Ruby is implemented in a way that allows you to define an object, use it to build a Range, and use the range in a way that does not break the program. Agreed.

But the documentation says "must respond to" and "as long as". That's why I said Range assumes #<=> and #succ, because the documentation says so.

If you use pass objects to .. that do not respond to #succ, you are indeed feeding _invalid_ objects to .. according to the documentation. The program may run, but that doesn't matter.

The docs appear to be wrong. There's plenty of external evidence
(e.g., discussions by Matz about float ranges, where he doesn't label
them as invalid or advise against using them), as well as internal
evidence (they work :-), suggesting that range objects do not have to
respond to #succ. I think it's just out-of-date or erroneous
documentation.

David

···

On Fri, 21 Sep 2007, Xavier Noria wrote:

On Sep 20, 2007, at 9:14 PM, Sebastian Hungerecker wrote:

--
* Books:
   RAILS ROUTING (new! http://www.awprofessional.com/title/0321509242\)
   RUBY FOR RAILS (http://www.manning.com/black\)
* Ruby/Rails training
     & consulting: Ruby Power and Light, LLC (http://www.rubypal.com)

22

Sorry Rick I think we are not communicating.

* I say that "must respond to" implies that _according to the docs_ objects in a Range _must_ respond to #succ. I think there's no room for opinion there. Note the premise _according to the docs_.

* I say that from a formal point of view, the interface of Ranges does not imply Ranges are finite, and thus a Range#length implemented as a loop from left endpoint to right endpoint thorugh #succ may not terminate. That's theoretical (real computers have physical constraints) and pretended just to give a complete answer to the original question.

* Since you asked for it, I gave a non-constructive proof that showed such a Range is (theoretically) definable. I'd need to dig into my faculty notes to find an explicit bijection between Q and N that passed through Z x Z doing arithmetic such as primer decomposition and some sort of encoding I don't remember now. If you really want me to show such a function I can search for it, but I promise it is boring and the demonstration more difficult than the bijection I used in the thread.

* You try to disprove my thesis not by pointing to an error in the demonstration, but by saying Q is dense, which is not true and signals you clearly don't know the stuff we are talking about. And you still demand a conrete implementation doubting about my proof which you can't follow. Sorry Nick, I'd would have been pleased to explain the demonstration with more detail in a private email, but I find disappointing that you simply doubt about something you don't understand (which is fine, set theory does not come with brains) and put yourself in a blind "show me the code" way.

Now, the Ruby way of using things is fine with me. I mean, I've founded a company which is enterely Ruby-based, so I can guarantee you duck typing and the Ruby way of doing things is perfectly OK for me. My contribution to this thread (which I expected to be just a single post) is strictly formal. I've not questioned the use of ranges with invalid objects, I've not claimed they do not work, I just assert those usages are formally invalid according to the docs, which is just a fact!

-- fxn

23

Right, I've got an infinite closed Range with standard Ruby:

   class ZSquared
     include Comparable

     attr_reader :n, :m

     def initialize(n, m)
       @n, @m = n, m
     end

     def succ
       self.class.new(n+1, m)
     end

     def <=>(zs)
       self.m <=> zs.m
     end
   end

   a = ZSquared.new(0, 0)
   b = ZSquared.new(0, 1)

   puts a < b # true

   length = 0
   (a .. b).each do |c|
     length += 1
     puts length
   end

   # be prepared to send Ctrl-C

I am very sorry for the direction this thread took, I am used to formal stuff and used to discuss within its limits with no further interpretations. I knew this was possible but the first example that came to my head was math-based and it was not my intention to get into proofs and stuff which may not be clear to all people in the list.

I guess the claim that well-defined infinite Ranges in Ruby are implementable is now clear.

-- fxn

24

And yet another example that satisfies in addition

   zs < zs.succ for all zs in ZSquared

which would be an expected relationship between succ and <=>:

   class ZSquared
     include Comparable

     attr_reader :n, :m

     def initialize(n, m)
       @n, @m = n, m
     end

     def succ
       self.class.new(n+1, m)
     end

     def <=>(zs)
       [self.m, self.n] <=> [zs.m, zs.n]
     end
   end

   a = ZSquared.new(0, 0)
   b = ZSquared.new(0, 1)

   puts a < b # true

   length = 0
   (a .. b).each do |c|
     length += 1
     puts length
   end

   # be prepared to send Ctrl-C

I guess that's enough for today at 1:57 AM.

-- fxn

25

Xavier Noria wrote:

I guess the claim that well-defined infinite Ranges in Ruby are
implementable is now clear.

Sorry if this is a stupid question, but couldn't you just have proved that
claim by giving 1..(1.0/0) as an example? That's an infinite range right
there and you don't have to define any custom classes. Or would you
say that doesn't qualify as well-defined?

···

--
Jabber: sepp2k@jabber.org
ICQ: 205544826

26

Exactly, thank you, let me write 1.0/0 as w to simplify the notation in what follows.

That is the basic idea I had in mind when I mentioned an alternative proof involving N and a few infinities. Note that technically you still need to define a class, because you need 1, and w to belong to the same class, and have #<=> and #succ defined for both ("have" in the context of this thread).

It is true that w.succ is not _needed_ to implement Range#length, but the rules I am playing with require your objects to respond to a couple of methods, that includes the endpoints. Thus, you need to define w.succ and w.succ.succ in turn, and so on. The result is another handful of "naturals" past w. We can write them like this (note this is just intuitive notation, we have not defined addition for w):

   w, w + 1, w + 2, w + 3, ....

You'd expect as well that "<" (which means <=> gives -1) satisfies

   w < w.succ (:= w + 1) < w.succ.succ (:= w + 2) < ....

Right, keep the ordinary ordering for the naturals. Let's define all naturals to be strictly less than w + n for all n, and define w + n <=> w + m iff n <=> m. That <=> works.

So yes, that was the idea but needs a bit of extra work to follow the docs.

I came with the ZSquared example (I prefer the second version) to avoid more math-like stuff and still have both methods implemented in the class, and with easy one-liners. You can visualize ZSquared in Z x Z if you want, but people can understand ZSquared gives an infinite Range just reasoning about arrays of integers otherwise.

Thus, even if Range required in practice that objects implemented #succ, Range#length is not guaranteed to terminate in general written as a loop over #succ.

Thank you Sebastian,

-- fxn

···

On Sep 21, 2007, at 8:14 AM, Sebastian Hungerecker wrote:

Xavier Noria wrote:

I guess the claim that well-defined infinite Ranges in Ruby are
implementable is now clear.

Sorry if this is a stupid question, but couldn't you just have proved that
claim by giving 1..(1.0/0) as an example? That's an infinite range right
there and you don't have to define any custom classes. Or would you
say that doesn't qualify as well-defined?

27

I think this thread deserves a summary.

Sammry Larbi asks three questions in the post that opens this thread, the first one asks whether it would make sense to define Range#length as the difference between its endpoints.

The short answer is that objects in ranges do not necessarily respond to #-.

Furthermore, according to the docs (Ruby docs and Pickaxe), objects in ranges respond to #succ, and so one may wonder whether you can define Range#length as an element count implemented as a loop from left endpoint to right endpoint via #succ. There's a warning, though, because #<=> and #succ do not guarantee ranges are finite, so such a method is not guaranteed to terminate. That's a claim at that point, and some people ask for further details.

There's a split here in the thread (mixed in practice):

1) The docs say so, but there's enough evidence to say they are wrong, objects in ranges are only required to respond to #succ if you want to iterate over them. If you want to implement Range#length that way you have to assume objects respond to #succ anyway.

2) A few examples of classes that give infinite ranges are described or implemented, the most simple of them being the ZSquared class copied below.

The other two questions of the original post remain unanswered by now (at least in the mailing list).

Best,

-- fxn

   class ZSquared
     include Comparable

     attr_reader :n, :m

     def initialize(n, m)
       @n, @m = n, m
     end

     def succ
       self.class.new(n+1, m)
     end

     def <=>(zs)
       [self.m, self.n] <=> [zs.m, zs.n]
     end
   end

   a = ZSquared.new(0, 0)
   b = ZSquared.new(0, 1)

   puts a < b # true

   length = 0
   (a .. b).each do |c|
     length += 1
     puts length
   end

   # be prepared to send Ctrl-C