Opened 7 years ago
Closed 6 years ago
#15456 closed defect (duplicate)
fix bug in has_right/left_descents in Weyl group code
Reported by:  zabrocki  Owned by:  

Priority:  major  Milestone:  sageduplicate/invalid/wontfix 
Component:  combinatorics  Keywords:  coxeter, sd65 
Cc:  sdenton, aschilling, nthiery, sagecombinat  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  Anne Schilling, Mike Zabrocki 
Report Upstream:  N/A  Work issues:  
Branch:  public/15456  Commit:  45ff0e370aea78c35197688d8983e9bfd1c00b51 
Dependencies:  Stopgaps: 
Description
The has_right_descents
method in WeylGroup
element methods calls has_left_descents
and vice versa. This causes an error in the following example.
sage: W = WeylGroup(['A',4]) sage: w = W.from_reduced_word([3,4,2]) sage: w.has_right_descent(3) Traceback (click to the left of this block for traceback) ... RuntimeError: maximum recursion depth exceeded
The doc tests for this method make calls to CoxeterGroup
code to test it and so all tests pass.
Change History (42)
comment:1 Changed 7 years ago by
comment:2 Changed 7 years ago by
Hi Nicolas,
This can't be a feature. In WeylGroup
this is a bug. In CoxeterGroup
it is correct.
In WeylGroups
the method has_right_descent
and has_left_descent
don't do anything except call each other.
comment:3 Changed 7 years ago by
BTW, in WeylGroup
the method has_descent
doesn't call either has_right_descent
or has_left_descent
and decides if there is a right/left descent by another method.
comment:4 Changed 7 years ago by
Right. The proper specification is:
 at least one of has_descent / has_right_descent / has_left_descent should be implemented
 in generic code, always use has_descent, not has_*_descent.
This definitely should be put in the doc if not yet there.
comment:5 Changed 7 years ago by
I take the part about it being correct in CoxeterGroup
back. It seems to only be correct for the CoxeterGroups().example()
.
I assume that you are right in that "Coxeter group category provides a default implementation for the other" but no one has implemented has_right_descent
or has_left_descent
for any of the finite or affine WeylGroups
or CoxeterGroups
(to an end user of these groups, this is a bug because it should just raise a Not Implemented
error).
Is the correct solution then that
(1) someone needs to implement them for each of the types
(2) that the default implementation should be has_left_descent
should call has_descent(self, side="left")
(3) the default implementation of has_right_descent
should raise a Not Implemented
error
(4) something else?
comment:6 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:7 Changed 7 years ago by
 Branch set to u/chapoton/15456
 Commit set to 549f238c87e446116457d645c2b0171b423c02df
 Status changed from new to needs_review
comment:8 Changed 7 years ago by
I think what we should do is have has_left_descent
call has_descent(self, side="right")
and has_right_descent
call has_descent(self, side="left")
.
comment:9 Changed 7 years ago by
8)
Indeed ? well, please do that if you think this is the thing to do.
comment:10 Changed 7 years ago by
tscrim: That's what WAS happening, but if you instantiate an abstract Weyl Group or Coxeter Group it leads to an infinite loop, which is a bug. What we need is a NotImplemented? error if neither side is implemented, and the appropriate call to the implemented 'side' if one side or the other is concretely implemented but not the other.
I see two possible ways forward: 1) The default Coxeter/Weyl? Group 'has_x_descent' methods just give a NotImplemented? error, pushing it to the person creating a concrete realization to actually implement them correctly and not give an infinite loop, or 2) Introduce some kind of '_is_implemented' flags for checking left and right descent, which are false by default, and set to true if there's a concrete implementation on one side that the other can use. Then if it's true, we call the other side, and otherwise raise a NotImplemented? error.
Option 2 seems doable but introduces an Obscure Thing for the implementers of Coxeter groups to keep track of. As such, I would advocate for Option 1.
comment:11 Changed 7 years ago by
It's also worth noting that sometimes one 'side' or the other is simply faster for computing descents. This is clearly true for simple permutations: one can check in constant time if there's a right descent, but it takes O(n) to check for a left descent. So then it would be bad news bears to have a default implementation of the right descent that calls the left decent.
But in other cases, it's maybe the left descent that's faster to compute, so you wouldn't want the reverse situation, either...
So I think I would advocate against breaking symmetry at the Category level, and just raise NotImplemented? errors for both sides.
comment:12 followup: ↓ 14 Changed 7 years ago by
I do not understand why my solution is not good enough. From my point of view, the function has_descent
in weyl_group.py
should rather be named has_right_descent
, because it is necessary to have at least one of the two (left or right) descent methods to avoid the infinite loop. I think that has_descent
should only be defined for abstract Coxeter groups.
comment:13 Changed 7 years ago by
Hey Tom,
If we made both left/right @abstract_method
's, then we would have to implement all methods. If we made them optional, I feel that we'd get bug reports about these not being implemented. The problem is that has_descent()
wasn't being brought into the loop, so if that was the only thing implemented, then one couldn't use has_left_descent()
as expects. Thus the spec:
 at least one of has_descent / has_right_descent / has_left_descent should be implemented
