Rotate error on childless binary trees

VivianePons commented 10 years ago

When one tries to apply a "right_rotate" (resp. "left_rotate") method on a binary tree which does not have a left (resp. right) subtree, one gets an "Index Error".

sage: bt = BinaryTree([])
sage: bt.right_rotate()
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
...
IndexError: list index out of range

This does not look like a neat error... The rotation is not defined in this case, so I'm not sure what the behavior should be:

1- return the same object

2- return None (seems like a bad idea)

3- raise a ValueError exception that says the rotation is not defined in this case

I would be up for 1 or 2 and I'm not sure which one is best, please tell me what you think!

CC: @fchapoton @darijgr @sagetrac-elixyre @tscrim

Component: combinatorics

Keywords: combinat, Tamari, binary trees, FindStat

Author: Viviane Pons

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

darijgr commented 10 years ago

comment:1

I'd suggest 2; why do you consider it a bad idea? I don't like throwing exceptions when the user is not at fault. I think 1 is too confusing.

Good catch; the two methods will be considerably more useful if they return reasonable data when the rotation cannot be performed.

VivianePons commented 10 years ago

comment:2

Well, it seems odd to me to return None on such an operation. The user expects a binary tree, I don't see why the result should be None, it might be confusing.

Maybe we should have a look on other combinatorial objects to see how this question is handled.

By the way, I didn't catch this error, FindStat did ;)

3f8450e1-87bf-41c6-ab53-29a0552debb3 commented 10 years ago

comment:3

Hi,

I think the first (return the same object) and the second (return None) solutions are not good ways.

To me, the method should raise an Exception: why not "NoRotationAvailable"? Or an (ugly) other solution the method *_rotate could be an iterator?

Cheers, Jean-Baptiste

stumpc5 commented 10 years ago

comment:4

What is wrong with returning the same object for the following reason:

The tree

    y
   / \
  x   C
 / \
A   B

is mapped to

    x
   / \
  A   y
     / \
    B   C

for nodes x and y and trees A,B,C. Now suppose that x doesn't exist and that A,B are empty. Then both pictures become

 y
  \
   C

This tree can thus be though of being fixed by the map.

VivianePons commented 10 years ago

comment:5

I'm also ok with returning the same object, I don't find it more confusing than returning None. The exception also makes sense, but as Darij said, it kinds of break something for no reason.

For example, in FindStat, we apply this rotation on all binary trees of size <=k. And of course, we can catch the exception, but it is just annoying that simply taking a big set and applying a method on all objects to see which new set we get breaks everything.

stumpc5 commented 10 years ago

Changed keywords from combinat, Tamari, binary trees to combinat, Tamari, binary trees, FindStat

darijgr commented 10 years ago

comment:7

