Words.__eq__ returns wrong answers

[ncohen]

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

[git]

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

​dbe5cbd

trac #15480: Words.eq returns wrong answers

[ncohen]

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

[git]

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

​ad1cb63

trac #15480: Two additional doctests

[andrew.mathas]

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?

[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

[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

[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

[andrew.mathas]

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

[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.

[andrew.mathas]

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

[ncohen]

Works for me ! Thanks ;-)

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

Nathann

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​ecd32ae

Fixing a typo