[RCR] New [] Semantics

[gabriele renzi]

Randy W. Sims ha scritto:

Or better. Some classes could implement an optional method (a mixin
interface?), say find_in_range, so that if the method exists for the
type of objects in the range it is called for an efficient lookup. If
the object does not support the method, it can be done the old way using
obj#succ.

isn't <=>+checking for same class enough for this?

 

[Randy W. Sims]

[Oops, first copy accidently got sent to Brian instead of list. Sorry.]

Range#include? just uses the <=> operator to test for the bottom and top of
the range (in other words, it's intended for objects which are Comparable
rather than Enumberable)




You can't do a binary search over an Enumberable, because it just gives you
the elements one at a time in order; it doesn't support "fetch Nth item".
You'd have to first enumerate everything into an Array, which brings you
back to the current situation anyway.

For some types it is possible to calculate whether a value exist within
a range without the need of iterating through the whole range with
#succ. Integer, Date, and possibly String could all offer the ability to
test if a member is in range by performing a quick calculation. Other
types would have to defer to the #succ method. Types that can provide
efficient membership test would all support an interface, a
#test_in_range(start, end, target) class method, that #member? could query.

Also, if you really want that sort of membership test with integers, then
there's no need for a binary search anyway:

myrange.include?(x) and x.to_i == x

ISTM that in Ruby, a range is *primarily* a continuous range with lower and
upper bounds. If the lower bound happens to be an object which responds to
'succ' to generate the next object in a sequence, and <=> to match the upper
bound, then magically it also becomes Enumerable.

