[Python-ideas] Support multiplication for sets

[Terry Reedy]

On 10/7/2011 7:20 AM, Paul Moore wrote:
> On 7 October 2011 11:37, Jakob Bowyer<jkbbwr-Re5JQEeQqe8AvxtiuMwx3w at public.gmane.org>  wrote:
>> There is that but from a math point of view the syntax a * b does make
>> sence.
>> Its slightly clearer and makes more sense to people from outside of a
>> programming background.

Math used a different symbol, an 'X' without serifs, for cross-products. 
The result is a set of 'ordered pairs', which is different from a duple.

> I'm not sure I'd agree, even though I come from a maths background.
> Explicit is better than implicit and all that...
>
> Even if it is slightly clearer to some people, I bet there are others
> (not from a mathematical background) who would be confused by it. And
> in that case, itertools.product is easier to google for than "*"...)
> And that's ignoring the cost of implementing, testing, documenting the
> change.
>
> Actually, just to give a flavour of the sorts of design decisions that
> would need to be considered, consider this:
>
>>>> a = set((1,2))
>>>> b = set((3,4))
>>>> c = set((5,6))
>>>> from itertools import product
>>>> def times(s1,s2):
> ...    return set(product(s1,s2))
> ...
>>>> times(a,times(b,c))
> {(1, (3, 6)), (2, (3, 5)), (2, (4, 5)), (1, (4, 6)), (1, (4, 5)), (2,
> (3, 6)), (2, (4, 6)), (1, (3, 5))}
>>>> times(times(a,b),c)
> {((2, 4), 6), ((1, 4), 5), ((1, 4), 6), ((2, 3), 6), ((1, 3), 6), ((2,
> 3), 5), ((2, 4), 5), ((1, 3), 5)}
>>>>
>
> So your multiplication isn't commutative

It is not *associative* -- unless one special-cases tuples to add 
non-tuple elements to tuple elements.

> (the types of the elements in
> the 2 expressions above are different).

If the elements of A*B are sequences, then A*B is also not commutative. 
But it would be if the elements were sets instead of pairs.

> That doesn't seem intuitive -
> so maybe a*b*c should be a set of 3-tuples. But how would that work?

In math, *...* is a ternary operator with 3 args, like if...else in 
Python or ;...: in C, but it generalizes to an n-ary operator. From
https://secure.wikimedia.org/wikipedia/en/wiki/Cartesian_product
'''
The Cartesian product can be generalized to the n-ary Cartesian product 
over n sets X1, ..., Xn:

     X_1\times\cdots\times X_n = \{(x_1, \ldots, x_n) : x_i \in X_i \}.

It is a set of n-tuples. If tuples are defined as nested ordered pairs, 
it can be identified to (X1 × ... × Xn-1) × Xn.'''

In other words, think of aXbXc as XX(a,b,c) and similarly for more Xs. 
In Python, better to define XX explicitly. One can even write the n-fold 
generalization by simulating n nested for loops.

> The problem very quickly becomes a lot larger than you first assume.
>
> Operator overloading is used much more sparingly in Python than in,
> say, C++. It's as much a language style issue as anything else.
>
> Sorry, but I still don't see enough benefit to justify this.

In most situations, one really needs an iterator that produces the pairs 
one at a time rather than a complete collection. And when one does want 
a complete collection, one might often want it ordered as a list rather 
than unordered as a set. Itertools.product covers all these use cases. 
And even that does not cover the n-ary case.

For many combinatorial algorithms, one need a 'cross-concatenation' 
operator defined on collections of sequences which adds the pair of 
sequences in each cross-product pair. The same 'x' symbol, possibly 
circled, has been used for that. Both are in unicode, but Python is 
currently restricted to a sparse set of ascii symbols.

-- 
Terry Jan Reedy