#8920 closed defect (fixed)
Factor code between words's alphabets and sets/enumerated sets/ordered sets
Reported by: | hivert | Owned by: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-5.8 |
Component: | combinatorics | Keywords: | Words, Sets, Cernay2012, days45 |
Cc: | sage-combinat, vdelecroix, sstarosta | Merged in: | sage-5.8.beta2 |
Authors: | Vincent Delecroix, Štěpán Starosta | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #13801, #6495 | Stopgaps: |
Description (last modified by )
Create a class TotallyOrderedFiniteSet
in sage.sets. Delete the different classes for alphabets (in sage.combinat.words.alphabet) and use the one in Sage (included the freshly created TotallyOrderedFiniteSet
).
Attachments (1)
Change History (33)
comment:1 Changed 11 years ago by
- Cc vdelecroix added
- Keywords Cernay2012 added
comment:2 Changed 10 years ago by
- Cc sstarosta added
comment:3 Changed 10 years ago by
- Description modified (diff)
comment:4 Changed 10 years ago by
Many tests currently break because of the following behavior
sage: int(2) in Integers() True sage: int(2) in PositiveIntegers() False
comment:5 Changed 10 years ago by
- Description modified (diff)
comment:6 Changed 10 years ago by
- Status changed from new to needs_review
comment:7 follow-up: ↓ 8 Changed 10 years ago by
Hey Vincent,
The patch needs rebasing to 5.5.rc0. Once you upload the rebase, I'll review the patch.
I think the only merged patch which might have caused the conflict is #13677.
Thanks,
Travis
comment:8 in reply to: ↑ 7 Changed 10 years ago by
Replying to tscrim:
Hey Vincent,
The patch needs rebasing to 5.5.rc0. Once you upload the rebase, I'll review the patch.
I think the only merged patch which might have caused the conflict is #13677.
Thanks,
Travis
Hi Travis,
I rebased the patch (together with Stepan Starosta) and actually we decided to simplify the FiniteEnumeratedSet? (the new version was slower). Everything should apply and work on 5.5.rc0.
Best, Vincent
comment:9 Changed 10 years ago by
- Reviewers set to Travis Scrimshaw
- Status changed from needs_review to needs_info
Hey Vincent and Stepan,
In build_alphabet
, the docstring states that this is an ordered alphabet. I get the following:
sage: A = Alphabet([1,3,7,2]) sage: A(3) < A(7) True sage: A(3) < A(2) False
I expected the last one to return True
since I expected these to be letters in A
and the comparison to take place in there (not default back to their natural ordering). I also get this:
sage: B = Alphabet(['a', 'b']) sage: B('a') --------------------------------------------------------------------------- TypeError Traceback (most recent call last) ... TypeError: Cannot convert str to sage.structure.element.Element
and both problems are because the alphabet does not have any element class. These problems were worse before this patch, but I was wondering if you wanted to take care of these here?
Words
still does proper comparison:
sage: W = Words(A); W Words over {1, 3, 7, 2} sage: W([2,1]) < W([2,2]) True sage: W([2,3]) < W([2,2]) True sage: W([2,2]) < W([2,7]) False
Additionally on is_endomorphism()
(line 1111 in morphism.py
), it was changed to test equality of the domain and codomain. What was the reasoning for this?
This applied cleanly for me on 5.5.rc0
, I'm curious as to why the patchbot defaulted back to 5.4.rc3
...
Thanks for you work on this,
Travis
comment:10 Changed 10 years ago by
- Dependencies set to #13801
comment:11 follow-up: ↓ 12 Changed 10 years ago by
- Status changed from needs_info to needs_review
Hi Travis,
thanks for reviewing the patch and your comments! I uploaded a new version with two major changes
- a new class TotallyOrderedFiniteSet?
- a dependency on #13801
All problems are similar to the ones there are currently with Nathann and posets (#13747) : to be or not to be a facade, that is the question. One major difference with the previous patch is that we provide a class TotallyOrderedFiniteSet? which has a facade option behavior and may choose the behavior you prefer.
How do facades behave
Facade are the default behavior for alphabets. The disadvantage of having a facade is that the elements need to have their order implemented, i.e., we get
sage: A = TotallyOrderedFiniteSet([0,2,1], facade=True) sage: A(2) < A(1) False
Another disadvantage of having a facade is that if some elements do not inherit from Element, the constructor raises an error
sage: B = TotallyOrderedFiniteSet(['a','b',3],facade=True) sage: B('a') Traceback (most recent call last): ... TypeError: Cannot convert str to sage.structure.element.Element
Not using facade ?
The possible workaround for the two above problems is to have a dedicated element class for TotallyOrderedFiniteSet?. If the option facade is set to False, it is what you get
sage: C = TotallyOrderedFiniteSet([1, 'a', -4], facade = False) sage: C(1) < C(-4) True sage: C('a') 'a'
... but
sage: 1 in C False sage: 1 == C(1) False sage: C(1) == 1 True
Partial conclusion
we do prefer having facade = True as a default behavior (as Nathann does).
About endomorphisms
Two reason to change is_endomorphism() are:
1) the operator <= is not defined on sets 2) the test was mathematically inaccurate : an endomorphism is a morphism for which domain = codomain (and not just a subset of codomain)
Thanks, Stepan and Vincent
comment:12 in reply to: ↑ 11 Changed 10 years ago by
Replying to vdelecroix:
Another disadvantage of having a facade is that if some elements do not inherit from Element, the constructor raises an error
sage: B = TotallyOrderedFiniteSet(['a','b',3],facade=True) sage: B('a') Traceback (most recent call last): ... TypeError: Cannot convert str to sage.structure.element.Element
Yeah, we hit the same problem in Poset, and we worked around it by having a custom call function. At some point, we should really fix it once for all in Parent.call.
Cheers,
Nicolas
comment:13 follow-up: ↓ 14 Changed 10 years ago by
Hey Stepan and Vincent,
Few more things:
- I get the same doctest failures as the patchbot; you just need to change the tests' output in
finite_word.py
.
- Would it be possible to just have
Alphabet()
(thus removing/renaming thebuild_alphabet()
)?
- Could you issue a deprecation warning for
OrderedAlphabet
?
- The
__new__()
function forOrderedAlphabet
needs a doctest.
- I would recommend for the documentation of
OrderedAlphabet_backward_compatibility
:Versions prior to :trac:`8920` uses the ``Alphabet`` classes with an argument ``._alphabet()`` instead of ``._elements()`` used in :class:`TotallyOrderedFiniteSet`. This class is dedicated to handling this problem which occurs when unpickling :class:`OrderedAlphabet`.
- The operator
<=
forAlphabet
andWords
did not behave as I expected:# Before sage: Alphabet('abc') <= Alphabet('12') False sage: Alphabet('abc') >= Alphabet('12') False sage: Alphabet('abcdef') <= Alphabet('12') False sage: Words('a') <= Words('123') False sage: Words('abcdef') <= Words('123') False sage: Words('abcdef') >= Words('123') False # With the patch sage: Alphabet('abc') <= Alphabet('12') True sage: Alphabet('abc') >= Alphabet('12') False sage: Alphabet('abcdef') <= Alphabet('12') True sage: Words('a') <= Words('123') True sage: Words('abcdef') <= Words('123') False sage: Words('abcdef') >= Words('123') True
- I'm still uncomfortable with the change to
is_endomorphism()
since I would (naively) expect the mapa->a, b->aa, c->aaa
be an endomorphism. The problem is word morphism automatically sets the codomain based on the image. As for the mathematics, yes, if it is a proper subset, it is not an endomorphism, but it naturally extends to one. I believe that having anything that is naturally extendable to an endomorphism should be considered an endomorphism by sage via the coercion model. Also in case you're worried, the above morphism worked with composition.
If a third party agrees with the changes in the patch, then I would add a warning to
is_endomorphism()
and/or toWordMorphism
about defining endomorphisms and add the testssage: w = WordMorphism('a->a,b->aa,c->aaa', codomain=Words('abc')) sage: w.is_endomorphism() True sage: w2 = WordMorphism('a->a,b->aa,c->aaa') sage: w == w2 FalseHowever there is one problem with this, and that is
w == w2
returnsTrue
. Thus the equality operator will need to be changed to reflect the dependency on the codomain.
Thank you,
Travis
comment:14 in reply to: ↑ 13 Changed 10 years ago by
Hey Stepan and Vincent,
Replying to tscrim:
- I'm still uncomfortable with the change to
is_endomorphism()
since I would (naively) expect the mapa->a, b->aa, c->aaa
be an endomorphism. The problem is word morphism automatically sets the codomain based on the image. As for the mathematics, yes, if it is a proper subset, it is not an endomorphism, but it naturally extends to one. I believe that having anything that is naturally extendable to an endomorphism should be considered an endomorphism by sage via the coercion model. Also in case you're worried, the above morphism worked with composition.If a third party agrees with the changes in the patch, then I would add a warning to
is_endomorphism()
and/or toWordMorphism
about defining endomorphisms and add the testssage: w = WordMorphism('a->a,b->aa,c->aaa', codomain=Words('abc')) sage: w.is_endomorphism() True sage: w2 = WordMorphism('a->a,b->aa,c->aaa') sage: w == w2 FalseHowever there is one problem with this, and that is
w == w2
returnsTrue
. Thus the equality operator will need to be changed to reflect the dependency on the codomain.
I talked with Nicolas about this, and he agreed with the changes in your patch, but also said we needed to change the ==
operator to check the codomain (in particular, we don't want a map f
to be surjective and g
to not be and compare equal because g
has a larger codomain). This might be a more general problem, and I'll take a look at it today and let you know what I find.
Best,
Travis
comment:15 Changed 9 years ago by
I've attached my review patch which address my comments and the doctests. The set comparisons in 14 are a more general issue for another ticket. If you agree with my changes, you can set this to positive review.
Best,
Travis
comment:16 follow-up: ↓ 17 Changed 9 years ago by
- Description modified (diff)
comment:17 in reply to: ↑ 16 Changed 9 years ago by
I modified the comparison of elements of TotallyOrderedFiniteSet
to make it more coherent.
comment:18 Changed 9 years ago by
I added link in the documentation and double quotes where it is needed.
comment:19 Changed 9 years ago by
- Keywords days45 added
- Status changed from needs_review to positive_review
Looks good to me now. Thank you.
Travis
comment:20 Changed 9 years ago by
- Milestone changed from sage-5.7 to sage-5.8
comment:21 Changed 9 years ago by
- Dependencies changed from #13801 to #13801, #6495
- Status changed from positive_review to needs_work
This needs to be rebased to #6495 and also this fuzz needs to be fixed:
applying /release/merger/patches/trac_8920-alphabet.patch unable to find 'doc/en/reference/structure.rst' for patching 1 out of 1 hunks FAILED -- saving rejects to file doc/en/reference/structure.rst.rej patching file sage/combinat/words/morphism.py Hunk #1 succeeded at 12 with fuzz 2 (offset 0 lines).
comment:22 Changed 9 years ago by
I rebased the patch for #6495.
Vincnet
comment:23 Changed 9 years ago by
- Status changed from needs_work to positive_review
comment:24 Changed 9 years ago by
On OS X:
sage -t --long -force_lib devel/sage/sage/sets/totally_ordered_finite_set.py ********************************************************************** File "/Users/dehayebuildbot/build/sage/dehaye/dehaye_full/build/sage-5.8.beta1/devel/sage-main/sage/sets/totally_ordered_finite_set.py", line 207: sage: A(1) < 1 Expected: True Got: False **********************************************************************
comment:25 Changed 9 years ago by
On arando
(Ubuntu 12.04 Linux i686 32-bit):
sage -t --long -force_lib devel/sage/sage/combinat/words/words.py ********************************************************************** File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.8.beta1/devel/sage-main/sage/combinat/words/words.py", line 851: sage: Words('ab') >= Words('abc') Expected: False Got: True ********************************************************************** File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.8.beta1/devel/sage-main/sage/combinat/words/words.py", line 853: sage: Words('abc') >= Words('ab') Expected: True Got: False **********************************************************************
comment:26 Changed 9 years ago by
- Status changed from positive_review to needs_work
comment:27 Changed 9 years ago by
I do not understand the first failure on OS X but I made a small modification in TotallyOrderedFiniteSet.__cmp__
and made more careful testing.
For the issue about comparisons of "Words", I just removed all related methods as they were needed nowhere and rely on comparison of alphabets which is not possible anymore.
Vincent
comment:28 Changed 9 years ago by
- Status changed from needs_work to needs_review
comment:29 Changed 9 years ago by
- Status changed from needs_review to positive_review
The long tests pass for me now. I'll try harder to remember to (re)run the long tests in the future.
comment:30 Changed 9 years ago by
- Merged in set to sage-5.8.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
comment:31 Changed 9 years ago by
Advice for the future: don't make needless whitespace changes, like you did here in morphism.py
. This causes a conflict with #12230 for no good reason.
Hi Vincent,
You are currently taking car of this. You may want either to reuse this ticket or to close it as duplicate.
Florent