I guess it's not really that big of a deal to me. It just seems a little
inconsistent. Sometimes a Range seems continuous (#include?) and other
times not ((1..5).each {|i| puts i}). I was just trying to think of a
way to make it more consistent without a major speed penalty.

Randy.

 

[Brian Candler]

Randy W. Sims ha scritto:


isn't <=>+checking for same class enough for this?

At the moment,

(3..5).member?(3.5) #=> false
(3..5).member?(4.0) #=> true

so following your rule exactly wouldn't duplicate the current behaviour.

You'd need some way of saying "is there some Integer x where x == 4.0"

Or I suppose more generally:

(a..b).member?(c)
is true if a <= b <[=] c
and there exists some d such that c == d and d.instance_of?(a.class)

Except - some ranges change class as they iterate, e.g. if 'a' is a Fixnum
and 'b' is a Bignum. Ugh!

Regards,

Brian.

 

[Brian Candler]

At the moment,

(3..5).member?(3.5) #=> false
(3..5).member?(4.0) #=> true

so following your rule exactly wouldn't duplicate the current behaviour.

Also, your rule requires that 'succ' generate all possible intervening
values between the two bounds, with no gaps. So to give a stupid
counterexample:

class Foo
attr_reader :x
def initialize(x); @x=x; end
def succ; self.class.new(@x+@x); end
def <=>(y); @x <=> y.x; end
def ==(y); @x == y.x; end
end
(Foo.new(1)..Foo.new(64)).member?(Foo.new(32)) #=> true
(Foo.new(1)..Foo.new(64)).member?(Foo.new(33)) #=> false

An optimised member? test would need to be coded specially for this class -
or fall back to iteration. Consider also:
(Foo.new("x")..Foo.new("xxxxxxxx")).each {|x| p x}

I agree with Matz - Range#member? is not very useful. For the occasional
case where you might need such semantics, it's easy enough to code up your
own object which behaves how you want.

You can argue that a Ruby Range shouldn't be able to iterate then, but I
just see it as a freebie bonus behaviour, which is actually useful in
practice.

Regards,

Brian.

 

[trans. (T. Onoma)]

On Saturday 09 October 2004 08:07 am, Brian Candler wrote:
| You can argue that a Ruby Range shouldn't be able to iterate then, but I
| just see it as a freebie bonus behaviour, which is actually useful in
| practice.

After expirementing with implementation of Interval which coerces to a purely
Iterative Range (see code below), I can safely say, that it is certainly
formally precise and seems to works quite well. On the other hand, I am not
sure the gain is great enough to justify it, but please, prove me wrong if
you see otherwise!

So Brian's assessment may indeed be the best take. Ruby's Range _is_ a
mathematical Interval. The Enumerable mixin is simply an added bonus for
utility. That said, the non-POLS of this stems from the fact the #member? and
#include? are defined in Enumerable, but Range goes and redefines them for
it's own purposes; also === and case statements become useless in the
Enumerable sense as well. So you end up with a hodgepodge.

The only way I see to clean it up is A) per a division like my coerce code
below, -OR- B) using a different method for checking inclusion (ex-
#contains?) so that #member? and #include? still belong to Enumerable, PLUS
expanding case to take an argument:

case 5.5
using :member?
when 0..10
puts "wrong"
else
puts "right"
end

That would do the trick. (Or is there already some way to do this?)

The only problem is that changing the meaning of Range#include? would likely
break some code.

OTOH, matz has a point when he ask how useful is Range#member? anyway. Hence
we should just well document the fact Range in NOT technically Enumerable it
can just be utilized as one in simple cases.

Food for thought,
T.


--------------- code -------------------

class Interval

def initialize(first, last, exclude_first=false, exclude_last=false)
@first = first
@last = last
@exclude_first = exclude_first
@exclude_last = exclude_last
end

def first ; @first ; end
def last ; @last ; end
def exclude_first? ; @exclude_first ; end
def exclude_last? ; @exclude_last ; end

def include?(x)
(@exclude_first ? (x <=> @first) == 1 : (x <=> @first) >= 0) &&
(@exclude_last ? (x <=> @last) == -1 : (x <=> @last) <= 0)
end

def length ; @last - @first ; end

alias_method( :begin, :first )
alias_method( :end, :last )
alias_method( :exclude_begin?, :exclude_first? )
alias_method( :exclude_end?, :exclude_last? )
alias_method( :member?, :include? )
alias_method( :===, :include? )
alias_method( :size, :length )

def to_rng
seed = ( @exclude_first ? @first.succ : @first )
term = ( @exclude_last ? proc{|x| (x <=> @last) == -1} : proc{|x| (x <=>
@last) <= 0} )
Range.new( seed, term )
end

# Any method of Enumerable coerce the Interval into to a Range
# Is there a better way to do this?
alias non_enumerable_method_missing method_missing
def method_missing(meth, *args, &yld)
if meth == :each or Enumerable.instance_methods.include?(meth.to_s)
to_rng.send(meth, *args, &yld)
else
non_enumerable_method_missing(meth, *args, &yld)
end
end

end


### Modified Range Class (purely discrete)

class Range

attr_reader :start, :step, :term, :skip

def initialize(start, step, skip=1)
@start = start
@skip = skip
if step.kind_of?(Proc)
@step = nil
@term = step
else
@step = step
@term = nil
end
end

def each
if @term
seed = @start
while @term.call(seed)
yield(seed)
@skip.times { seed = seed.succ }
end
else
seed = @start
@step.times {
@skip.times { seed = seed.succ }
yield(seed)
}
end
end

# cache (bad idea?)
def last
if ! @last
if @term
seed = @start
while @term.call(seed)
prior = seed
@skip.times { seed = seed.succ }
end
@last = prior
else
seed = @start
@step.times { @skip.times { seed = seed.succ } }
@last = seed
end
end
@last
end

alias_method( :end, :last )
alias_method( :first, :start )
alias_method( :length, :step )
alias_method( :size, :step )

undef_method :exclude_end?

end


# --- quick testing ---


# interval

i = Interval.new(0,10)

puts i.first
puts i.last

puts i.member?(0)
puts i.member?(5)
puts i.include?(10)

puts i.include?(11)
puts i.include?(-1)

puts i.length


# range

r = i.to_rng

puts r.last


# coerce

i.each {|e| puts e }

puts i.select { |e| e % 2 == 0 }


T.

 

[Tom Reilly]

The following is a slight modification of the ftp server example in
programming ruby.

require 'socket'
q = 0
server = TCPServer.new('localhost', 800)
while (session = server.accept)
q += 1
#________________________________________
puts "Request: #{session.gets}"
#________________________________________
session.print "ret info #{q}\n"
session.close
end

The following is a simple client I wrote.

require 'socket'
t = TCPSocket.new('localhost', 800)
#___________________________
t.print "TxxxxT"
#___________________________
rslt = t.gets
p rslt
t.close

I am using windows 2000.

If I run the programs with the instruction between the lines commented out,
they work fine.
If I run them the way they are written, then both lock up.
Could anyone tell me why? Or what the fix might be?

Thanks
Tom

 

[ts]

T> t.print "TxxxxT"

[...]

T> Could anyone tell me why? Or what the fix might be?

You don't have a \n at the end, and it's best to use IO#sync=


Guy Decoux

 

[trans. (T. Onoma)]

On Saturday 09 October 2004 04:28 am, Yukihiro Matsumoto wrote:
| Hi,
|
| In message "Re: Range behavior (Re: [RCR] New [] Semantics)"
|
| on Fri, 8 Oct 2004 22:43:52 +0900, "trans. (T. Onoma)"
| || planA - leave member? and include? as they are; they are very easy
| || to distinguish, and to remember. why bother?
| ||
| || planB - making member? as alias to include?; they behave same. no
| || confusion, no problem. who wants membership for ranges?
| |
| |Okay, planB is good. You are going the other way toward Range being
| |continuous.
|
| OK. I will consider taking planB in the future. Would somebody
| volunteer to update the RDoc in range.c if I change?

I will if no one else will --just some documentation changes, yes?

T.

 

[James Edward Gray II]

I agree with Matz - Range#member? is not very useful. For the
occasional
case where you might need such semantics, it's easy enough to code up
your
own object which behaves how you want.

Or just use:

(3..5).to_a.include?(4)

James Edward Gray II

 

[trans. (T. Onoma)]

07 AM, Brian Candler wrote:
| > I agree with Matz - Range#member? is not very useful. For the
| > occasional
| > case where you might need such semantics, it's easy enough to code up
| > your
| > own object which behaves how you want.
|
| Or just use:
|
| (3..5).to_a.include?(4)

Note that this won't work for

Inf = 1.0/0
(3..Inf).to_a.include?(5)

T.

 

[Brian Candler]

07 AM, Brian Candler wrote:
| > I agree with Matz - Range#member? is not very useful. For the
| > occasional
| > case where you might need such semantics, it's easy enough to code up
| > your
| > own object which behaves how you want.
|
| Or just use:
|
| (3..5).to_a.include?(4)

Note that this won't work for

Inf = 1.0/0
(3..Inf).to_a.include?(5)

But that's unlikely to be useful anyway, even with the current member?
syntax, since it either returns true or hangs in an infinite loop:

(3..Inf).member?(1)

[Actually Ruby hangs in an infinite loop even if the value is found, but
Matz has acknowledged that as a bug]

Regards,

Brian.

 

[trans. (T. Onoma)]

On Saturday 09 October 2004 02:34 pm, Brian Candler wrote:
| > Inf = 1.0/0
| > (3..Inf).to_a.include?(5)
|
| But that's unlikely to be useful anyway, even with the current member?
| syntax, since it either returns true or hangs in an infinite loop:
|
| (3..Inf).member?(1)
|
| [Actually Ruby hangs in an infinite loop even if the value is found, but
| Matz has acknowledged that as a bug]

Granted.

I have given the usage question some thought. I think the most common uses are
1) for Interval, then 2) as Array index, then 3) simple iterator on Integers.
Please let me know if you can think of any other common use cases. For 1 and
2 all that really matters is the two bound points.