would be satisfied in my proposal.
Although I think we could do a modified version of your proposal 1) by implementing some kind of modification to @abstract_method
. Something like
@abstract_method(circular=['foo', 'bar'])
where if foo
and bar
were also called, then error out.
comment:14 in reply to: ↑ 12 Changed 7 years ago by
Replying to chapoton:
I do not understand why my solution is not good enough. From my point of view, the function
has_descent
inweyl_group.py
should rather be namedhas_right_descent
, because it is necessary to have at least one of the two (left or right) descent methods to avoid the infinite loop. I think thathas_descent
should only be defined for abstract Coxeter groups.
The has_descent()
in weyl_group.py
works for both sides, and by simply doing an alias, you're exposing invalid (at least 'should not be used') arguments in has_right_descent()
. In essence what you're doing is saying has_right_descent()
should call has_descent()
with the appropriate arguments. I'm saying let's do this in a generic fashion to follow the spec (I think comment:4 point 1 is in the doc already, but I haven't checked).
comment:15 Changed 7 years ago by
I couldn't find an indication that the documentation specifies that at least one of has_descent / has_right_descent / has_left_descent should be implemented.
Instead it seems to be that the default implementation of has_descent
calls has_left
orright_descent
Maybe we should throw checks in _test_has_descent
to ensure that all of the functions work.
comment:16 Changed 7 years ago by
 Commit changed from 549f238c87e446116457d645c2b0171b423c02df to d0bdccadb38c68a0019d2056daebfd601b8910cb
Branch pushed to git repo; I updated commit sha1. New commits:
d0bdcca  trac #15456 another try

comment:17 Changed 7 years ago by
Here is new (better) proposal:
The main idea is "please never override has_descent" and "please implement either has_left_descent or has_right_descent" in every instance (if only as a place holder raising NotImplementedError
).
In categories/coxeter_group
, there is only the mechanism:
 has_descent calls either has_left_descent or has right_descent
 they call each other
In instances of Coxeter group, one implements either has_left_descent or has_right_descent or both. Even in a minimalistic way, raising a NotImplementedError
.
What do you think ?
comment:18 Changed 7 years ago by
 Commit changed from d0bdccadb38c68a0019d2056daebfd601b8910cb to bef966f7e6f1ce42da5578c8da4df8d5ebdf9f9b
Branch pushed to git repo; I updated commit sha1. New commits:
bef966f  trac #15456 remove two unused lines

comment:19 Changed 7 years ago by
I think this is a good solution and probably what was intended to happen when the CoxeterGroup
code was originally written. Do others agree?
comment:20 Changed 7 years ago by
I don't like having the warning saying "don't override this", especially since I don't see a good reason for doing this (and there's no "final" semantic in python). I am in favor of saying we must implement either has_left_descent()
or has_right_descent()
. Also possibly implementing has_left/right_descent() for
weyl_group.py to call
has_descent()`.
Anyways, I've put my working version on trac at u/tscrim/15456
. I also gave default implementations of has_left/right_descent()
to weyl_group.py
for speed. Although now that I've done the implementation, I'm less convinced of my suggestion. Perhaps what would be best is some category magic. We test upon creation of a Coxeter group to see if any of the methods have been implemented. Thus we do the following:
 If
has_descent()
has been implemented, give defaulthas_*_descent()
callhas_descent()
with the appropriate args for those not implemented.  If none were implemented, error out on construction.
 Otherwise set it up as we have it now.
Maybe this is heavyhanded?
Nevertheless, here are some timings. I'm using the example from the ticket description. Baseline:
sage: %timeit w.has_descent(3, side="left") 1000 loops, best of 3: 860 us per loop sage: %timeit w.has_descent(3, side="left") 1000 loops, best of 3: 820 us per loop sage: %timeit w.has_descent(3, side="right") 1000 loops, best of 3: 200 us per loop sage: %timeit w.has_descent(3, side="right") 1000 loops, best of 3: 209 us per loop
With Frederic's branch:
sage: %timeit w.has_descent(3, side="left") 1000 loops, best of 3: 987 us per loop sage: %timeit w.has_left_descent(3) 1000 loops, best of 3: 929 us per loop sage: %timeit w.has_descent(3, side="right") 1000 loops, best of 3: 204 us per loop sage: %timeit w.has_right_descent(3) 1000 loops, best of 3: 215 us per loop
With my branch:
sage: %timeit w.has_descent(3, side="left") 1000 loops, best of 3: 867 us per loop sage: %timeit w.has_left_descent(3) 1000 loops, best of 3: 902 us per loop sage: %timeit w.has_descent(3, side="right") 1000 loops, best of 3: 200 us per loop sage: %timeit w.has_right_descent(3) 1000 loops, best of 3: 191 us per loop
comment:21 Changed 7 years ago by
So, what shall we do here ?
If I understand your proposal, when no has_something
is implemented in an instance of Coxeter group, one has two different possibilities of infinite loop instead of one.
Supose now that I only implement has_left
and that I call has_right
. This will result in an infinite loop in your proposal, no ?
comment:22 Changed 7 years ago by
Ah, I made a correction in my implementation has_right(i)
called (~self).has_descent(i, side='left')
.
I'm not so sure now what the best course of action is. From the above, having to create the inverse is slow (at least generically). I'm partially inclined to just implement has_left
and has_right
for Weyl groups which calls has_descent(i, side=*)
to fix the problem at present. In any of the solutions except my initial one, I would think the speed should roughly be the same...
comment:23 Changed 7 years ago by
 Keywords coxeter added
comment:24 Changed 7 years ago by
 Commit changed from bef966f7e6f1ce42da5578c8da4df8d5ebdf9f9b to c1deaa5708d0f9e08e02d24c8cb5a0a39328453b
Branch pushed to git repo; I updated commit sha1. New commits:
c1deaa5  Merge branch 'u/chapoton/15456' of ssh://trac.sagemath.org:22/sage into 15456

comment:25 followup: ↓ 33 Changed 7 years ago by
I am comfortable with accepting Frédéric's changes. From Nicolas' comments I think that the original implementation meant to have has_descent
should call either has_left
or has_right
and at least one of those needs to be implemented.
I checked that at least the _test_has_descent
will fail when one of these is not implemented by going into a Coxeter group implementation, deleting the has_right_descent
method, and then checking that G._test_has_descent()
raises an error. The problem is that all tests will pass in the implementation of a Coxeter group unless the _test_has_descent
method is called (which was probably always the case and the source of the original problem). Is there a way of ensuring that a test of the left and right functions will be made for future implementations? We can just leave it up to the warning which is already in the documentation.
comment:26 Changed 7 years ago by
 Commit changed from c1deaa5708d0f9e08e02d24c8cb5a0a39328453b to 5922bda3f092d44b86b3a32b34b1d0a64834713c
Branch pushed to git repo; I updated commit sha1. New commits:
5922bda  Merge branch 'u/chapoton/15456' of ssh://trac.sagemath.org:22/sage into 15456

comment:27 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:28 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:29 Changed 6 years ago by
 Milestone changed from sage6.4 to sage6.5
comment:30 Changed 6 years ago by
 Milestone changed from sage6.5 to sage6.7
comment:31 Changed 6 years ago by
 Milestone changed from sage6.7 to sage6.8
comment:32 Changed 6 years ago by
 Branch changed from u/chapoton/15456 to public/15456
 Commit changed from 5922bda3f092d44b86b3a32b34b1d0a64834713c to 45ff0e370aea78c35197688d8983e9bfd1c00b51
New commits:
45ff0e3  Merge branch 'develop' into u/chapoton/15456

comment:33 in reply to: ↑ 25 Changed 6 years ago by
Replying to zabrocki:
I am comfortable with accepting Frédéric's changes. From Nicolas' comments I think that the original implementation meant to have
has_descent
should call eitherhas_left
orhas_right
and at least one of those needs to be implemented.I checked that at least the
_test_has_descent
will fail when one of these is not implemented by going into a Coxeter group implementation, deleting thehas_right_descent
method, and then checking thatG._test_has_descent()
raises an error. The problem is that all tests will pass in the implementation of a Coxeter group unless the_test_has_descent
method is called (which was probably always the case and the source of the original problem). Is there a way of ensuring that a test of the left and right functions will be made for future implementations? We can just leave it up to the warning which is already in the documentation.
I am ok with Federic's solution. All tests pass, so I think this should go in.
comment:34 Changed 6 years ago by
 Reviewers set to Anne Schilling, Mike Zabrocki
 Status changed from needs_review to positive_review
Anne looked at the code as well. We both approve and I am setting to positive review.
comment:35 Changed 6 years ago by
This will conflict will #18610 and is probably a duplicate. The review is coming too late.
This need to be checked, nevertheless.
comment:36 Changed 6 years ago by
 Status changed from positive_review to needs_info
comment:37 Changed 6 years ago by
 Milestone changed from sage6.8 to sageduplicate/invalid/wontfix
comment:38 Changed 6 years ago by
 Keywords sd65 added
comment:39 followup: ↓ 40 Changed 6 years ago by
 Status changed from needs_info to positive_review
ok, let us consider that this has been solved by #18610
comment:40 in reply to: ↑ 39 Changed 6 years ago by
comment:41 Changed 6 years ago by
This is 'positive review as a duplicate', the usual standard procedure, so that it can be closed!
comment:42 Changed 6 years ago by
 Resolution set to duplicate
 Status changed from positive_review to closed
This is not a bug but a feature :)
When implementing a Coxeter group one can choose to either implement has_right_descent or has_left_descent (or both), and the Coxeter group category provides a default implementation for the other, if needed.
Granted, it would be nice if there was a nicer error message mentionning that at least one of has_left_descent or has_right_descent should be implemented. However, at this point, we have not generic infrastructure for this kind of situation, and it would be a bit tedious to do it by hand (but ideas on how to handle this are welcome!).
Cheers,