[Python-ideas] Support multiplication for sets

[Terry Reedy]

On 10/7/2011 8:57 PM, Terry Reedy wrote:
> On 10/7/2011 7:20 AM, Paul Moore wrote:
>> On 7 October 2011 11:37, Jakob
>> Bowyer<jkbbwr at gmail.com> 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.

And itertools.product already does this.

>> 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.

And itertools.product *does* cover the n-ary case. Sorry for the 
apparent error.

> 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