Opened 7 years ago
Closed 7 years ago
#15480 closed defect (fixed)
Words.__eq__ returns wrong answers
Reported by: | ncohen | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.1 |
Component: | combinatorics | Keywords: | |
Cc: | slabbe, vdelecroix, sage-combinat, saliola | Merged in: | |
Authors: | Nathann Cohen | Reviewers: | Andrew Mathas |
Report Upstream: | N/A | Work issues: | |
Branch: | u/andrew.mathas/ticket/15480 (Commits) | Commit: | ecd32aebf69a5cfc00a9bd4735eb47b100c8b09c |
Dependencies: | Stopgaps: |
Description (last modified by )
Right now equality between sets of words only compares the alphabets:
sage: Words(3, 10) == Words(3,900) True sage: Words(2, finite=False) == Words(2) True sage: Words(2) == Words(2,30) True sage: Words(10,0) == Words(20,0) False sage: WordPaths('abcd') == Words("abcd",3) True
I am not proud of this patch's code, but I see NO other way to fix all these incorrect answers without rewriting the class hierarchy. The fact that a class of finite words is an instance (i.e. it inherits) from a class of infinite words makes it really hard to implement O_o
sage: isinstance(Words(4,30), type(Words(3))) True
You cannot be sure, when implementing the __eq__
method of Words_all
, that self really represents an infinite class of words.
Besides, the old code reads:
if isinstance(other, Words_all): return self.alphabet() == other.alphabet() else: return NotImplemented
I haven't been able to guess when not (type(self) is type(other))
does not mean that the two classes should not be reported as equal.
Though the old code seems to imply that this can happen.
If this can happen we need to add a doctest somewhere.
Nathann
Change History (19)
comment:1 Changed 7 years ago by
- Branch set to u/ncohen/15480
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 7 years ago by
- Commit set to dbe5cbd894e2771f3f430ec310120af68b06022a
comment:3 Changed 7 years ago by
- Description modified (diff)
Oh. I see. That's for
sage: Words("abcd") == WordPaths("abcd") True
Then for this case I will keep the old behaviour.
Ready for review ! This is only hacks, but it fixes the wrong results :-/
Nathann
comment:4 Changed 7 years ago by
- Commit changed from dbe5cbd894e2771f3f430ec310120af68b06022a to ad1cb6306d1dd48b2aa91c92ca00bf10fe1430b2
comment:5 Changed 7 years ago by
- Description modified (diff)
I was just looking at this and I agree it's a mess. I thought that you might be able to get away with just
if self.cardinality()!=other.cardinality(): return False if self.cardinality()==1: return True if self.alphabet() != other.alphabet(): return False return type(self)==type(other)
but this does not catch
sage: Words("abcd") == WordPaths("abcd") True
As I don't really play with these things it is not clear to me that these two should be equal.
Is this really correct?
comment:6 Changed 7 years ago by
I did not know the existence of WordPaths? either before this patch, but I think this has been done on purpose for there are 4 doctests in the __eq__
function that test this kind of equalities. So it's not just a result of the code, it seems to be somebody wanted to get there. But that's just guessing.
As per the cardinality test I tried to avoid calling self.cardinality()
twice. I was wondering if this could be costly from time to time, but it's defintely prettier without this caching, so if you think it's overkill let's rewrite it as you did as I cannot produce an word where .cardinality()
takes time.
Nathann
comment:7 follow-up: ↓ 9 Changed 7 years ago by
Personnally, I would delete the file combinat/words/paths.py
and rewrite it all. So if there is some problem with it, don't try too much to fix it...
I am not familiar with the git process of reviewing a patch... Is it easy or difficult to learn? Is Sage ready for including git patches? I will have time to learn the git process in January or February.
Sébastien
comment:8 Changed 7 years ago by
Yooooooo !
Well, I can't put into Sage any code that breaks doctests, and I know absolutely nothing of what WordPaths? is meant to do so I cannot really rewrite it O_o
The word.py file could very well do with a complete rewrite, to be honest. These class inheritances are hell to work with. Or perhaps we would just need to create additional classes, so that classes exposed to the user can't be Words_all or anything similar. My problem is that there is no class for infinite words which will not ALSO be inherited by classes of finite words. So it's pretty hard to write infinite-specific code. This could be solved by only returning to the user new classes that also inherits from Words_all even when the user wants infinite words (which are handled by Words_all right now). This way we would have a way to know what each class deals with.
Learning git takes a bit of time, though you can easily master it with a week-end's afternoon or something like that. It's funny, and new but not so complicated after all. And you can ask around if you have questions :-)
Aaaaaaand everything should be documented on #14481 as this will be the future dev documentation !
Nathann
comment:9 in reply to: ↑ 7 Changed 7 years ago by
- Description modified (diff)
Replying to slabbe:
Personnally, I would delete the file
combinat/words/paths.py
and rewrite it all. So if there is some problem with it, don't try too much to fix it...
Unfortunately because of sage's depreciation policy we can't just remove paths.py
, even if this is the right thing to do.
I was going to suggest that we instead remove the doc tests of the form sage: Words("abcd") == WordPaths?("abcd") True }}} Without these we could have a more natural looking equality test.
Unfortunately, with this "more natural" equiality test there are now multiple doctest failures in finite_word.py and in word_generators.py. So this is not a good solution. I have not drilled down to find out why these doctests fail because this does not happen with Nathann's patch. So, as unnatural as the code looks, it is perhaps the best way to go.
Andrew
comment:10 Changed 7 years ago by
ps. Git has a bit of a learning curve, but it is quite nice once you get use to it (of course, getting used to it and being able to use it "properly" are not quite the same thing.) I'm happy to review this ticket.
comment:11 Changed 7 years ago by
- Branch changed from u/ncohen/15480 to u/andrew.mathas/ticket/15480
- Created changed from 12/03/13 11:30:38 to 12/03/13 11:30:38
- Modified changed from 12/04/13 12:09:42 to 12/04/13 12:09:42
comment:12 Changed 7 years ago by
- Commit changed from ad1cb6306d1dd48b2aa91c92ca00bf10fe1430b2 to 4b13af1227aae4570d94df704aeace1a5aec927c
- Status changed from needs_review to positive_review
I've pushed a new commit which adds a warning message to the documentation of Words_all
about extending the class and potential problems with __eq__
and elsewhere.
All doctests pass in sage/combinat so assuming that the patchbot is happy I give this a positive review.
A.
New commits:
4b13af1 | Editting comments and adding warning to class documentation |
comment:13 Changed 7 years ago by
Works for me ! Thanks ;-)
Less wrong results in Sage.. Wuuhuuu.. :-P
Nathann
comment:14 Changed 7 years ago by
- Reviewers set to Andrew Mathas
comment:15 Changed 7 years ago by
- Commit changed from 4b13af1227aae4570d94df704aeace1a5aec927c to ecd32aebf69a5cfc00a9bd4735eb47b100c8b09c
- Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
ecd32ae | Fixing a typo |
comment:16 Changed 7 years ago by
- Status changed from needs_review to positive_review
comment:17 Changed 7 years ago by
- Milestone changed from sage-5.13 to sage-6.0
comment:18 Changed 7 years ago by
- Milestone changed from sage-6.0 to sage-6.1
comment:19 Changed 7 years ago by
- Resolution set to fixed
- Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits: