Opened 10 years ago
Last modified 5 years ago
#9677 needs_work defect
Sage Sets don't implement genuine comparison
Reported by: | rlm | Owned by: | AlexGhitza |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | basic arithmetic | Keywords: | |
Cc: | kini | Merged in: | |
Authors: | Robert Miller | Reviewers: | Mike Hansen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: | todo |
Description
Right now there is either equals, or less than. If a != b
, then we get a < b
but not b > a
:
sage: a = Set([1]) sage: b = Set([]) sage: a == b False sage: a < b True sage: b > a False
This came up in
http://groups.google.com/group/sage-devel/browse_thread/thread/1c058efd05d3b91f
Attachments (1)
Change History (19)
comment:1 Changed 10 years ago by
comment:2 follow-up: ↓ 3 Changed 10 years ago by
I completely, emphatically disagree. I think that total orderings are very important to try to preserve wherever possible, especially in this case.
comment:3 in reply to: ↑ 2 Changed 10 years ago by
Replying to rlm:
I completely, emphatically disagree. I think that total orderings are very important to try to preserve wherever possible, especially in this case.
See also my comments on the thread referenced above.
comment:4 Changed 10 years ago by
- Status changed from new to needs_review
comment:5 Changed 10 years ago by
I don't understand why you have these lines:
if len_self != len_other: return cmp(len_self, len_other)
that just makes it so that the comparison is incompatible with what it is for lists. Why not just make it the same?
comment:6 Changed 10 years ago by
You mean just remove those lines? That's fine with me. This was just meant to be an optimization.
comment:7 Changed 10 years ago by
Patch is updated.
comment:8 Changed 10 years ago by
I guess you didn't test your patch? I just applied it and ran tests on sage.math, and got:
---------------------------------------------------------------------- The following tests failed: sage -t devel/sage/sage/graphs/graph_generators.py # 2 doctests failed sage -t devel/sage/sage/graphs/digraph.py # 2 doctests failed sage -t devel/sage/sage/combinat/sf/powersum.py # 0 doctests failed sage -t devel/sage/sage/graphs/graph.py # Time out ---------------------------------------------------------------------- Timings have been updated. Total time for all tests: 488.9 seconds
comment:9 Changed 10 years ago by
- Status changed from needs_review to needs_work
Changed 8 years ago by
comment:10 Changed 8 years ago by
- Reviewers set to Mike Hansen
- Status changed from needs_work to positive_review
I rebased the patch and ran the tests which do pass. I think we can give this positive review.
comment:11 follow-up: ↓ 12 Changed 8 years ago by
- Status changed from positive_review to needs_work
I think the patch behaviour of
sage: a = [2,3] sage: b = [2,3,4j] sage: set(a) < set(b) True sage: Set(a) < Set(b) False
is too dangerous to let pass unremarked.
comment:12 in reply to: ↑ 11 Changed 8 years ago by
Replying to dsm:
I think the patch behaviour of
sage: a = [2,3] sage: b = [2,3,4j] sage: set(a) < set(b) True sage: Set(a) < Set(b) Falseis too dangerous to let pass unremarked.
In Python (according to http://docs.python.org/library/sets.html) for the set type we have: "The subset and equality comparisons do not generalize to a complete ordering function. For example, any two disjoint sets are not equal and are not subsets of each other, so all of the following return False: a<b, a==b, or a>b. Accordingly, sets do not implement the cmp() method."
The Python convention does make sense and is what most people would expect... and is the direction Sage should move in.
RLM who wrote "I completely, emphatically disagree." has got sucked up into an industry job, so isn't involved in Sage development right now, so I don't think he'll care much what happens with this ticket.
That said, having a total ordering -- which is different and inconsistent with set's order -- is useful (!). However, it can be done as a separate explicit function or method, which can get passed to the sort method explicitly.
comment:13 Changed 8 years ago by
- Cc kini added
comment:14 Changed 7 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:15 Changed 6 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:16 Changed 6 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:17 Changed 6 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:18 Changed 5 years ago by
- Stopgaps set to todo
The noted behaviour is definitely a bug. However, the attached patch solves this by introducing an attempt at inducing a total ordering on Sets by sorting them first by cardinality and then by lexicographic ordering on the sorted list of set elements. This only works if the elements of the set have a total ordering implemented.
While python used to try to have a total ordering on all objects, this has been abandoned (e.g. python complex numbers and python sets)
Shouldn't the sage design follow python in this respect? See also
http://groups.google.ca/group/sage-devel/msg/eab3aafb319a2769