Opened 6 years ago

Closed 6 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 andrew.mathas)

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 6 years ago by ncohen

  • Branch set to u/ncohen/15480
  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 6 years ago by git

  • Commit set to dbe5cbd894e2771f3f430ec310120af68b06022a

Branch pushed to git repo; I updated commit sha1. New commits:

dbe5cbdtrac #15480: Words.eq returns wrong answers

comment:3 Changed 6 years ago by ncohen

  • 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

Last edited 6 years ago by ncohen (previous) (diff)

comment:4 Changed 6 years ago by git

  • Commit changed from dbe5cbd894e2771f3f430ec310120af68b06022a to ad1cb6306d1dd48b2aa91c92ca00bf10fe1430b2

Branch pushed to git repo; I updated commit sha1. New commits:

ad1cb63trac #15480: Two additional doctests

comment:5 Changed 6 years ago by andrew.mathas

  • 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 6 years ago by ncohen

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: Changed 6 years ago by 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...

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 6 years ago by ncohen

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 6 years ago by andrew.mathas

  • 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

Last edited 6 years ago by andrew.mathas (previous) (diff)

comment:10 Changed 6 years ago by andrew.mathas

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 6 years ago by andrew.mathas

  • 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 6 years ago by andrew.mathas

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

4b13af1Editting comments and adding warning to class documentation

comment:13 Changed 6 years ago by ncohen

Works for me ! Thanks ;-)

Less wrong results in Sage.. Wuuhuuu.. :-P

Nathann

comment:14 Changed 6 years ago by andrew.mathas

  • Reviewers set to Andrew Mathas

comment:15 Changed 6 years ago by git

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

ecd32aeFixing a typo

comment:16 Changed 6 years ago by andrew.mathas

  • Status changed from needs_review to positive_review

comment:17 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.13 to sage-6.0

comment:18 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.0 to sage-6.1

comment:19 Changed 6 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.