[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Re: Idiomatic Ruby for Array#extract / Range#length?

Xavier Noria

9/20/2007 2:19:00 PM

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

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
22 Answers

Rob Biedenharn

9/20/2007 2:47:00 PM

0



Rick DeNatale

9/20/2007 3:40:00 PM

0

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!?

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denh...

Xavier Noria

9/20/2007 3:59:00 PM

0

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.

-- fxn

Rick DeNatale

9/20/2007 4:57:00 PM

0

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

Rick DeNatale

9/20/2007 5:26:00 PM

0

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?

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

Xavier Noria

9/20/2007 5:28:00 PM

0

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.

Xavier Noria

9/20/2007 5:44:00 PM

0

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

David A. Black

9/20/2007 6:04:00 PM

0

Xavier Noria

9/20/2007 7:02:00 PM

0

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

Sebastian Hungerecker

9/20/2007 7:14:00 PM

0

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