Note: Consider a special EvenInt class with a succ of: {|x| x+2}, make a Range
of those and use it as an Array index argument,

arr = [1,2,3,4,5,6,7,8]
arr[EvenInt.new(2)..EvenInt.new(4)]

would you expect [2,3,6,8]? I haven't tried it but my bet is you'll get
[2,3,4,5,6,7,8] instead.

Now, consider, how often have you use any of these on a Range:

collect, detect, each_with_index, entries,
find, find_all, grep, map, member?,
reject, select, sort

So maybe Enumerable isn't really needed in Range, and would work just fine
with only a couple of useful methods toward that end, like a specially
defined #each --I'm not even sure #succ is really a good match for this
either.

For all those much less common Enumerable uses of a Range, one would be better
off using a dedicated class anyway --a real Iterator. So why not just provide
one of those in the standard libs, instead of trying to get Range to serve
triple duty.

Clearly this is the direction things are headed anyway.

T.

 

[Martin DeMello]

| Separating Range functionality into a mixin might also make it easier to
| get goodies like negative-stepping and infinite ranges.

Could you elaborate on this more?

Right now, Range = Interval + Compactly Represented 'Arithmetic Series'

Separating the two aspects would let us have intervals with +/-Inf as a
bound, without having to worry about explicitly enumerating over the
'elements' (a pure interval would have no elements).

