Re: Idiomatic Ruby for Array#extract / Range#length?
Xavier Noria
> 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
Rob Biedenharn
Rick DeNatale
> 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/
Xavier Noria
> On 9/20/07, Xavier Noria <f...@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.
-- fxn
Rick DeNatale
You lost me, so what's the rational which is the successor to 1/3?
Rick DeNatale
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.
Xavier Noria
> 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.
Xavier Noria
> 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
David A. Black
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)
Xavier Noria
> 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
Sebastian Hungerecker
> 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: sep...@jabber.org
ICQ: 205544826
Xavier Noria
> 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.
-- fxn
Rob Biedenharn
Rick DeNatale
http://talklikeaduck.denhaven2.com/articles/2007/09/20/duck-a-la-range
Xavier Noria
> 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
Rick DeNatale
>
> > 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.
Xavier Noria
* 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
Xavier Noria
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
Xavier Noria
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
David A. Black
On Fri, 21 Sep 2007, Xavier Noria wrote:
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.
Sebastian Hungerecker
> 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: sep...@jabber.org
ICQ: 205544826
Xavier Noria
> 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?
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
Xavier Noria
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]
Olivier Renaud
> 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 :)
> 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.
> Thanks and kind regards,
> Sam
--
Olivier Renaud
Rick DeNatale
> 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).
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.