Opened 12 years ago

Closed 9 years ago

Last modified 6 years ago

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

Status badges

Description (last modified by vdelecroix)

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)

trac_8920-alphabet.patch (144.9 KB) - added by vdelecroix 9 years ago.
apply only this one (takes care of changes in the review patch)

Download all attachments as: .zip

Change History (33)

comment:1 Changed 11 years ago by hivert

  • Cc vdelecroix added
  • Keywords Cernay2012 added

Hi Vincent,

You are currently taking car of this. You may want either to reuse this ticket or to close it as duplicate.

Florent

comment:2 Changed 10 years ago by sstarosta

  • Cc sstarosta added

comment:3 Changed 10 years ago by vdelecroix

  • Description modified (diff)

comment:4 Changed 10 years ago by vdelecroix

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 vdelecroix

  • Description modified (diff)

comment:6 Changed 10 years ago by vdelecroix

  • Status changed from new to needs_review

comment:7 follow-up: Changed 10 years ago by 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

comment:8 in reply to: ↑ 7 Changed 10 years ago by vdelecroix

  • Authors set to Vincent Delecroix, Stepan Starosta

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 tscrim

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

  • Dependencies set to #13801

comment:11 follow-up: Changed 10 years ago by vdelecroix

  • 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

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 nthiery

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: Changed 10 years ago by tscrim

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 the build_alphabet())?
  • Could you issue a deprecation warning for OrderedAlphabet?
  • The __new__() function for OrderedAlphabet 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 <= for Alphabet and Words 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 map a->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 to WordMorphism about defining endomorphisms and add the tests

sage: 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
False

However there is one problem with this, and that is w == w2 returns True. 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 tscrim

Hey Stepan and Vincent,

Replying to tscrim:

  • I'm still uncomfortable with the change to is_endomorphism() since I would (naively) expect the map a->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 to WordMorphism about defining endomorphisms and add the tests

sage: 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
False

However there is one problem with this, and that is w == w2 returns True. 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 tscrim

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: Changed 9 years ago by vdelecroix

  • Description modified (diff)

comment:17 in reply to: ↑ 16 Changed 9 years ago by vdelecroix

I modified the comparison of elements of TotallyOrderedFiniteSet to make it more coherent.

comment:18 Changed 9 years ago by vdelecroix

I added link in the documentation and double quotes where it is needed.

comment:19 Changed 9 years ago by tscrim

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

  • Milestone changed from sage-5.7 to sage-5.8

comment:21 Changed 9 years ago by jdemeyer

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

I rebased the patch for #6495.

Vincnet

comment:23 Changed 9 years ago by tscrim

  • Status changed from needs_work to positive_review

comment:24 Changed 9 years ago by jdemeyer

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
**********************************************************************
Last edited 9 years ago by jdemeyer (previous) (diff)

comment:25 Changed 9 years ago by jdemeyer

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 jdemeyer

  • Status changed from positive_review to needs_work

Changed 9 years ago by vdelecroix

apply only this one (takes care of changes in the review patch)

comment:27 Changed 9 years ago by vdelecroix

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

Last edited 9 years ago by vdelecroix (previous) (diff)

comment:28 Changed 9 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:29 Changed 9 years ago by tscrim

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

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

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.

comment:32 Changed 6 years ago by chapoton

  • Authors changed from Vincent Delecroix, Stepan Starosta to Vincent Delecroix, Štěpán Starosta
Note: See TracTickets for help on using tickets.