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)

trac_9677.patch (2.4 KB) - added by mhansen 8 years ago.

Download all attachments as: .zip

Change History (19)

comment:1 Changed 10 years ago by nbruin

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

comment:2 follow-up: Changed 10 years ago by rlm

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 rlm

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 rlm

  • Status changed from new to needs_review

comment:5 Changed 10 years ago by was

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 rlm

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 rlm

Patch is updated.

comment:8 Changed 10 years ago by was

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 was

  • Status changed from needs_review to needs_work

Changed 8 years ago by mhansen

comment:10 Changed 8 years ago by mhansen

  • 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: Changed 8 years ago by dsm

  • 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 was

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)
False

is 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 kini

  • Cc kini added

comment:14 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:15 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:16 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:17 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:18 Changed 5 years ago by jakobkroeker

  • Stopgaps set to todo
Note: See TracTickets for help on using tickets.