For the arithmetic series aspect, I was thinking of replacing succ with
step (i.e., have the range require a step(n) operator, and have succ
call step(1) internally. This would let those classes that can implement
an efficient step operator do so, and the ones that don't could have
succ fundamental and step(n) call succ n times instead).

I thought I had negative ranges worked out but I was wrong I'll have
to think on it some more.

martin

 

[trans. (T. Onoma)]

Consider a special EvenInt class with a succ of: {|x| x+2}, make a
| Range of those and use it as an Array index argument,
|
|    arr = [1,2,3,4,5,6,7,8]
|    arr[EvenInt.new(2)..EvenInt.new(4)]
|
| would you expect [2,3,6,8]? I haven't tried it but my bet is you'll get
| [2,3,4,5,6,7,8] instead.

In fact, I just played with this idea a bit and found Range to be quite out of
wack:

class Fixnum
def succ
self + 2
end
end

r = 2..14
=> 2..14
r.to_a
=> [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
r.each {|e| print "#{e} "}; puts
2 3 4 5 6 7 8 9 10 11 12 13 14
=> nil
r.member?(4)
=> true
r.member?(3)
false

Unless I goofed somehow, this is even more evidence that Enumerable is of
little use in Range. From the looks of it I'm don't think #succ is even being
used for anything besides the #member? method!!! I assume this is because it
is trying to optimize for Fixnum.

T.

 

[Yukihiro Matsumoto]

Hi,

In message "Re: Range behavior (Re: [RCR] New [] Semantics)"

|| OK. I will consider taking planB in the future. Would somebody
|| volunteer to update the RDoc in range.c if I change?
|
|I will if no one else will --just some documentation changes, yes?

Yes.

matz.

 

[Brian Candler]

I have given the usage question some thought. I think the most common uses are
1) for Interval, then 2) as Array index, then 3) simple iterator on Integers.
Please let me know if you can think of any other common use cases. For 1 and
2 all that really matters is the two bound points.

Those are the common cases I can think of too.

Note: Consider a special EvenInt class with a succ of: {|x| x+2}, make a Range
of those and use it as an Array index argument,

arr = [1,2,3,4,5,6,7,8]
arr[EvenInt.new(2)..EvenInt.new(4)]

would you expect [2,3,6,8]? I haven't tried it but my bet is you'll get
[2,3,4,5,6,7,8] instead.

An array is indexed by an Integer, not an EvenInt. I would expect it to do
the same as

arr[EvenInt.new(2).to_i .. EvenInt.new(4).to_i]

and thus be the same as

arr[2 .. 4]

returning [3,4,5].

Right, here's a quick test to see:

class Foo
def initialize(x)
@x = x
end
def to_i
@x / 10
end
end

arr = [1,2,3,4,5,6,7,8]
arr[Foo.new(20)..Foo.new(40)]
#>> ArgumentError: bad value for range

Nope, so I'm wrong. Perhaps it does iterate over the range after all. OK,
let's add:

class Foo
def succ
self.class.new(@x+1)
end
attr_reader :x
def <=>(y)
@x <=> y.x
end
end

