Idiomatic Ruby for Array#extract / Range#length?

ruby-talk
1

During the monthly meeting of our code dojo, we were surprised by a couple
of things in Ruby, so I had a couple of questions I'd like to ask the
community:

1) Would it make sense to talk about a Range having a length, as in:

class Range
      def length
           self.end - self.begin
      end
end

2) What about a 2 dimensional slice (you want a submatrix, for example)?

def test_extract_submatrix
  assert_equal [[1,2,3],[4,5,6],[7,8,9]].extract_submatrix(1..2,1..2)
, [[5,6],[8,9]]
end

class Array
  def extract_submatrix(row_range, col_range)
    self[row_range].transpose[col_range].transpose
  end
end

3) Are the better/more idiomatic ways to do these?

4) Excuse my ignorance, as I've yet to use Facets, but are these the type of
things it adds (and more)? Are they already in there?

Thanks and kind regards,
Sam

2

A range only assumes #<=> and #succ.

Thus, the only sensible definable length given those basic pieces would be "number of elements", computed looping over the collection. A length computed as a difference max - min is not guaranteed to make sense in a range because the elements may not respond to #-.

On the other hand note that the definition of Range does not imply the collection is finite, given suitables #<=> and #succ a range can represent an enumeration of the rationals in [0, 1]. So strictly speaking "number of elements" defined with that procedure does not apply to all ranges either.

-- fxn

···

On Sep 20, 2007, at 2:28 PM, Sammy Larbi wrote:

1) Would it make sense to talk about a Range having a length, as in:

class Range
      def length
           self.end - self.begin
      end
end

3

During the monthly meeting of our code dojo, we were surprised by a couple
of things in Ruby, so I had a couple of questions I'd like to ask the
community:

1) Would it make sense to talk about a Range having a length, as in:

class Range
      def length
           self.end - self.begin
      end
end

There's been quite a lot of interesting discussion surrounding my first
question, which I truly appreciate and have enjoyed reading for the most
part.

2) What about a 2 dimensional slice (you want a submatrix, for example)?

def test_extract_submatrix
  assert_equal [[1,
2,3],[4,5,6
],[7,8,9]].extract_submatrix
(1..2,1..2)
, [[5,6],[8,9
]]
end

class Array
  def extract_submatrix(
row_range, col_range)
    self[row_range]
.transpose[col_range].transpose
  end

end

But what about this 2-dimensional slice? Any thoughts on that? There is
already Array#transpose that assumes a 2D array, so I think it might fit.
Can you think of a better way to do it?

3) Are the better/more idiomatic ways to do these?

···

On 9/20/07, Sammy Larbi <sam@powersource.com> wrote:

4) Excuse my ignorance, as I've yet to use Facets, but are these the type
of things it adds (and more)? Are they already in there?

Thanks and kind regards,
Sam

4

During the monthly meeting of our code dojo, we were surprised by a couple
of things in Ruby, so I had a couple of questions I'd like to ask the
community:

1) Would it make sense to talk about a Range having a length, as in:

class Range
      def length
           self.end - self.begin
      end
end

This code will work only when begin and end respond to #-. This is a valid
implementation for Numeric objects, but not for other classes.
In the general case, you'd have to generate every objects of the range to
count them (using #to_a and #size).
And as the previous posts were debating, some ranges are not able to generate
the objects in the Range : the ranges of objects that do not respond to
#succ. And some ranges can be infinite.
By the way, generating all objects and counting is not restricted to Range,
but is general for any other Enumerable.

2) What about a 2 dimensional slice (you want a submatrix, for example)?

def test_extract_submatrix
  assert_equal [[1,2,3],[4,5,6],[7,8,9]].extract_submatrix(1..2,1..2)
, [[5,6],[8,9]]
end

class Array
  def extract_submatrix(row_range, col_range)
    self[row_range].transpose[col_range].transpose
  end
end

Yes, this may be a useful method. It could be extended for use with
n-dimensional arrays.
Take a look to NArray library. I'm not sure, but I think it can do what you
are looking for, in an optimized way.

3) Are the better/more idiomatic ways to do these?

Your code is fine :slight_smile:

4) Excuse my ignorance, as I've yet to use Facets, but are these the type
of things it adds (and more)? Are they already in there?