Christian: the fact that you are sweeping under the rug is that the (non-existent) x becomes the root. I really don't like the idea of pretending that nothing's wrong and just returning the old tree. If it is implemented, how do we easily tell if something has been done to the tree? (I am not sure if we currently have a reasonable equality for trees -- something I should have fixed in #14498 but probably did not. Either way it wouldn't be the fastest way to do.)

stumpc5 commented 10 years ago

comment:8

Replying to @darijgr:

If it is implemented, how do we easily tell if something has been done to the tree?

Indeed, then the map would loose to be injective.

An alternative option would be to extend the domain and the codomain to all of the binary trees such that the map keeps being injective (and then a bijection on binary trees, not only a map from those having a left child bijectively onto those having a right child). To achieve this, one could possibly reflect the tree horizontally.

What do you think about that?

VivianePons commented 10 years ago

comment:9

I don't think it is a good idea. A rotation is really a rotation not a reflection!

stumpc5 commented 10 years ago

comment:10

Replying to @VivianePons:

I don't think it is a good idea. A rotation is really a rotation not a reflection!

I don't really have an opinion here -- instead of reflecting interchange the two subtrees, just do something that makes this map an operation on binary trees.

darijgr commented 10 years ago

comment:11

@Christian: That looks rather random...

Is the purpose here to make the method in Sage more useful or to make Findstat understand it as a combinatorial map? For the former purpose, I'd say either an exception or None is good, and I'm in favor of None because people think exceptions in Python aren't fast enough to be used on a regular basis ( http://paltman.com/2008/01/18/try-except-performance-in-python-a-simple-test/ ). For the latter purpose, I don't know what to do -- if FindStat is really tailored to complete maps (as it seems to me right now), then IMHO any kind of tweaks that forcibly make partial maps complete would only obscure the kind of patterns and identities that FindStat is attempting to find. I certainly don't want to replace the e_i crystal operator on tableaux by "e_i or Schuetzenberger involution if e_i cannot be applied" and likewise; I don't have any good reason to expect that these maps would behave nicely...

VivianePons commented 10 years ago

comment:12

Yeah, to be honest a rotate is not defined on every binary tree.

Even so, it still seems quite fair to me to define it as the identity on the elements where it's not defined. I don't see why it's a problem that it is not injective. It can say in the doc, that the rotation will be performed only if t[0] is not none.

I really don't like the return None', it just hides the problem. If you don't think of checking the result of your operation, it might raise other weird / non understandable errors later.

stumpc5 commented 10 years ago

comment:13

Replying to @darijgr:

IMHO any kind of tweaks that forcibly make partial maps complete would only obscure the kind of patterns and identities that FindStat is attempting to find.

findstat can only handle maps that are defined for all elements of a combinatorial collection and this makes sense -- but this should not be a topic here (whatever you guys gonna decide, we will have to look for a, possibly different, solution for findstat).

Nevertheless, there should be a description of the rotation map on other Catalan objects (through a bijection to binary trees), and a natural extension there should lead to an extension of the rotation map. Does such a description exist?

darijgr commented 10 years ago

comment:14

The problem with doing nothing is that it is expensive to check if the result is the result of a rotation or the result of doing nothing. If you add an additional variable that causes this behavior, OK, but I'd really not like seeing it as default behavior.

stumpc5 commented 10 years ago

comment:15

Replying to @stumpc5:

Nevertheless, there should be a description of the rotation map on other Catalan objects (through a bijection to binary trees), and a natural extension there should lead to an extension of the rotation map. Does such a description exist?

Considering planted trees (i.e., rooted trees for which the children come in a linear order) on n vertices, there is also a natural rotation. This rotation (1) corresponds to rotation of the corresponding complete matching of a regular (2n-2)-gon, and (2) it exhibits a cyclic sieving for the usual suspect polynomial (MacMahon's q-Catalans).

I feel like I have seen a bijection between binary trees and planted trees which send your rotation to the above rotation. Is that possible?

3f8450e1-87bf-41c6-ab53-29a0552debb3 commented 10 years ago

comment:16

Rotation on binary trees is an elementary transformation that should be coherent with the definition (the original one!!)

So that transformation is a partial map:

that return a new (different) binary tree
or that is not defined! -> raise an exception

If you are not agree with exception, the method could be an iterator. (My opinion (again) is that way is a wrong but I don't have any real argument...)

VivianePons commented 10 years ago

comment:17

Let me summarize here:

raising an exception is consistent mathematically but breaks everything unexpectedly. Let say you have a big set of objects on which you want to apply the rotation, you can't do it easily without checking every single element. Also, the try catch might be slow.
returning None does not break everything right away but it might lead to errors later that might be difficult to understand.
doing nothing is also problematic because you then don't know if your tree has been changed or not.
the iterator for something that returns at most one element seems somehow a bad idea (and is definitely not natural for a non advanced user)

I would really like to know if there are other combinatorial objects that have something like that and how it's dealt with. One possible solution proposed by Darij would be to have a default behavior and some kind of optional argument so that people can make it do what they want.

darijgr commented 10 years ago

comment:18

If we go down the exception route, I would advocate for a new exception called PartialMapException or likewise (unless we already have such a thing!) that is thrown whenever a combinatorial partial map is caught off its domain. That could then be used for other things like crystal operations on tableaux etc. -- rather than having each programmer decide on their favorite exception and then try to catch them as StandardErrors. Then, FindStat (or other code) could catch these PartialMapExceptions and take them as signs that nothing is wrong and there just is no image. Basically this means implementing the Maybe monad.

slel commented 2 years ago

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-When one tries to apply a "right_rotate" (resp. "left_rotate") method on a binary tree which does not have a left (resp. right) subtree, one gets a "Index Error".
+When one tries to apply a "right_rotate" (resp. "left_rotate") method on a binary tree which does not have a left (resp. right) subtree, one gets an "Index Error".

@@ -14,9 +14,9 @@

1- return the same object

-2- return None (seems like a bad idea) +2- return None (seems like a bad idea)

-3- raise a ValueError exception that says the rotation is not defined in this case +3- raise a ValueError exception that says the rotation is not defined in this case

I would be up for 1 or 2 and I'm not sure which one is best, please tell me what you think!

sagemath / sage

Rotate error on childless binary trees #16264