Idiomatic Ruby for Array#extract / Range#length?

[Sammy_L]

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

[Sammy_L]

On Sep 20, 2007, at 2:28 PM, Sammy L. 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

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

[Sammy_L]

On 9/20/07, Xavier N. [email protected] 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!?

–
Rick DeNatale

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

[Sammy_L]

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

On 9/20/07, Xavier N. [email protected] 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.

– fxn

[Sammy_L]

On 9/20/07, Rick DeNatale [email protected] wrote:

return the NEXT rational!?
(n) = q define q.succ to be f(n+1). For any given f(n) = q, f(m) = p
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?

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.

–
Rick DeNatale

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

[Sammy_L]

On 9/20/07, Xavier N. [email protected] wrote:

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/

[Sammy_L]

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,

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

[Sammy_L]

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.

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.

[Sammy_L]

Hi –

On Fri, 21 Sep 2007, Xavier N. 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

[Sammy_L]

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?

– fxn

[Sammy_L]

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

Xavier N. 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.

– fxn

[Sammy_L]

On 9/20/07, Xavier N. [email protected] wrote:

an object-oriented language, Ruby can create ranges based on objects

So, in what sense succ is not required?

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

–
Rick DeNatale

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

[Sammy_L]

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

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.

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

[Sammy_L]

Xavier N. 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

[Sammy_L]

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

[Sammy_L]

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

[Sammy_L]

On 9/20/07, Xavier N. [email protected] wrote:

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.

#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.

–
Rick DeNatale

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

[Sammy_L]

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

[Sammy_L]

Hi –

On Fri, 21 Sep 2007, Xavier N. wrote:

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

[Sammy_L]

Xavier N. 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?