Words.__eq__ returns wrong answers

[nathanncohen]

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

CC: @seblabbe @videlec @sagetrac-sage-combinat @saliola

Component: combinatorics

Author: Nathann Cohen

Branch/Commit: u/andrew.mathas/ticket/15480 @ ecd32ae

Reviewer: Andrew Mathas

Issue created by migration from https://trac.sagemath.org/ticket/15480

[nathanncohen]

Branch: u/ncohen/15480

[sagetrac-git]

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

[dbe5cbd](https://github.com/sagemath/sagetrac-mirror/commit/dbe5cbd)

trac #15480: Words.__eq__ returns wrong answers

[sagetrac-git]

Commit: dbe5cbd

[nathanncohen]

comment:3

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

[sagetrac-git]

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

[ad1cb63](https://github.com/sagemath/sagetrac-mirror/commit/ad1cb63)

trac #15480: Two additional doctests

[sagetrac-git]

Changed commit from dbe5cbd to ad1cb63

[AndrewMathas]

comment:5

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?

[nathanncohen]

comment:6

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

[seblabbe]

comment:7

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

[nathanncohen]

comment:8

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

[AndrewMathas]

comment:9

Replying to @seblabbe:

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

[AndrewMathas]

comment:10

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.

[AndrewMathas]

Changed branch from u/ncohen/15480 to u/andrew.mathas/ticket/15480

[AndrewMathas]

Changed commit from ad1cb63 to 4b13af1

[AndrewMathas]

comment:12

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](https://github.com/sagemath/sagetrac-mirror/commit/4b13af1)

Editting comments and adding warning to class documentation

[nathanncohen]

comment:13

Works for me ! Thanks ;-)

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

Nathann

[AndrewMathas]

Reviewer: Andrew Mathas

[sagetrac-git]

Changed commit from 4b13af1 to ecd32ae

[sagetrac-git]

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

[ecd32ae](https://github.com/sagemath/sagetrac-mirror/commit/ecd32ae)

Fixing a typo