Duck A La Range
Posted by Rick DeNatale Thu, 20 Sep 2007 15:36:00 GMT
On ruby-talk, Sammy Larbi recently asked if it would make sense to add a length method to Range, something like this:
class Range
def length
self.end - self.begin
end
end This led to an interesting discussion about the varieties of ranges, and ultimately led me to this article about duck types.
This led to an observation by Xavier Noria that
- Ranges don't require their elements to support a "-" method, only :succ and :<=>, so this wouldn't work for all ranges.
- A first approximation of a general implementation of Range#length would be to iterate over the elements of the range and count them but..
- Some ranges might actually have an infinite number of elements, so length doesn't make sense for them.
Home, Home on the Infinite Range
In thinking about this a bit, I'm not sure that you can have a Range with an infinite number of elements which supports enumeration. Xavier gave a range of rational numbers as an example, but I'm not sure I see how you can define both a :<=>, and :succ methods for rational numbers which make sense. The problem is that although rational numbers are countable, they are also densely ordered.
The fact that rationals are countable simply means that you can pair each rational number with an integer. One proof of this constructs the sequence: 1/1, 2/1, 1/2, 1/3, 3/1, 4/1, 3/2, ...
Now this shows that you can put the rationals into an infinite sequence, and define :succ such that (1/1).succ => (2/1), but if you want to keep the normal meaning of :<=>, you have the problem that 2/1 looks like it is less than 1/2.
The fact that rationals are densely ordered means that for any two rationals a <. b there are an infinite number of rationals, c, such that a <. c < b. Which makes it hard to pick which one should be a.succ.
Now it might be possible to come up with an enumerable infinite range which works, but it hurts my head, and it's not really the main point of this article.
What About Non-enumerable Ranges?
The rdoc for Range includes this:
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.
This is true, if you want to use all of the methods of Range, but one can actually usefully create ranges of objects with support <=> but don't support succ.
1.0.methods.include?(:succ) # => false
(1.0..2.0).include?(1.5) # => true Floats respond to <=>, but they don't respond to succ. As shown above you can create a Float range, and use it to see if a number falls within that Range. What you can't do is enumerate such a Range:
(1.0..2.0).to_a # =>
# ~> -:3:in `each': can't iterate from Float (TypeError)
# ~> from -:3:in `to_a'
# ~> from -:3 So what does this have to do with duck typing? It just goes to serve as another illustration of why classes make lousy duck types. It's not just a matter of what an objects class is, in general it's a matter of what the object can do at the time, and that can depend on things other than the class and the methods. The duck in this last example is a bird which can determine whether or not it includes a number, it simply has to quack yes or no when fed a number. It doesn't have to walk along all the numbers it 'contains.'
Whether or not such a duck is useful depends on the user of the duck, not the duck itself.
About That Picture
I searched around to find a non-copyrighted photo of Duck a l'orange, and couldn't find one. I did find one of a Turducken. For those unfamiliar with this bird, it's a boneless turkey, which has been stuffed with a boneless duck, which has in turn been stuffed with a boneless chicken. After thinking about this a bit it seemed appropriate for this article which is after all about the effects of stuffing one object with another.
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.
I’ve already answered this on ruby-talk.
Although the documentation for Range talks about needing succ for elements, it neglects to mention that that requirement only exists if you use certain methods.
In practice, being able to construct a Range of, say, floats for interval testing is not uncommon in Ruby despite what the documentation says.
If you take the position that it’s somehow wrong to built float ranges, then I suppose you should avoid putting elements into an Array which don’t support <=> since if you do the Array#sort method won’t work.
Personally I feel better working with, rather than against, the flexibility provided by Ruby.
Dude, I thought you were totally making up “Turducken” !