From: "trans. (T. Onoma)" Date: 2004-10-08T01:19:21+09:00 Subject: Re: Range behavior (Re: [RCR] New [] Semantics) Brian, you make some excellent points, and clarify the issues. Thanks. A BIG question that comes to mind after reading your post is this: What do people usually use Range for? Is it continuous or discrete? I know there is some of both, but I wonder if one far exceeds the other. Hopefully yes, b/c I think the solution must basically fall to something like this: - Range is defined as discrete. It represents an iterative set. - The range has it's own #succ which *defaults* to the #succ method of the seed (first) value, but can be easily overridden. - The Ranges #succ can be overridden as either a proc or a an object. If an object, then each step is simply determined by the addition of that object, i.e. self + #succ. If that succ object is a Numeric, then the range is a numeric range and can gain the speed advantages of the faster modulo #member? code. - Range is Enumerable, and #include? is the same as #member? and #===. - It should be defined by seed and number of steps, not an end member. If not, then we need a "when to end" proc, as well as end_exclusive? in order for this proc to default to succ <=> end >= 0, or > 0. plus the dilema of infinite loops. That gets messy. So I think not. - A new class is made for the continuous uses called Interval. - The Interval is defined by a first and last, exclusive/inclusive. - For Interval the #member?, #include, and #=== methods mean "circumscribes". - I'm not sure how the two will relate, if one can be subclass of the other but no doubt the Interval can have a suitable #to_rng(div_size) method. Of course that's all well and good, but what about the literal form now? Will a..b be an Interval or a Range? And how will we literally write the other? T. On Thursday 07 October 2004 11:07 am, Brian Candler wrote: | I can understand why there is not an explicit flag at the moment, because | generally it's implicit: | - you can't use the continuous methods if the lower and upper bounds don't | respond to spaceship* | - you can't use the discrete methods if the lower bound doesn't respond to | 'succ', or the upper bound doesn't respond to spaceship* | | [*] Actually, I might not have those the right way round. I don't know, | without looking at the source, whether it is bounds <=> member or member | <=> bounds which is tested. | | irb(main):001:0> (3.3..5.3).each {|x| puts x} | TypeError: cannot iterate from Float | | Since the discrete methods rely on succ, == and spaceship all being | available, then I can't think of any case where a range would work usefully | for the discrete case but not the continuous case. | | The flag you propose might be useful if you want to make the semantics of | === different for discrete/continuous ranges. However it seems reasonable | for === to mean 'continuous range', because that's the case which almost | always is available. | | Actually, although Range#each is useful, I can see little use for | Range#member?. Why iterate through a range stepwise when there is almost | always a better way to test membership? (It may be domain-specific though, | e.g. if bounds are Integer then test for elem.to_i == elem) | | If Range#member? is not particularly useful, that's another reason why it | should not be the default for ===. And it could be inherited from | Enumerable, rather than having its own implementation. | | > This becomes increasing interesting (or frustrating depending on your | > slant) when we consider the further advantages of having a NumericRange | > --notice that its advantage is specific to discreteness (member modulo). | > But all Ranges are based on succ and are therefore by definition discrete | > --only Numeric ranges can be Continuous. | | I don't see in principle why you can't have a continuous range foo..bar | where foo and bar are not Numeric, but do respond to <=>. Can't think of a | useful example though :-) | | > Consider further how succ determines successive members --a Range is an | > indeterminate ordered set built by iteration. Oddly one defines a Range | > with a first and last argument, but iterations are supposed to be defined | > by a seed (first) and the number of successive iterations. And there is | > good reason for this: there is no way to be sure that any given _last_ is | > a member of the set! Look at this: | | Indeed - which is why a Ruby discrete range relies on spaceship to | determine whether the end of iteration has been reached. | | > class ShrinkyDink | > def initialize(x); @x = x.to_i; end | > def succ; @x - 1; end | > def <=>(b); @x <=> b; end | > end | > | > rng = ShrinkyDink.new(0)...ShrinkyDink.new(100) | | This is a bit odd though. Your 'succ' method returns an Integer, not | another instance of ShrinkyDink. Do you mean this? | | def succ; self.class.new(@x-1); end | | > Not only is ShrinkyDink.new(100) not a member of the range, but nothing | > "inbetween" the two is either! | | It's not a 'member', although ShrinkyDink(-50) is. And ShrinkyDink(50) is | included within the range, but it's not a member. Argh! | | class ShrinkyDink | attr_reader :x | def initialize(x); @x = x.to_i; end | def succ; ShrinkyDink.new(@x - 1); end | def <=>(b); @x <=> b.x; end | end | | rng = ShrinkyDink.new(0)...ShrinkyDink.new(100) | p rng.include?(ShrinkyDink.new(50)) # true | p rng.include?(ShrinkyDink.new(150)) # false | # p rng.member?(ShrinkyDink.new(-50)) # would be true, except for Ruby | bug | | # rng.each { |a| p a } # infinite loop! | | There is an implied contract that #succ takes you 'closer' to the upper | bound. Unfortunately the direction of the spaceship test is fixed. In your | case | | rng = ShrinkyDink.new(100)...ShrinkyDink.new(0) | | might have been useful in the discrete case, except that it never iterates | because ShrinkyDink.new(100) > ShrinkyDink.new(0) by your spaceship | definition. It's not useful in the continuous case either, because all | values are out of range. | | So, how else could discrete ranges be handled? Maybe if they provided | either (a) an iteration count [as you suggested]; or | (b) a final element, which can be tested using == alone; or | (c) a proc which determines when the iteration is complete | | rather than forcing the test { |e| e < upperbound } | or { |e| e <= upperbound } which happens now. | | ------------------------------------------------------------------------- | class DiscreteRange1 | include Enumerable | def initialize(lower, count) | @lower = lower | @count = count | end | def each | val = @lower | @count.times do | yield val | val = val.succ | end | end | end | | class DiscreteRange2 | include Enumerable | def initialize(lower, final, exclude_end=false) | @lower = lower | @final = final | @exclude_end = exclude_end | end | def each | val = @lower | while val != @final | yield val | val = val.succ | end | yield val unless @exclude_end | end | end | | class DiscreteRange3 | include Enumerable | def initialize(lower, &cond) | @lower = lower | @cond = cond | end | def each | val = @lower | while @cond.call(val) | yield val | val = val.succ | end | end | end | | DiscreteRange1.new(10,5).each { |x| puts x } | DiscreteRange2.new(10,14).each { |x| puts x } | DiscreteRange3.new(10) { |x| x < 15 }.each { |x| puts x } | ------------------------------------------------------------------------- | | The third is the most general pattern. Current Ruby ranges could be | simulated by | | DiscreteRange3.new(lower) { |x| x < upper } # exclude_end | DiscreteRange3.new(lower) { |x| x <= upper } # not exclude_end | | So, all very interesting, but where does this leave (3..5) ? | | - we want interval semantics: | case n | when (0...3) | # xxx | when (3..7.5) | # xxx | end | | - we want discrete iterator semantics | b = (0..3).to_a | | - there's no reason why the upper bound couldn't be a proc: | | (0..proc{|x| x<3}).to_a | | - if the upper bound is not a proc, then ISTM that DiscreteRange2 would be | a reasonable pattern, allowing your ShrinkyDinks to iterate backwards. | However it would break | | (0..3.5).to_a # becomes infinite | | - ranges with a length, rather than an upper bound, are definitely of | interest because of the parallel with substrings and array slices: | | a[3,2] # from 3 for 2 elements | | and so I wonder if having an explicit object for them could tidy this area | up. | | That's more than enough thinking aloud though! | | Regards, | | Brian. -- ( o _ カラチ // trans. / \ transami@runbox.com I don't give a damn for a man that can only spell a word one way. -Mark Twain