Is there any existing implementation of Python2 where ordering is transitive? That is, where it's impossible to see this behaviour without creating user-defined types:
>>> x < y < z < x
True
CPython is not transitive because of this counterexample
x = 'b'
y = ()
z = u'ab'
However, this ordering in CPython is documented as only an implementation detail.
Every mainstream Python implementation fails in one way or another except for Skulpt, but it's arguably an incomplete implementation.
CPython (and variants), PyPy, and Jython:
>>> 'b' < () < u'ab' < 'b'
True
IronPython:
IronPython internally compares the .NET Object.GetHashCode() hashes of unlike objects, so you can break it by abusing the special handling of int and float comparisons and the fact that the internal hash representation of float('+inf') is less than the hash of [] (I'm not sure how stable this is, so it might not work on every installation of IronPython):
>>> 2**200 < float('+inf') < [] < 2**200
True
>>> {1: 3} < {1: 4} < {1: 3}
1
>>> {1: 3} < {1: 3}
0
Skulpt
If you count Skulpt as a complete implementation of Python 2 (it can't compare dictionaries and a few other inconvenient types, and has no unicode type), it actually does work by copying CPython's rules for comparison and conveniently leaving out the unicode type:
# 1. None is less than anything
# 2. Sequence types are greater than numeric types
# 3. [d]ict < [l]ist < [s]tring < [t]uple
>>> None < 0 < {} < [] < '' < ()
True
For CPython 2, you would actually have [t]uple < [u]nicode, but because unicode and str comparisons are handled as a special case, you lose transitivity. Although it's unlikely that Python 2 will get a patch to fix this "bug", I think you can ensure transitivity by just explicitly changing the order from:
[d]ict < [l]ist < [s]tring < [t]uple < [u]nicode
To:
[u]nicode < [d]ict < [l]ist < [s]tring < [t]uple
That way, the special case of str to unicode comparisons doesn't break anything.
False. What spec does {1: 3} < {1: 4} < {1: 3} holding violate? –
Crick {1: 3} < {1: 4} and {1: 4} < {1: 3} can't both be true, since this would make sorting unstable. –
Capias {1: 3} < {1: 4} < {1: 3} violate the Python specs and 'b' < () < u'ab' < 'b' doesn't? Or you mean they are both violations? –
Souvenir {1: 3} < {1: 4} and {1: 4} < {1: 3} can't both hold. 'b' < () < u'ab' < 'b' doesn't violate anything, since sorting those four elements is stable and strings are compared lexicographically. –
Capias set: >>> sorted([set([1]), set([0]), set([1])]) result [set([1]), set([0]), set([1])]. Both inequalities are False if one set is not a subset of other. In Python 3 it is said explicitly that total ordering is not applied to sets or mappings. –
Anisomerous 'b' , () , u'ab' in some case and () , u'ab' , 'b' in another? –
Souvenir sorted(['b' , () , u'ab']) and sorted([() , u'ab' , 'b']) have different results (leaving both the lists unchanged). Isn't this a failure/violation? –
Souvenir Some comparisons are declared as not specified in Python 2.7:
The most important general rules for comparisons are in The Python Language Reference chapter 5. Expressions / 5.9 Comparisons.
The first rules are the well known ones for comparison of numeric types (bool, int, long, float), strings (str, unicode), tuples and lists. The last two rules declare what is not specified:
- Mappings (dictionaries) compare equal if and only if their sorted (key, value) lists compare equal. [5] Outcomes other than equality are resolved consistently, but are not otherwise defined. [6]
- Most other objects of built-in types compare unequal unless they are the same object; the choice whether one object is considered smaller or larger than another one is made arbitrarily but consistently within one execution of a program.
Many specific rules are in Comparison chapter in The Python Standard Library / Built-in Types, referenced above in the question, and in docs about specific types like complex, Decimal or Fraction.
Order comparison is not supported for type complex and it should raise TypeError. Decimal type is compared by value. It is compatible with numbers.Number since Python 2.7. fractions.Fraction is also compared by value.
My reflection: If a relation of comparison can be arbitrary and can be not reproducible within two executions of the program on the same computer, then it is not useful to say about transitivity. All cases above where the order is explicitly not specified in Python 2 should raise TypeError in Python 3.
The transitivity or ordering of builtin types is known broken in Python 2.7 only between types where equivalency of values of different builtin types is implemented but they are not implemented equivalent to other types.
Example: broken transitivity in IronPython (inspired by Blender's comment and simplified):
>>> assert long(0) < 1.0 < [] < long(0) # 0 < 1; 'float' < 'list' < 'long'
Even the equivalency (==), that looks simpler to decide, is also not always transitive. That breaks the transitivity of the operator (<=). See examples in comments. (Thanks for fix) (Equivalency is not the identity. a is b implies a == b, but not vice-versa.)
Examples use many trivial user-defined classes, with names one-letter capital or lowercase:
class A(object): pass
class a(object): pass
...
class z(object): pass
All numeric types have many naturally equivalent values in CPython and IronPython (and probably in all other implementations according docs)
>>> assert (False == 0 == 0L == 0.0 == 0 + 0j == Decimal('0') == Fraction(0, 1) <
... True == 1 == 1L == 1.0 == 1 + 0j == Decimal('1') == Fraction(1, 1))
Numeric types are ordered before all other types in CPython:
>>> assert 0 < 10**1000 < float('inf') < A() < Z() < a()
Numeric types are dispersed between other types in IronPython
>>> assert D() < decimal.Decimal('0') < E()
>>> assert F() < fractions.Fraction(0, 1) < G()
>>> assert b() < False < c() # bool
>>> assert c() < 0 + 0j < d() # complex
>>> assert f() < 0.0 < g() # float
>>> assert i() < 0 < j() # int
>>> assert l() < 0L < m() # long
str, bytearray and unicode have equivalent values
>>> assert bytearray('ab') == 'ab' == u'ab'
Nothing special in ordering to other types is used in CPython,
>>> assert b() < bytearray('ab') < c() # bytearray
>>> assert s() < 'ab' < t() # str
>>> assert u() < u'ab' < v() # unicode in CPython
In IronPython: The type unicode behaves like str. It is not strange because strings are implemented in .NET like unicode and the same is in IronPython.
>>> assert s() < u'ab' < t() # unicode in Iron Python like str
>>> unicode
<type 'str'>
== always being transitive, since bytearray('ab') == 'ab' == u'ab' is true but bytearray('ab') == u'ab' is false (at least in CPython). –
Crick OrderedDict([(0,0), (1,1)]) == {0:0, 1:1} == OrderedDict([(1,1), (0,0)]) provides another counterexample of equality transitivity. –
Demarcation <= operator. –
Anisomerous coerce(...), __cmp__(...). The method __cmp__ is still crucial for comparison for many types in Python 2.7. Many types with total ordering (e.g. int, dict) don't implement __eq__, __lt__... and implement only __cmp__. –
Anisomerous __cmp__, __eq__, __ne__. It is enough to denote the strange result of comparison. –
Anisomerous © 2022 - 2024 — McMap. All rights reserved.
x < y < z < xgives True for OP's example. – Cormier2**200 < float('+inf') < [] < 2**200– Capiasx < y < z < xdoesn't make it a transitivity counterexample.x < y < z and not x < zdoes. – Crickx < y < z < xholds and your relation is also transitive, then you get bothx < zandz < x, which violates antisymmetry. – Capiasx < y < z and not x < z. – Demarcationa < borb < amust hold for unequalaandb. – Capias<to object of type Y", i.e. when the types are different and the types are not both numeric/strings, then the order of the values is defined by the order of just their types. This is even stronger than antisymmetry because it tells you that ifa < b -> forall x, y, type(x)=type(a), type(y) = type(b) -> x < y. – PeguTypeError! – Pegu__lt__to return True and also__gt__to return True, it would be inconsistent mathematically (because he claims to be both bigger and smaller than 0), but one might call it 'consistent' in another sense because it is consistently wrong - the behaviour is always the same across e.g. different interpreters and platforms. 'Consistent' as 'deterministic', 'predictable'. – Demarcation