Yes, the submatrix thing is the kind of method I could expect to see in
Facets. I'm not aware of the existence of such a method, though.

···

Le jeudi 20 septembre 2007 14:28, Sammy Larbi a écrit :

Thanks and kind regards,
Sam

--
Olivier Renaud

5
6

True in theory, but, I wonder just how you would code succ so as to
return the NEXT rational!?

···

On 9/20/07, Xavier Noria <fxn@hashref.com> wrote:

On the other hand note that the definition of Range does not imply
the collection is finite, given suitables #<=> and #succ a range can
represent an enumeration of the rationals in [0, 1].

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

7

I think that it's debatable even in the case of Numerics, for example:

(1.2..1.5).length #=> 0.3

Normally length returns the number of elements in a collection, and
the method as provided doesn't actually work correctly for integer
ranges, it should be:

class Range
  def length
      1 + last - first
  end
end

But, what about:

(1...3).length

end-start would give 2 but:

(1...3).to_a => [1, 2]

To fix this:

class Range
   def length
       last - first + (exclude_end? ? 0 : 1)
  end
end

Now we have another case:

(3..1).to_a #=> []

so:

class Range
   def length
      [0, last - first + (exclude_end? ? 0 : 1)].max
  end
end

But then what about:

(1.2..1.5).length

A collection can't have 0.3 elements!

I think it only makes sense for Integer ranges.

···

On 9/22/07, Olivier Renaud <o.renaud@laposte.net> wrote:

Le jeudi 20 septembre 2007 14:28, Sammy Larbi a écrit:
> During the monthly meeting of our code dojo, we were surprised by a couple
> of things in Ruby, so I had a couple of questions I'd like to ask the
> community:
>
> 1) Would it make sense to talk about a Range having a length, as in:
>
> class Range
> def length
> self.end - self.begin
> end
> end