arr[Foo.new(20)..Foo.new(40)]
#>> TypeError: cannot convert Foo into Integer

Hmm, closer, but no banana. Next:

class Foo
alias :to_int :to_i
end

arr[Foo.new(20)..Foo.new(40)]
#=> [3, 4, 5]

Bingo, but that's strange:

(Foo.new(20)..Foo.new(40)).each {|x| p x}

generates 21 elements, but we only have 3 elements to our array. Perhaps
it's not iterating over the range after all?

Let's try a fresh object without 'succ':

class Bar
def initialize(x)
@x = x
end
def to_int
@x / 10
end
end
arr[Bar.new(20)..Bar.new(40)]

#>> ArgumentError: bad value for range

Put the spaceship back in:

class Bar
attr_reader :x
def <=>(y)
puts "Spaceship! #{x.inspect}<=>#{y.x.inspect}"
@x <=> y.x
end
end
arr[Bar.new(20)..Bar.new(40)]

# Spaceship! 20<=>40
#=> [3, 4, 5]

Ok, so now we have the answer.

arr[range]

is essentially the same as

arr[range.first.to_int .. range.last.to_int]

However the lower and upper bounds are compared once with the spaceship
operator first (*before* they are converted to integers). Oh yes, that's
because of the overloaded use of ranges:

arr[5..-2]

means "from arr[5] to character arr[size-2] (inclusive)"

arr[Bar.new(20)..Bar.new(-20)]

# Spaceship! 20<=>-20
# => [3, 4, 5, 6, 7]

Anyway, you can see here that a Range is definitely being treated as just a
pair of values (lower and upper), not as anything iterative at all.

Aside: Perhaps the conversion to integers should take place before the
comparison?

Now, consider, how often have you use any of these on a Range:

collect, detect, each_with_index, entries,
find, find_all, grep, map, member?,
reject, select, sort

The pattern

(0..9).collect { |c| ... }

isn't uncommon. Things like find/find_all/member? seem pretty useless to me.
sort is clearly no use at all

So maybe Enumerable isn't really needed in Range, and would work just fine
with only a couple of useful methods toward that end, like a specially
defined #each --I'm not even sure #succ is really a good match for this
either.

to_a is very important. each and map/collect would be the only other two I'd
see as important. Perhaps 'min' and 'max' could alias to 'first' and 'last',
since they're so trivially implemented (although that would give three
aliases: begin/first/min, end/last/max. I think Range#begin and Range#end
are dangerous method names, given that they are also Ruby keywords)

For all those much less common Enumerable uses of a Range, one would be better
off using a dedicated class anyway --a real Iterator. So why not just provide
one of those in the standard libs, instead of trying to get Range to serve
triple duty.

Or drop Enumerable from Range, and give it a handful of duck-type methods:
each
to_a
map / collect
(min)
(max)

plus its own non-enumerable 'include?' of course.

Mixing in the real Enumerable saves a little bit of coding, but like you
say, it adds a lot of methods which have little or no value and perhaps
that's what's confusing.

However I don't really object to a Range being Enumerable in the full sense,
even if some of the methods don't make sense; I think it's important to
distinguish Range#include? / member? from Enumberable#include? / member?

Regards,

Brian.

 

[trans. (T. Onoma)]

|    each
|    to_a
|    map / collect
|   (min)
|   (max)
|
| plus its own non-enumerable 'include?' of course.
|
| Mixing in the real Enumerable saves a little bit of coding, but like you
| say, it adds a lot of methods which have little or no value and perhaps
| that's what's confusing.
|
| However I don't really object to a Range being Enumerable in the full
| sense, even if some of the methods don't make sense; I think it's important
| to distinguish Range#include? / member? from Enumberable#include? / member?

Fully concur. This is essentially the conclusion I arrived at too. It is
confusing from the start: (0..4).kind_of?(Enumerable) can't answer
"sort-of" Fact is, as matz pointed out, Range doesn't even need a
#member? method. Dump Enumerable and add the methods you mention above (plus
#include?).

BTW: I agree #begin and #end are not good method names.

T.