#18411: get rid of CartesianProduct
-------------------------+-------------------------------------------------
Reporter: | Owner:
vdelecroix | Status: needs_review
Type: | Milestone: sage-6.9
enhancement | Resolution:
Priority: major | Merged in:
Component: | Reviewers: Nicolas Thiéry
combinatorics | Work issues:
Keywords: | Commit:
Authors: | 22f8b77a3cc2223863396f8d422fbbeec51d1656
Vincent Delecroix | Stopgaps:
Report Upstream: N/A |
Branch: |
public/18411 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by nthiery):
Here is a trace of the non trivial points we discussed privately with
Vincent:
> >- enumerated_set_from_iterator: do we want instead to start filling
> >the cache in case it does not exist yet?
>
> Nope. The cache might be *never* used in that class. And when it exists
it
> is automatically filled since it is a lazy_list.
Oh, I had not noticed that, in EnumeratedSetFromIterator, the existence
of the cache was decided upon construction. +1 then.
>>>> - Why moving __iter__ from EnumeratedSets.CartesianProducts to
>>>> Sets.CartesianProducts?
>>>
>>> Because otherwise there are some failing doctests. For example
>>> Set([1,2,3])
>>> is iterable but the following was not
>>> cartesian_product([Set(1,2,3), Set([1,2,3])])
>>>
>>> The fact that something is iterable does not necessarily mean that it
>>> belongs to EnumeratedSet. At least for me and the current class
>>> FiniteEnumeratedSet, the enumerated set {1, 2, 3} is not equal to the
>>> enumerated set {3, 2, 1}. But they are equal as sets. And the set {1,
2, 3}
>>> should be iterable.
>>
>> I see your point. Yet this is annoying; where do we want to put the
>> exact limit between Set and EnumeratedSet? Where should, e.g. features
>> like cardinality_from_iterator live?
>>
>> Hmm, I am not sure what to do here.
>
>Right. My main motivation was to fix some doctests were previous code
>expected that the result was iterable. I do not exactly remind where it
was.
Would it make sense to put it in `Sets.Finite.CartesianProduct`, given
that it only works in the finite case?
>The iterator is mandatory for cardinality_from_iterator, as it is not
>for Sets I would not put there.
Yeah, that's a good point.
>> - Do we want to systematically use itertools.product when in some
>> cases it's memory complexity is not as good as what we can do when we
>> have iterables and not iterators as input?
>
>Clearly not. But we are lacking something better. Once the list is
>expanded, you can not beat itertools. So in most cases, it is what you
>want since the size of factors is small compared to the size of the
product.
>
>> - Sets 2034: is_empty: - don't catch all exceptions - is it about
>> parents not implementing is_empty, or about returning Unknown or
>> raising an exception? In which case we should specify that exception
>> and only catch that one.
>
>done
>
>> - CartesianProduct_iters: Make the difference with cartesian_product
>> more explicit and add a link?
>
>done
>
>> - Compositions: return FiniteEnumeratedSet([self])
>
>done
>
>> or make cartesian_product() return FiniteEnumeratedSet([xxx]) or
>> Set([xxx]) where xxx is the trivial tuple.
>
>This is not a good idea. The interface should be uniform when you do
>elt[i] to access the i-th cartesian projection.
>
>> - partition_tuple: could there not be other combinations, like (())?
>
>I did not found any. The empty tuple comes from the iteration with
product.
>
>> - root_lattice_realization: is the conversion to FiniteEnumeratedSet
>> still necessary?
>>
>> C = cartesian_product([PositiveIntegers(),
>> FiniteEnumeratedSet(Q.roots())])
>>
>> If so, should instead cartesian_product do more input tidying work?
>
>Indeed, it is not. done.
>
> >- sets.family: maybe that test was about checking that things work
> >when a parent C is just in EnumeratedSets but C.cardinality() ==
> >infinity
>
> I reintroduced the test using cartesian_product instead of
CartesianProduct
>
>> ... about `cartesian_product()` ...
>>
>> So what about returning:
>>
>> sage: from sage.sets.cartesian_product import CartesianProduct
>> sage: CartesianProduct((), Sets().CartesianProducts())
>> The cartesian product of ()
>>
>> I vaguely remember we discussed this at some point, but don't remember
>> what the outcome was. Of course if the user did not specify a category
>> to cartesian_product(), we don't quite know what's the category he
>> expects, but Sets().CartesianProducts() sounds like a reasonable
>> starting point.
>
>I also remember that we discussed it. And indeed, for the sake of
>backward compatibility it needs to be done in that ticket... we had
>
>sage: CartesianProduct()
>Cartesian product of
>sage: CartesianProduct().cardinality()
>1
>sage: CartesianProduct().an_element()
>[]
>
>There is an other commit for that.
Thanks!
I made some minor review changes. Since the spacing commit for the
tutorial was going the wrong way w.r.t. Python's convention, I allowed
myself to revert it, and actually fix accordingly the surrounding
lines (which I had written incorrectly a couple years ago). I hope
that's ok.
Up to the final position of the `__iter__` method which I am not yet
quite comfortable with, I am happy with the current state.
Anyone a point of view on this final sticking point?
Cheers,
Nicolas
--
Ticket URL: <http://trac.sagemath.org/ticket/18411#comment:38>
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.