This code will work only when begin and end respond to #-. This is a valid
implementation for Numeric objects, but not for other classes.
In the general case, you'd have to generate every objects of the range to
count them (using #to_a and #size).

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

8

Of course that won't happen in practice, but since we were speculating about a possible definition of length for ranges I thought that comment was needed for the reply to be complete.

The non-constructive argument goes like this (you say it is true so I guess you already know this):

Let f be a bijection between the rationals in the open interval (0, 1) and N. Such a bijection exists because Q is numerable. For any f(n) = q define q.succ to be f(n+1). For any given f(n) = q, f(m) = p in (0, 1) define q <=> p iff n <=> m.

I have seen explicit bijections between Q and N, I guess a programmable .succ could be given.

To complete the reasoning about the closed interval [0, 1], define 0 <=> q and q <=> 1 to be -1 for any q in (0, 1), and define 0.succ to be f(0). 1.succ can be any arbitrary value, when you compute the length iterating over a collection max.succ is not used anyway.

I've written that off the top of my head but I think it is correct.

-- fxn

···

On Sep 20, 2007, at 5:39 PM, Rick DeNatale wrote:

On 9/20/07, Xavier Noria <fxn@hashref.com> wrote:

On the other hand note that the definition of Range does not imply
the collection is finite, given suitables #<=> and #succ a range can
represent an enumeration of the rationals in [0, 1].

True in theory, but, I wonder just how you would code succ so as to
return the NEXT rational!?

9

You lost me, so what's the rational which is the successor to 1/3?

···

On 9/20/07, Xavier Noria <fxn@hashref.com> wrote:

On Sep 20, 2007, at 5:39 PM, Rick DeNatale wrote:

> On 9/20/07, Xavier Noria <fxn@hashref.com> wrote:
>
>> On the other hand note that the definition of Range does not imply
>> the collection is finite, given suitables #<=> and #succ a range can
>> represent an enumeration of the rationals in [0, 1].
>
> True in theory, but, I wonder just how you would code succ so as to
> return the NEXT rational!?

Of course that won't happen in practice, but since we were
speculating about a possible definition of length for ranges I
thought that comment was needed for the reply to be complete.

The non-constructive argument goes like this (you say it is true so I
guess you already know this):

Let f be a bijection between the rationals in the open interval (0,
1) and N. Such a bijection exists because Q is numerable. For any f
(n) = q define q.succ to be f(n+1). For any given f(n) = q, f(m) = p
in (0, 1) define q <=> p iff n <=> m.

I have seen explicit bijections between Q and N, I guess a
programmable .succ could be given.

To complete the reasoning about the closed interval [0, 1], define 0
<=> q and q <=> 1 to be -1 for any q in (0, 1), and define 0.succ to
be f(0). 1.succ can be any arbitrary value, when you compute the
length iterating over a collection max.succ is not used anyway.

I've written that off the top of my head but I think it is correct.

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

10

My last reply was a bit tongue in cheek.

Since rationals are densely ordered, it really doesn't make sense to
define a succ function since if a < b are both rationals there are an
infinite number of rationals c such that a < c < b,

Getting back to the original thread though, it's actually not quite
true that ranges require the starting and ending elements to implement
succ, as long as you don't use methods which need them like each,
to_a etc. If you don't need the enumerable aspects of a range then
you don't need to restrict the elements in that way.

(1.0..2.0).include?(1.5) # => true
1.0.methods.include?(:succ) # => false
(1.0..2.0).to_a # =>
# ~> -:3:in `each': can't iterate from Float (TypeError)
# ~> from -:3:in `to_a'
# ~> from -:3

class Foo
  attr_accessor :value

  def initialize(value)
    @value = value
  end

  def <=>(another)
    @value <=> another.value
  end

  def inspect
    "Foo(#{value})"
  end
end

foo_range = Foo.new(1)..Foo.new(10) # => Foo(1)..Foo(10)
foo_range.include?(Foo.new(5)) # => true
foo_range.to_a # =>
# ~> -:23:in `each': can't iterate from Foo (TypeError)
# ~> from -:23:in `to_a'
# ~> from -:23

So while it might make sense for SOME ranges to have a length, this is
not true in general.

And from a duck typing point of view note that ranges can be different
types of ducks depending on what they are being used for, and not all
ranges can be some of those types of ducks.

···

On 9/20/07, Rick DeNatale <rick.denatale@gmail.com> wrote:

On 9/20/07, Xavier Noria <fxn@hashref.com> wrote:
> On Sep 20, 2007, at 5:39 PM, Rick DeNatale wrote:
>
> > On 9/20/07, Xavier Noria <fxn@hashref.com> wrote:
> >
> >> On the other hand note that the definition of Range does not imply
> >> the collection is finite, given suitables #<=> and #succ a range can
> >> represent an enumeration of the rationals in [0, 1].
> >
> > True in theory, but, I wonder just how you would code succ so as to
> > return the NEXT rational!?
>
> Of course that won't happen in practice, but since we were
> speculating about a possible definition of length for ranges I
> thought that comment was needed for the reply to be complete.
>
> The non-constructive argument goes like this (you say it is true so I
> guess you already know this):
>
> Let f be a bijection between the rationals in the open interval (0,
> 1) and N. Such a bijection exists because Q is numerable. For any f
> (n) = q define q.succ to be f(n+1). For any given f(n) = q, f(m) = p
> in (0, 1) define q <=> p iff n <=> m.
>
> I have seen explicit bijections between Q and N, I guess a
> programmable .succ could be given.
>
> To complete the reasoning about the closed interval [0, 1], define 0
> <=> q and q <=> 1 to be -1 for any q in (0, 1), and define 0.succ to
> be f(0). 1.succ can be any arbitrary value, when you compute the
> length iterating over a collection max.succ is not used anyway.
>
> I've written that off the top of my head but I think it is correct.

You lost me, so what's the rational which is the successor to 1/3?

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

11

OK, the point is that we are not using the everyday order of Q. Our target are Ruby ranges, and I took custom orders and succ on a subset of Q to show a (theoretic) property of Ruby ranges that follows from the fact that they only assume #<=> and #succ.

In Ruby we are defining a class[*]

   class MyReorderedRationalsBetween0and1
     attr_reader :q

     def initialize(q)
       @q = q
     end

     def <=>(p)
       ...
     end

     def succ
       ...
     end
   end

such that we have a range r

   my0 = MyReorderedRationalsBetween0and1.new(0)
   my1 = MyReorderedRationalsBetween0and1.new(1)
   r = my0..my1

which is well-defined and infinite. That is what I meant when I said that an enumeration of the rationals in [0, 1] with suitables #<=> and #succ would give an example of infinite range.

I demonstrated that is possible in theory, taking a function f that set theory guarantees it exists.

Now, I didn't give a computable f you can encode in Ruby, but I am sure there's one. Of course it wouldn't really work in practice because you can't represent all rationals in a real computer. So in the first place there's no way you can go over the rationals in a real computer, no matter whether you have an f or not.

I think I could come with a simpler example that had the naturals plus infinity plus perhaps something else technically needed, and use standard orderings and succs for the finite part.

-- fxn

[*] There's a detail about 1.succ that I won't address to keep it simple.

···

On Sep 20, 2007, at 6:56 PM, Rick DeNatale wrote:

You lost me, so what's the rational which is the successor to 1/3?

12

No, no, they are dense *with the ordinary ordering*. It is not a property of the rationals as a set, it is a property of the rationals with their ordinary order.

I defined a succ in Q x (0, 1) just fine. It makes perfect sense to define a succ for rationals, as I indeed showed.

-- fxn

···

On Sep 20, 2007, at 7:26 PM, Rick DeNatale wrote:

Since rationals are densely ordered, it really doesn't make sense to
define a succ function since if a < b are both rationals there are an
infinite number of rationals c such that a < c < b,

13

Hi --

···

On Fri, 21 Sep 2007, Xavier Noria wrote:

On Sep 20, 2007, at 6:56 PM, Rick DeNatale wrote:

You lost me, so what's the rational which is the successor to 1/3?

OK, the point is that we are not using the everyday order of Q. Our target are Ruby ranges, and I took custom orders and succ on a subset of Q to show a (theoretic) property of Ruby ranges that follows from the fact that they only assume #<=> and #succ.

See Rick's point about #succ, though. Ranges don't assume #succ,
though they will make use of it if it's there.

David

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

14

Ah, I thought they did because of this excerpt from the Pickaxe:

"So far we’ve shown ranges of numbers and strings. However, as you’d expect from
an object-oriented language, Ruby can create ranges based on objects that you define.
The only constraints are that the objects must respond to succ by returning the next
object in sequence and the objects must be comparable using <=>."

Also, the documentation of Range says:

"Ranges can be constructed using objects of any type, as long as the
objects can be compared using their +<=>+ operator and they support
the +succ+ method to return the next object in sequence."

So, in what sense succ is not required?

-- fxn

···

On Sep 20, 2007, at 7:26 PM, Rick DeNatale wrote:

Getting back to the original thread though, it's actually not quite
true that ranges require the starting and ending elements to implement
succ,

15

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 can check whether a given object is inside that range
though. See:

class Bla
  attr_accessor :blabb
  @@blubb=0

  def initialize()
    @blabb=@@blubb
    @@blubb+=1
  end

  def <=>(other)
    blabb<=>other.blabb
  end
end

arr=Array.new(10) {Bla.new}

(arr[2]..arr[5]).include? arr[4] #=> true
(arr[2]..arr[5]).include? arr[1] #=> false
(arr[2]..arr[5]).include? arr[7] #=> false

(arr[2]..arr[5]).each do end # TypeError: can't iterate from Bla

···

--
NP: Shape of Despair - Still-motion
Jabber: sepp2k@jabber.org
ICQ: 205544826

16
17

http://talklikeaduck.denhaven2.com/articles/2007/09/20/duck-a-la-range

···

On 9/20/07, Xavier Noria <fxn@hashref.com> wrote:

On Sep 20, 2007, at 7:26 PM, Rick DeNatale wrote:

> Getting back to the original thread though, it's actually not quite
> true that ranges require the starting and ending elements to implement
> succ,

Ah, I thought they did because of this excerpt from the Pickaxe:

"So far we've shown ranges of numbers and strings. However, as you'd
expect from
an object-oriented language, Ruby can create ranges based on objects
that you define.
The only constraints are that the objects must respond to succ by
returning the next
object in sequence and the objects must be comparable using <=>."

Also, the documentation of Range says:

"Ranges can be constructed using objects of any type, as long as the
objects can be compared using their +<=>+ operator and they support
the +succ+ method to return the next object in sequence."

So, in what sense succ is not required?

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

18

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.

-- fxn

···

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

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.

19

Well, the fact that the documentation says "must respond to" and "as long as" disallows in my view to pass objects that do not respond to #<=> and #succ. I think that is clear and unrelated to duck typing. Of course that may indicate that the documentation needs a different wording, but the current docs are clear and according to them if you pass an object that does not respond to #succ to the Range constructor the object is invalid, the code is invalid, albeit it may run.

About rationals: I claim that the definition of a closed Range in Ruby (theoretically) allows for infinite ranges. That's my point. I prove that in ruby-talk giving an example.

Now, the example uses the rationals because what I want to show follows easily from the fact that Q is bijectable with N, which is a basic result in set theory. (See proof in the mailing list.)

Density is always relative to an ordering, and for brevity what I do is to change the order using a standard technique which consists of defining stuff into one set by transferring it from another through a bijection. The fact that the ordenary order of Q makes Q dense is not relevant to this discussion at all. You see a class with #<=> and #succ that provides an infinite Range.

But that's just a way to support my claim, I could construct another thing and show it gives infinite Ranges (again, theoretically). I am sure I could simplify the proof for non-mathematicians taking N and Inifinity or something close to that.

-- fxn

···

On Sep 20, 2007, at 9:41 PM, Rick DeNatale wrote:

http://talklikeaduck.denhaven2.com/articles/2007/09/20/duck-a-la-range

20

> http://talklikeaduck.denhaven2.com/articles/2007/09/20/duck-a-la-range

Well, the fact that the documentation says "must respond to" and "as
long as" disallows in my view to pass objects that do not respond to
#<=> and #succ. I think that is clear and unrelated to duck typing.
Of course that may indicate that the documentation needs a different
wording, but the current docs are clear and according to them if you
pass an object that does not respond to #succ to the Range
constructor the object is invalid, the code is invalid, albeit it may
run.

And as we know all documentation is perfect.

There are at least two uses of Ranges in ruby.

1) To represent a range for the purposes of determining if something
falls within that range.
     (98.0..99.1).include?(temperature) is a valid example of such a use.

