On Aug 4, 4:23 am, Robert Miller <rlmills...@gmail.com> wrote: > I'm not sure what the point of a comparison function is if we don't > implement a total ordering. The main place cmp methods get used is in > sorting.
But it is a fact that Python has already abandoned total ordering semantics for "<". > If you have a large list of objects, and, for example, you > want to know whether X is in the list, you might find this out by > looping over the whole list. Or, if the list is sorted, you can use > cmp to do a binary search. Thus testing for containment goes from n to > log(n). Or you use hashes and it becomes an "O(1)" problem, which is how python solves membership for sets and dictionaries. (I always have trouble believing this is really O(1), but it does work very well in practice) > Python's own sort function uses cmp, which suggests to me that > it is a silly decision to abandon total orderings. Sage's uniq > function only works if the objects input have a total ordering defined > by their cmp method. Then that is an implementation error in uniq. Turning the sequence into a set and then into a sequence should be more efficient, provided that __hash__() is implemented decently. I agree it's questionable that sort gives undefined results on python sets. I would think an error would be preferable but the current behaviour is documented. > I think that __cmp__ isn't something for which > "canonical" in the mathematical sense should be applied. This is a > computer scientific operation, for doing computer scientific things, > such as smart searches through lists and giving unique output. To ease the transition to python 3.0, sage should start migrating to __lt__ etc. If the method were just __cmp__, I would agree with you. However, the infix notation a < b translates to a __cmp__ call too, and in a computer algebra system, I expect "a < b" to have a decidedly mathematical meaning. > it would be handy to be able to > count on something as simple as sorted(L) returning the same thing for > any permutation of L. I really don't think that is too much to ask of > a computer algebra system. But you are already asking more than the underlying computer language, python, provides. There are some other cases where sage departs from python semantics (transitivity of ==), but that is for mathematical reasons. I would be really disappointed if sage decides to be less mathematical and more computer scienctific than python. It is going to be a herculean task to avoid a < b < c < a from occurring for any sage objects a,b,c, which will be necessary for safeguarding sorted(L). In categories where string representations tend to provide a poor representation of the identity of an element, you can use explicit equality tests for doctesting. -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
