On Wed, Aug 4, 2010 at 5:51 PM, Nils Bruin <nbr...@sfu.ca> wrote:
> On Aug 4, 1:16 pm, Robert Miller <r...@rlmiller.org> wrote:
>> So you want Sage Sets to implement "a < b" to mean "a is a subset of
>> b"? I'll admit that that is reasonable, and it is a fact that it
>> follows Python convention.
>
> My initial reaction for this is affirmative: If python makes a choice,
> then sage must follow because it is a python library.
If Python jumped off a cliff...
> There are other areas of mathematics where "<" gets used for proper
> inclusion. A group theorist is going to be very surprised if for two
> groups H,G, the expression "H < G" is valid but does not mean "H is a
> subgroup of G".
But if you ask a good mathematician, given sets A and B, is A less
than B or is it true that A < B, they will ask, what do you mean by
"<"?
> In the category of sets (finite sets for that matter), I cannot think
> of a meaning for "<".
So then you would rather have Sage sets give an error rather than sort
in a list? I can't imagine why this is a good thing. You seem to be
ignoring the sorted() function altogether, rather than admitting it
can ever be useful.
> Indeed, and computer algebra systems (the good ones anyway) take great
> care in making the choice of monomial ordering explicit.
And we could also document our choices well.
>> For things like the adjacency matrix, having a
>> consistent if arbitrary total ordering of the vertices is important.
>
> But then an adjacency matrix is something that is defined for a graph
> *PLUS* an ordering of its vertices. A graph only has associated to it
> an "adjacency class", which is the conjugacy class of one of its
> adjacency matrices under permutation matrices, i.e.:
>
> { P.transpose()* adjacency_matrix * P : P in permutation matrices of
> the right size }
I think that this is entirely too pedantic for the problem at hand. I
would like to pick an arbitrary, consistent ordering and stick with
it, to make the user's life easier, and the developer's.
> Python 3 is clear on the matter: If there is not a natural ordering,
> then __lt__() is going to return a type error. In addition, for sets
> "<" is commandeered for a partial ordering, so routines that assume
> that __lt__() is consistent with a total ordering are going to return
> undefined results, and this is documented. I for one would not expect
> "sorted" to work on arbitrary iterables, so I'd be happy with an error
> and disappointed with an undefined result, until I read the relevant
> documentation.
I think this renders the sort function pretty useless. You can't even
sort a list of objects with the same type. I would much rather have a
Sage which sorts lists of things gladly than errors all over itself
all the time.
>> I love this kind of stuff
> [sorted([frozenset,....]) examples]
> this is documented to be undefined.
I know! You've made your point... The fact is that Python is still
ordering the elements of a set which are sets. The "sorted( set(...)
)" examples are not documented to be undefined, and they work.
>> So, given that we want to have graphs whose vertex sets are sets, or
>> subspaces, what is to be done?
>
> Don't rely on sorting, but use other methods for getting consistent
> orderings and efficient membership tests.
Such as?
>> Also, consider the fact that many Sage functions use "return
>> sorted(output)" to guarantee a consistent ordering of the output. What
>> you're advocating means that this wouldn't work in many cases...
>
> Yes. Personally, I would be in favour of actively randomizing the
> order in which results are returned whenever the results are not
> supposed to be returned in any particular order. So many subtle bugs
> creep into code due to people assuming results are returned in some
> particular order and then in some future edition of the code, this
> order is changed and the code unexpectedly breaks.
I think consistent ordering of outputs is not too much to expect,
*especially* within one run of Sage.
> I understand that consistent string representation of output is
> necessary for doctesting, but then you can just do a sort in the
> doctest, in the spirit of:
>
> sage: f = PolynomialRing(ComplexNumbers(100),"x").random_polynomial()
> sage: L = f.roots()
> sage: sorted(L, key = lambda v: [v[0].abs(),v[0].arg()])
It is very difficult to define such a sort (which is consistent) on
arbitrary objects coming in without becoming *very* inefficient. I'm
not trying to demand that all Sage objects always define a total
ordering, I'm just suggesting that since there is an inconsistent
definition of < for Sage sets, and since they get used frequently as
vertices, that we define a total ordering. You yourself admitted that
you can't think of a natural mathematical meaning for < for arbitrary
sets...
> In short:
> - I don't believe sorting is essential for programming many things
> efficiently
I hear that loud and clear. But that's no reason to make it impossible
to do so, in favor of a more difficult but also arbitrary decision.
> - I don't think routines should be going out of their way to sort
> their output
No routines? Ever? What if that's part of the design? Are you making a
broad, sweeping design decision about how everything should always be
done?
> - The reality is that Python will not support total ordering in many
> cases anymore.
That doesn't mean we can't. Sage sets aren't Python sets, and we don't
have to make the same mistakes. We can still be a Python library
without doing the same exact thing as Python all the time. By that
logic, we should delete the Sage Sets class entirely.
--
Robert L. Miller
http://www.rlmiller.org/
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
