#15862: Mutability of tableaux, for the n-th time
-------------------------------------+-------------------------------------
Reporter: darij | Owner:
Type: defect | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: combinatorics | Resolution:
Keywords: tableaux, sage- | Merged in:
combinat, mutability, days64 | Reviewers:
Authors: Josh Swanson, Jan | Work issues:
Keitel, Darij Grinberg | Commit:
Report Upstream: N/A | 430003da7a7b6d3afc60e385f3d6e812b3864f25
Branch: public/15862 | Stopgaps: #17997
Dependencies: |
-------------------------------------+-------------------------------------
Description changed by darij:
Old description:
> Tableaux in Sage are mutable objects, at least indirectly:
> {{{
> sage: T = Tableau([[1,2],[2]])
> sage: t0 = T[0]
> sage: t0[1] = 3
> sage: T
> [[1, 3], [2]]
> }}}
> This in itself is probably not a bug, although not the kind of behavior I
> like either (what exactly is sped up by mutability of tableaux?). But
> there are things which probably are bugs given this behavior:
>
> 1. Tableaux are hashed by reference:
> {{{
> sage: T = Tableau([[1,2],[2]])
> sage: hash(T)
> -7723024261707595164
> sage: T[0][1] = 4
> sage: hash(T)
> -7723024261707595164
> }}}
>
> 2. Line 311 of `sage/combinat/tableau.py` says:
> {{{
> # Since we are (suppose to be) immutable, we can share the
> underlying data
> }}}
> But we are not immutable. This comment line is supposed to provide
> justification for initializing the tableau as a `CombinatorialObject`,
> but the docstring of `CombinatorialObject` says that
> "CombinatorialObjects are shallowly immutable, and the intention is that
> they are semantically immutable". The latter is not satisfied for
> tableaux.
>
> If we want tableaux to be mutable, why wrap them inside such a class? If
> we want them to be immutable, wouldn't it be right to encode them as
> CombinatorialObjects of CombinatorialObjects? Or is the speed cost for
> this too steep? And, finally, what is it that CombinatorialObject does
> that tuple does not?
>
> And, on a related note, does Sage provide a class for immutable
> dictionaries? (I'm still hell-bent on implementing arbitrary-shaped
> tableaux.)
>
> 3. Mutating tableaux poisons type judgments (or what passes for type
> judgments in Sage):
> {{{
> sage: T = StandardTableau([[1,2],[3]])
> sage: T[0][1] = 5
> sage: isinstance(T, StandardTableau)
> True
> }}}
>
> 4. There is some action at a distance (although fortunately rare):
> {{{
> sage: T = SkewTableau([[1,2],[3]])
> sage: S = T.to_tableau() # Tableau(S) doesn't work, wondering if it
> should?
> sage: S
> [[1, 2], [3]]
> sage: T
> [[1, 2], [3]]
> sage: T[0][1] = 5
> sage: S
> [[1, 5], [3]]
> sage: T
> [[1, 5], [3]]
> }}}
>
> 5. How would I define Loday's Hopf algebra of tableaux if tableaux are
> mutable?
New description:
Tableaux in Sage used to be implemented as lists of lists. The outer list
was wrapped in a `CombinatorialObject`, which made it immutable (at least
without accessing underscored attributes). The inner lists, however, could
be easily mutated; for example:
{{{
sage: T = Tableau([[1,2],[2]])
sage: t0 = T[0]
sage: t0[1] = 3
sage: T
[[1, 3], [2]]
}}}
This kind of mutability was likely not intended. I, personally, have only
ever triggered it by accident.
The present branch replaces the inner lists in the implementation of
tableaux and skew tableaux by tuples. As a consequence, tableaux become
completely (rather than just shallowly) immutable (unless their entries
themselves are mutable, which can be blamed on the user). They are still
printed as lists of lists, but this is just a `_repr_` issue.
The branch also makes some optimizations and corrections.
------------------------
Old description:
Tableaux in Sage are mutable objects, at least indirectly:
{{{
sage: T = Tableau([[1,2],[2]])
sage: t0 = T[0]
sage: t0[1] = 3
sage: T
[[1, 3], [2]]
}}}
This in itself is probably not a bug, although not the kind of behavior I
like either (what exactly is sped up by mutability of tableaux?). But
there are things which probably are bugs given this behavior:
1. Tableaux are hashed by reference:
{{{
sage: T = Tableau([[1,2],[2]])
sage: hash(T)
-7723024261707595164
sage: T[0][1] = 4
sage: hash(T)
-7723024261707595164
}}}
2. Line 311 of `sage/combinat/tableau.py` says:
{{{
# Since we are (suppose to be) immutable, we can share the
underlying data
}}}
But we are not immutable. This comment line is supposed to provide
justification for initializing the tableau as a `CombinatorialObject`, but
the docstring of `CombinatorialObject` says that "CombinatorialObjects are
shallowly immutable, and the intention is that they are semantically
immutable". The latter is not satisfied for tableaux.
If we want tableaux to be mutable, why wrap them inside such a class? If
we want them to be immutable, wouldn't it be right to encode them as
CombinatorialObjects of CombinatorialObjects? Or is the speed cost for
this too steep? And, finally, what is it that CombinatorialObject does
that tuple does not?
And, on a related note, does Sage provide a class for immutable
dictionaries? (I'm still hell-bent on implementing arbitrary-shaped
tableaux.)
3. Mutating tableaux poisons type judgments (or what passes for type
judgments in Sage):
{{{
sage: T = StandardTableau([[1,2],[3]])
sage: T[0][1] = 5
sage: isinstance(T, StandardTableau)
True
}}}
4. There is some action at a distance (although fortunately rare):
{{{
sage: T = SkewTableau([[1,2],[3]])
sage: S = T.to_tableau() # Tableau(S) doesn't work, wondering if it
should?
sage: S
[[1, 2], [3]]
sage: T
[[1, 2], [3]]
sage: T[0][1] = 5
sage: S
[[1, 5], [3]]
sage: T
[[1, 5], [3]]
}}}
5. How would I define Loday's Hopf algebra of tableaux if tableaux are
mutable?
--
--
Ticket URL: <http://trac.sagemath.org/ticket/15862#comment:45>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