2) As an collection of elements. This case does require succ and <=>
to be able to enumerate
the elements.

Logical ranges, which have a logical expression as the start and
finish aren't really range objects but they use the notation.

The first usage does not require the start and end elements to support
succ, this is a fault of the documentation.

Note that the documentation OMITS explicitly mentioning that start
must be less than end, for the range to be non-empty. it only gives
examples to imply that.

About rationals: I claim that the definition of a closed Range in
Ruby (theoretically) allows for infinite ranges. That's my point. I
prove that in ruby-talk giving an example.

An example which conveniently implements the succ and <=> methods as ...

Hand waving is not an example which gives a proof.

Now, the example uses the rationals because what I want to show
follows easily from the fact that Q is bijectable with N, which is a
basic result in set theory. (See proof in the mailing list.)

Density is always relative to an ordering, and for brevity what I do
is to change the order using a standard technique which consists of
defining stuff into one set by transferring it from another through a
bijection. The fact that the ordenary order of Q makes Q dense is not
relevant to this discussion at all. You see a class with #<=> and
#succ that provides an infinite Range.

And ordering is what ranges are all about. Since your handwaving
example is a bit hard to follow, I'm not sure how you handle having a
range between two arbitrary rationals and ensure that the start is
less than the end in general.

But if you really want a Range of rationals arranged so as to fit an
ordering picked so as to be able to generate a sequence but not in
natural sequence, I guess you can. Of course if you want the natural
sequence, I guess you are face with having to enumerate the entire
sequence so as to be able to sort it.

But that's just a way to support my claim, I could construct another
thing and show it gives infinite Ranges (again, theoretically). I am
sure I could simplify the proof for non-mathematicians taking N and
Inifinity or something close to that.

Being pragmatic, I'm much more interested in being able to use

   (1.2..3.6).include?(a)

than usages which only seem useful in theory.

···

On 9/20/07, Xavier Noria <fxn@hashref.com> wrote:

On Sep 20, 2007, at 9:41 PM, Rick DeNatale wrote:

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/