# String + Range = Strange

**URL:** <https://www.ruby-forum.com/t/string-range-strange/49215>\
**Category:** Ruby\
**Created:** [December 1, 2005, 2:10pm UTC](https://www.ruby-forum.com/t/string-range-strange/49215 "2005-12-01T14:10:35Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![martindemello](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/f08c70/32.png) [@martindemello](https://www.ruby-forum.com/u/martindemello)\
**Post date:** [December 1, 2005, 2:10pm UTC](https://www.ruby-forum.com/t/string-range-strange/49215/1 "2005-12-01T14:10:35Z")

</div>

How does this work?

irb(main):002:0\> (“a”…“z”).to\_a  
=\> [“a”, “b”, “c”, “d”, “e”, “f”, “g”, “h”, “i”, “j”, “k”, “l”, “m”,  
“n”, “o”, “p”, “q”, “r”, “s”, “t”, “u”, “v”, “w”, “x”, “y”, “z”]  
irb(main):003:0\> (“aa”…“z”).to\_a  
=\> []  
irb(main):004:0\> (“aa”…“1z”).to\_a  
=\> []  
irb(main):005:0\> (“aa”…“b1”).to\_a  
[“aa”…“zz” elided]

What I mean is, what algorithm is used to determine that the stream of  
successors is not going to hit the endpoint of the range? And could this  
be used to do a faster-than-O(n) set memnbership test?

martin

---

<div class="post-metadata">

**Author:** ![martindemello](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/f08c70/32.png) [@martindemello](https://www.ruby-forum.com/u/martindemello)\
**Post date:** [December 1, 2005, 2:30pm UTC](https://www.ruby-forum.com/t/string-range-strange/49215/2 "2005-12-01T14:30:58Z")

</div>

Exactly.

And the same holds true of many a sequence, like even numbers. Now how  
can membership be optimized in a custom manner?

T.

---

<div class="post-metadata">

**Author:** ![martindemello](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/f08c70/32.png) [@martindemello](https://www.ruby-forum.com/u/martindemello)\
**Post date:** [December 1, 2005, 6:47pm UTC](https://www.ruby-forum.com/t/string-range-strange/49215/3 "2005-12-01T18:47:43Z")

</div>

Martin wrote:

> irb(main):005:0\> (“aa”…“b1”).to\_a  
> [“aa”…“zz” elided]  
> Then - Trans wrote:  
> Exactly.
> 
> And the same holds true of many a sequence, like even numbers. Now how can membership be optimized in a custom manner?

Maybe I’m about to say something silly (by not being up-to speed) but  
why on earth could anyone consider the output from the above one-liner  
to be sane? Not only is upper bound exceeded (under any sensible notion  
of comparison) but many intermediate values are missing for example “b!”  
and “a~” as well as more esoteric strings with control characters such  
as “b\0” and all strings with capital letters in them?  
To make matters worse, even if we accept that ranges have a peculiar  
semantics over strings, they are inconsistent.

irb(main):001:0\> (“aa”…“b1”)===“zz”  
=\> false  
irb(main):002:0\> (“aa”…“b1”).to\_a.include? “zz”  
=\> true

The max method also behaves in a very counter intuitive way without  
converting to an array:

irb(main):003:0\> (“A”…“d”).max  
=\> “Z”

Establishing set membership is something for which (in other languages)  
I’ve long had an active interest - which brings me to comment on the  
even numbers question. A really powerful resolution of range would  
support “modifiers”:

Projection- Applying a function to each element  
Selection- Filtering values which do not exist  
Intersection- Retaining only values present in both  
Union - Retaining values present in either  
Minus - Retaining values present in the first but not the second.

It is interesting to note that it is possible to efficiently compute  
membership (without enumerating all the possible values) unless  
Projection is applied. If projection is applied then it is necessary  
that the projection function can be inverted - which can’t be done in  
the general case. So, given an appropriate implementation of efficient

- the following generate the odd numbers below n.

efficient(0…n).filter { |x| x%2==0 }  
efficient(0…(n/2)).project { |x| x=x\*2 }  
efficient(0…n).minus efficient(0…n).filter { |x| x%2==1 }  
… and many, many more possibilities…

For each of these (except project, assuming no-one supplies the  
hand-verified inverse to the supplied function) there are efficient  
[i.e. far better than O(n)] ways to establish membership.

Does anyone not claim that ranges are broken with respect to strings?

---

<div class="post-metadata">

**Author:** ![martindemello](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/f08c70/32.png) [@martindemello](https://www.ruby-forum.com/u/martindemello)\
**Post date:** [December 1, 2005, 9:34pm UTC](https://www.ruby-forum.com/t/string-range-strange/49215/4 "2005-12-01T21:34:34Z")

</div>

Bob S. wrote:

> The point is that even though “aa”…“b1” is a valid range, calling  
> succ repeatedly from the starting point will never yield the endpoint.

This, I think is the crux of the matter. It seems to me that given that  
if “aa”…“b1” is a valid range, that calling calling succ on “aa” should  
logically eventually reach “b1”. I understand that in Ruby, today, it  
doesn’t.

I suppose I can get the behaviour I expect by doing something like this.

class String  
def succ  
s=String.new self  
(s.length-1).downto 0 do |i|  
s[i]=(s[i]+1)&0xff  
return s unless s[i]==0  
end  
1.chr.concat s  
end  
end

Is there any good reason that this isn’t the default behaviour for succ

- given that Ruby claims an objective is to have “sensible defaults”? I  
can see a justification for having a method defined how String#succ is  
defined today - but I don’t see why it has to be as the default succ  
method… especially since it gives such counter-intuitive results when  
used with ranges. Alternatively - I suppose - it might make sense if  
ranges didn’t use succ?

Ranges in regexps don’t work the same “smart” way - wouldn’t consistent  
default behaviour be far preferable?

---

<div class="post-metadata">

**Author:** ![martindemello](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/f08c70/32.png) [@martindemello](https://www.ruby-forum.com/u/martindemello)\
**Post date:** [December 2, 2005, 7:25am UTC](https://www.ruby-forum.com/t/string-range-strange/49215/5 "2005-12-02T07:25:54Z")

</div>

Steve [RubyTalk] wrote:

> Bob S. wrote:
> 
> > The point is that even though “aa”…“b1” is a valid range, calling  
> > succ repeatedly from the starting point will never yield the endpoint.
> 
> This, I think is the crux of the matter. It seems to me that given that  
> if “aa”…“b1” is a valid range, that calling calling succ on “aa” should  
> logically eventually reach “b1”. I understand that in Ruby, today, it  
> doesn’t.

I think that String#succ is of limited usefulness, and will _always_ be  
a  
source of strange edge cases like this.

Personally, I think that (perhaps) String ranges should be disallowed as  
being mostly nonsensical (unless a rigid order, like character set  
order,  
were imposed).

Hal

---

<div class="post-metadata">

**Author:** ![martindemello](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/f08c70/32.png) [@martindemello](https://www.ruby-forum.com/u/martindemello)\
**Post date:** [December 1, 2005, 7:36pm UTC](https://www.ruby-forum.com/t/string-range-strange/49215/6 "2005-12-01T19:36:21Z")

</div>

Steve [RubyTalk] wrote:

> > can membership be optimized in a custom manner?
> 
> Maybe I’m about to say something silly (by not being up-to speed) but  
> why on earth could anyone consider the output from the above one-liner  
> to be sane? Not only is upper bound exceeded (under any sensible notion  
> of comparison) but many intermediate values are missing for example “b!”  
> and “a~” as well as more esoteric strings with control characters such  
> as “b\0” and all strings with capital letters in them?  
> To make matters worse, even if we accept that ranges have a peculiar  
> semantics over strings, they are inconsistent.

I don’t know about being sane, but the behavior is explicable by the  
fact that:

```
Range#to_a (Enumerable#to_a) calls
Range#each, which uses
String#step (for Strings, anyway), which uses
String#upto, which calls on
String#succ (to generate successive entries)
and String#<=> (to compare against the endpoint)

```

The key is that String#upto stops iterating as soon as String#succ  
generates either

a) a string lexically equal to the endpoint (or the endpoint’s  
successor, if the range excludes the endpoint), or  
b) a longer string.

(see rb\_str\_upto() in string.c in the Ruby source code)

It’s this second factor that’s coming into play here.

```
"aa".succ => "ab"
"az".succ => "ba"
...
"zy".succ => "zz"
"zz".succ => "aaa" # stop iterating here, "aaa" is longer than "zz"

```

The point is that even though “aa”…“b1” is a valid range, calling succ  
repeatedly from the starting point will never yield the endpoint.

> irb(main):001:0\> (“aa”…“b1”)===“zz”  
> =\> false

Right, because this is a check on the endpoints.

> irb(main):002:0\> (“aa”…“b1”).to\_a.include? “zz”  
> =\> true

Also right, because succ eventually generates ‘zz’

> The max method also behaves in a very counter intuitive way without  
> converting to an array:
> 
> irb(main):003:0\> (“A”…“d”).max  
> =\> “Z”

Again, ‘Z’.succ is ‘AA’, so the iteration stops. ‘d’ is never reached,  
and ‘Z’ is the last element generated.

Note that (‘A’…‘d’).last =\> ‘d’

> Does anyone not claim that ranges are broken with respect to strings?

The point is that ‘A’…‘d’ is somewhat nonsensical given the default  
implementation of String#succ. However, you could define String#succ in  
such a way that ‘A’…‘d’ was logical.

(very) contrived example:

```
class String
  def succ
    self.downcase[0].succ.chr
  end
end

('A'..'d').to_a => ["A", "b", "c", "d"]
('A'..'d').max => 'd'
```

---

<div class="post-metadata">

**Author:** ![martindemello](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/f08c70/32.png) [@martindemello](https://www.ruby-forum.com/u/martindemello)\
**Post date:** [December 2, 2005, 12:47pm UTC](https://www.ruby-forum.com/t/string-range-strange/49215/7 "2005-12-02T12:47:59Z")

</div>

Hal F. wrote:

> Steve [RubyTalk] wrote:
> 
> > This, I think is the crux of the matter. It seems to me that given  
> > that if “aa”…“b1” is a valid range, that calling calling succ on  
> > “aa” should logically eventually reach “b1”. I understand that in  
> > Ruby, today, it doesn’t.  
> > I think that String#succ is of limited usefulness, and will _always_ be a  
> > source of strange edge cases like this.  
> > I can see circumstances where it might be useful to have a method  
> > defined as succ currently is (for example, maybe, when generating  
> > human-readable indices where character-encoding-order makes no sense.  
> > Ruby’s notion of String, is far more powerful than that suggests - it  
> > allows an encoding of an arbitrary byte sequence - i.e. Ruby Strings  
> > (unlike strings in most languages) are appropriate type for manipulating  
> > binary “messages” - which is an _extremely_ useful feature (at least it  
> > is to me!)  
> > Personally, I think that (perhaps) String ranges should be disallowed as  
> > being mostly nonsensical (unless a rigid order, like character set order,  
> > were imposed).  
> > I hope that they are not. Obviously, the current mish-mash is far from  
> > desirable but I, for one, will want to determine if a given binary byte  
> > sequence is “between” two other byte sequences. The present situation  
> > is that I can do this using ranges if I replace succ with a “more  
> > sensible” (if likely less efficient) version to the default. I wouldn’t  
> > want to loose the support for byte-sequence ranges using strings -  
> > though I would be wholly in favour of any suggestion to rename succ  
> > “alpha\_num\_succ” (or similar) and to implement succ as iterating of byte  
> > sequence. I can’t see any reason that, by default, any standard type  
> > should not support a consistent total ordering… I hope that, in  
> > future, my wish might become reality. 🙂

Steve