Repository: sympy/sympy

Issue:
Set iteration can return booleans
For example 

```py
>>> list(Intersection(FiniteSet(x), FiniteSet(y)))
[Contains(x, {y}), Contains(y, {x})]
>>> list(Intersection(FiniteSet(x), Reals))
[(x > -oo) & (x < oo)]
```

The problem here is that `Contains` and `And` are booleans, so they aren't actually elements of the set (the elements of the set are numbers, not booleans). 

See also https://github.com/sympy/sympy/pull/10249.

I would suggest raising a TypeError in this case. That would match the behavior of `in` (`__contains__`) and `bool` on relationals (like `bool(x < y)`).

I initially had a commit to do this at https://github.com/sympy/sympy/pull/16344/commits/ff65f86f9da9d848805d944c6d02f9d41c791ace, but it leads to some test failures in the integration tests, because `_eval_interval` iterates over the singularities, which are from solveset.

I think we need a way to iterate over elements that isn't strict (but doesn't return booleans, that is just mathematically wrong), and a way that is. I'm not sure which should be the default for `__iter__`. 

Also one comment on the above commit, it should be TypeError, not ValueError, to match `Set.__contains__` and `Relational.__bool__`.

Discussion:
sympy-bot: :white_check_mark:

Hi, I am the [SymPy bot](https://github.com/sympy/sympy-bot) (v148). I'm here to help you write a release notes entry. Please read the [guide on how to write release notes](https://github.com/sympy/sympy/wiki/Writing-Release-Notes).



Your release notes are in good order.

Here is what the release notes will look like:
* sets
  - Implemented iteration methods for `Complement`, `SymmetricDifference`, `` ([#17584](https://github.com/sympy/sympy/pull/17584) by [@sylee957](https://github.com/sylee957))

This will be added to https://github.com/sympy/sympy/wiki/Release-Notes-for-1.5.

Note: This comment will be updated with the latest check if you edit the pull request. You need to reload the page to see it. <details><summary>Click here to see the pull request description that was parsed.</summary>

    <!-- Your title above should be a short description of what
    was changed. Do not include the issue number in the title. -->

    #### References to other Issues or PRs
    <!-- If this pull request fixes an issue, write "Fixes #NNNN" in that exact
    format, e.g. "Fixes #1234". See
    https://github.com/blog/1506-closing-issues-via-pull-requests . Please also
    write a comment on that issue linking back to this pull request once it is
    open. -->


    #### Brief description of what is fixed or changed

    Unevaluated `Complement`, `SymmetricDifference` sets hadn't implemented any iteration method, and it gives error for
    ```python
    FiniteSet(
        *Complement(
            FiniteSet(1, 2, 3), 
            FiniteSet(0, 1),
            evaluate=False)
    )
    ```
    But I think that some cases can easily be determined to be finite or iterable, and it would be possible to add another way to access elements via sampling.

    #### Other comments

    I've also moved `roundrobin` to utilities.

    The only remaining case would be `ConditionSet`, but I have not done the work here because I think that the class needs some redesigns to handle the `evaluate` keyword to properly test iterations over unevaluated ConditionSet.

    #### Release Notes

    <!-- Write the release notes for this release below. See
    https://github.com/sympy/sympy/wiki/Writing-Release-Notes for more information
    on how to write release notes. The bot will check your release notes
    automatically to see if they are formatted correctly. -->

    <!-- BEGIN RELEASE NOTES -->
    - sets
      - Implemented iteration methods for `Complement`, `SymmetricDifference`, ``
    <!-- END RELEASE NOTES -->


</details><p>

oscarbenjamin: The doctest needs fixing but otherwise this looks good. This can also close #16362
sylee957: I’m thinking of documenting about how the iteration for sympy sets are handled, since things had become different for the python sets, or the previous implementation where more things were considered distinct without mathematical context.
So I need some more time.
codecov[bot]: # [Codecov](https://codecov.io/gh/sympy/sympy/pull/17584?src=pr&el=h1) Report
> Merging [#17584](https://codecov.io/gh/sympy/sympy/pull/17584?src=pr&el=desc) into [master](https://codecov.io/gh/sympy/sympy/commit/982efb5bf6d6529643a58056023606f091cee696?src=pr&el=desc) will **decrease** coverage by `7.783%`.
> The diff coverage is `90.909%`.

```diff
@@              Coverage Diff              @@
##            master    #17584       +/-   ##
=============================================
- Coverage   74.799%   67.016%   -7.784%     
=============================================
  Files          633       633               
  Lines       164836    164856       +20     
  Branches     38750     38757        +7     
=============================================
- Hits        123296    110480    -12816     
- Misses       36128     48928    +12800     
- Partials      5412      5448       +36
```


Patch:
diff --git a/doc/src/modules/sets.rst b/doc/src/modules/sets.rst
index d70a87beaa..35a8a8910e 100644
--- a/doc/src/modules/sets.rst
+++ b/doc/src/modules/sets.rst
@@ -94,3 +94,27 @@ ComplexRegion
    :members:
 
 .. autofunction:: normalize_theta_set
+
+Iteration over sets
+^^^^^^^^^^^^^^^^^^^
+
+For set unions, `\{a, b\} \cup \{x, y\}` can be treated as
+`\{a, b, x, y\}` for iteration regardless of the distinctiveness of
+the elements, however, for set intersections, assuming that
+`\{a, b\} \cap \{x, y\}` is `\varnothing` or `\{a, b \}` would not
+always be valid, since some of `a`, `b`, `x` or `y` may or may not be
+the elements of the intersection.
+
+Iterating over the elements of a set involving intersection, complement,
+or symmetric difference yields (possibly duplicate) elements of the set
+provided that all elements are known to be the elements of the set.
+If any element cannot be determined to be a member of a set then the
+iteration gives ``TypeError``.
+This happens in the same cases where ``x in y`` would give an error.
+
+There are some reasons to implement like this, even if it breaks the
+consistency with how the python set iterator works.
+We keep in mind that sympy set comprehension like ``FiniteSet(*s)`` from
+a existing sympy sets could be a common usage.
+And this approach would make ``FiniteSet(*s)`` to be consistent with any
+symbolic set processing methods like ``FiniteSet(*simplify(s))``.
diff --git a/sympy/sets/fancysets.py b/sympy/sets/fancysets.py
index 5c6986a756..07046ae2a9 100644
--- a/sympy/sets/fancysets.py
+++ b/sympy/sets/fancysets.py
@@ -496,7 +496,7 @@ class Range(Set):
         >>> next(iter(r))
         Traceback (most recent call last):
         ...
-        ValueError: Cannot iterate over Range with infinite start
+        TypeError: Cannot iterate over Range with infinite start
         >>> next(iter(r.reversed))
         0
 
@@ -652,7 +652,7 @@ def __iter__(self):
         if self.has(Symbol):
             _ = self.size  # validate
         if self.start in [S.NegativeInfinity, S.Infinity]:
-            raise ValueError("Cannot iterate over Range with infinite start")
+            raise TypeError("Cannot iterate over Range with infinite start")
         elif self:
             i = self.start
             step = self.step
diff --git a/sympy/sets/sets.py b/sympy/sets/sets.py
index db9b7f2d06..c86d8397d3 100644
--- a/sympy/sets/sets.py
+++ b/sympy/sets/sets.py
@@ -25,7 +25,7 @@
 from sympy.sets.contains import Contains
 from sympy.utilities import subsets
 from sympy.utilities.exceptions import SymPyDeprecationWarning
-from sympy.utilities.iterables import sift
+from sympy.utilities.iterables import sift, roundrobin
 from sympy.utilities.misc import func_name, filldedent
 
 from mpmath import mpi, mpf
@@ -785,10 +785,7 @@ def __iter__(self):
         If self.is_iterable returns True (both constituent sets are iterable),
         then return the Cartesian Product. Otherwise, raise TypeError.
         """
-        if self.is_iterable:
-            return product(*self.sets)
-        else:
-            raise TypeError("Not all constituent sets are iterable")
+        return product(*self.sets)
 
     @property
     def is_empty(self):
@@ -802,7 +799,7 @@ def _measure(self):
         return measure
 
     def __len__(self):
-        return Mul(*[len(s) for s in self.sets])
+        return reduce(lambda a, b: a*b, (len(s) for s in self.args))
 
     def __bool__(self):
         return all([bool(s) for s in self.sets])
@@ -1256,30 +1253,7 @@ def _eval_evalf(self, prec):
                    sys.exc_info()[2])
 
     def __iter__(self):
-        import itertools
-
-        # roundrobin recipe taken from itertools documentation:
-        # https://docs.python.org/2/library/itertools.html#recipes
-        def roundrobin(*iterables):
-            "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
-            # Recipe credited to George Sakkis
-            pending = len(iterables)
-            if PY3:
-                nexts = itertools.cycle(iter(it).__next__ for it in iterables)
-            else:
-                nexts = itertools.cycle(iter(it).next for it in iterables)
-            while pending:
-                try:
-                    for next in nexts:
-                        yield next()
-                except StopIteration:
-                    pending -= 1
-                    nexts = itertools.cycle(itertools.islice(nexts, pending))
-
-        if all(set.is_iterable for set in self.args):
-            return roundrobin(*(iter(arg) for arg in self.args))
-        else:
-            raise TypeError("Not all constituent sets are iterable")
+        return roundrobin(*(iter(arg) for arg in self.args))
 
 
 class Intersection(Set, LatticeOp):
@@ -1356,23 +1330,42 @@ def _contains(self, other):
         return And(*[set.contains(other) for set in self.args])
 
     def __iter__(self):
-        no_iter = True
-        for s in self.args:
-            if s.is_iterable:
-                no_iter = False
-                other_sets = set(self.args) - set((s,))
-                other = Intersection(*other_sets, evaluate=False)
-                for x in s:
-                    c = sympify(other.contains(x))
-                    if c is S.true:
+        sets_sift = sift(self.args, lambda x: x.is_iterable)
+
+        completed = False
+        candidates = sets_sift[True] + sets_sift[None]
+
+        finite_candidates, others = [], []
+        for candidate in candidates:
+            length = None
+            try:
+                length = len(candidate)
+            except:
+                others.append(candidate)
+
+            if length is not None:
+                finite_candidates.append(candidate)
+        finite_candidates.sort(key=len)
+
+        for s in finite_candidates + others:
+            other_sets = set(self.args) - set((s,))
+            other = Intersection(*other_sets, evaluate=False)
+            completed = True
+            for x in s:
+                try:
+                    if x in other:
                         yield x
-                    elif c is S.false:
-                        pass
-                    else:
-                        yield c
+                except TypeError:
+                    completed = False
+            if completed:
+                return
 
-        if no_iter:
-            raise ValueError("None of the constituent sets are iterable")
+        if not completed:
+            if not candidates:
+                raise TypeError("None of the constituent sets are iterable")
+            raise TypeError(
+                "The computation had not completed because of the "
+                "undecidable set membership is found in every candidates.")
 
     @staticmethod
     def _handle_finite_sets(args):
@@ -1545,6 +1538,19 @@ def as_relational(self, symbol):
 
         return And(A_rel, B_rel)
 
+    @property
+    def is_iterable(self):
+        if self.args[0].is_iterable:
+            return True
+
+    def __iter__(self):
+        A, B = self.args
+        for a in A:
+            if a not in B:
+                    yield a
+            else:
+                continue
+
 
 class EmptySet(with_metaclass(Singleton, Set)):
     """
@@ -1899,6 +1905,25 @@ def as_relational(self, symbol):
 
         return Xor(A_rel, B_rel)
 
+    @property
+    def is_iterable(self):
+        if all(arg.is_iterable for arg in self.args):
+            return True
+
+    def __iter__(self):
+
+        args = self.args
+        union = roundrobin(*(iter(arg) for arg in args))
+
+        for item in union:
+            count = 0
+            for s in args:
+                if item in s:
+                    count += 1
+
+            if count % 2 == 1:
+                yield item
+
 
 def imageset(*args):
     r"""
diff --git a/sympy/utilities/iterables.py b/sympy/utilities/iterables.py
index 7756708b03..546eca0377 100644
--- a/sympy/utilities/iterables.py
+++ b/sympy/utilities/iterables.py
@@ -12,7 +12,8 @@
 
 # this is the logical location of these functions
 from sympy.core.compatibility import (
-    as_int, default_sort_key, is_sequence, iterable, ordered, range, string_types
+    as_int, default_sort_key, is_sequence, iterable, ordered, range,
+    string_types, PY3
 )
 
 from sympy.utilities.enumerative import (
@@ -2578,3 +2579,28 @@ def rotations(s, dir=1):
     for i in range(len(seq)):
         yield seq
         seq = rotate_left(seq, dir)
+
+
+def roundrobin(*iterables):
+    """roundrobin recipe taken from itertools documentation:
+    https://docs.python.org/2/library/itertools.html#recipes
+
+    roundrobin('ABC', 'D', 'EF') --> A D E B F C
+
+    Recipe credited to George Sakkis
+    """
+    import itertools
+
+    if PY3:
+        nexts = itertools.cycle(iter(it).__next__ for it in iterables)
+    else:
+        nexts = itertools.cycle(iter(it).next for it in iterables)
+
+    pending = len(iterables)
+    while pending:
+        try:
+            for next in nexts:
+                yield next()
+        except StopIteration:
+            pending -= 1
+            nexts = itertools.cycle(itertools.islice(nexts, pending))


Test patch:
diff --git a/sympy/sets/tests/test_fancysets.py b/sympy/sets/tests/test_fancysets.py
index f3159d25c3..71610ac1bf 100644
--- a/sympy/sets/tests/test_fancysets.py
+++ b/sympy/sets/tests/test_fancysets.py
@@ -220,7 +220,7 @@ def test_Range_set():
     assert all(i.is_Integer for i in Range(0, -1, 1))
 
     it = iter(Range(-oo, 0, 2))
-    raises(ValueError, lambda: next(it))
+    raises(TypeError, lambda: next(it))
 
     assert empty.intersect(S.Integers) == empty
     assert Range(-1, 10, 1).intersect(S.Integers) == Range(-1, 10, 1)
diff --git a/sympy/sets/tests/test_sets.py b/sympy/sets/tests/test_sets.py
index 559cd41df2..727cdb6dec 100644
--- a/sympy/sets/tests/test_sets.py
+++ b/sympy/sets/tests/test_sets.py
@@ -236,6 +236,19 @@ def test_difference():
 
 
 def test_Complement():
+    A = FiniteSet(1, 3, 4)
+    B = FiniteSet(3, 4)
+    C = Interval(1, 3)
+    D = Interval(1, 2)
+
+    assert Complement(A, B, evaluate=False).is_iterable is True
+    assert Complement(A, C, evaluate=False).is_iterable is True
+    assert Complement(C, D, evaluate=False).is_iterable is None
+
+    assert FiniteSet(*Complement(A, B, evaluate=False)) == FiniteSet(1)
+    assert FiniteSet(*Complement(A, C, evaluate=False)) == FiniteSet(4)
+    raises(TypeError, lambda: FiniteSet(*Complement(C, A, evaluate=False)))
+
     assert Complement(Interval(1, 3), Interval(1, 2)) == Interval(2, 3, True)
     assert Complement(FiniteSet(1, 3, 4), FiniteSet(3, 4)) == FiniteSet(1)
     assert Complement(Union(Interval(0, 2), FiniteSet(2, 3, 4)),
@@ -404,7 +417,7 @@ def test_intersection():
     i = Intersection(line**2, line**3, evaluate=False)
     assert (2, 2) not in i
     assert (2, 2, 2) not in i
-    raises(ValueError, lambda: list(i))
+    raises(TypeError, lambda: list(i))
 
     a = Intersection(Intersection(S.Integers, S.Naturals, evaluate=False), S.Reals, evaluate=False)
     assert a._argset == frozenset([Intersection(S.Naturals, S.Integers, evaluate=False), S.Reals])
@@ -434,6 +447,15 @@ def test_is_disjoint():
     assert Interval(0, 2).is_disjoint(Interval(3, 4)) == True
 
 
+def test_ProductSet__len__():
+    A = FiniteSet(1, 2)
+    B = FiniteSet(1, 2, 3)
+    assert ProductSet(A).__len__() == 2
+    assert ProductSet(A).__len__() is not S(2)
+    assert ProductSet(A, B).__len__() == 6
+    assert ProductSet(A, B).__len__() is not S(6)
+
+
 def test_ProductSet():
     # ProductSet is always a set of Tuples
     assert ProductSet(S.Reals) == S.Reals ** 1
@@ -1145,16 +1167,27 @@ def test_Eq():
 
 
 def test_SymmetricDifference():
-   assert SymmetricDifference(FiniteSet(0, 1, 2, 3, 4, 5), \
-          FiniteSet(2, 4, 6, 8, 10)) == FiniteSet(0, 1, 3, 5, 6, 8, 10)
-   assert SymmetricDifference(FiniteSet(2, 3, 4), FiniteSet(2, 3 ,4 ,5 )) \
-          == FiniteSet(5)
-   assert FiniteSet(1, 2, 3, 4, 5) ^ FiniteSet(1, 2, 5, 6) == \
-          FiniteSet(3, 4, 6)
-   assert Set(1, 2 ,3) ^ Set(2, 3, 4) == Union(Set(1, 2, 3) - Set(2, 3, 4), \
-          Set(2, 3, 4) - Set(1, 2, 3))
-   assert Interval(0, 4) ^ Interval(2, 5) == Union(Interval(0, 4) - \
-          Interval(2, 5), Interval(2, 5) - Interval(0, 4))
+    A = FiniteSet(0, 1, 2, 3, 4, 5)
+    B = FiniteSet(2, 4, 6, 8, 10)
+    C = Interval(8, 10)
+
+    assert SymmetricDifference(A, B, evaluate=False).is_iterable is True
+    assert SymmetricDifference(A, C, evaluate=False).is_iterable is None
+    assert FiniteSet(*SymmetricDifference(A, B, evaluate=False)) == \
+        FiniteSet(0, 1, 3, 5, 6, 8, 10)
+    raises(TypeError,
+        lambda: FiniteSet(*SymmetricDifference(A, C, evaluate=False)))
+
+    assert SymmetricDifference(FiniteSet(0, 1, 2, 3, 4, 5), \
+            FiniteSet(2, 4, 6, 8, 10)) == FiniteSet(0, 1, 3, 5, 6, 8, 10)
+    assert SymmetricDifference(FiniteSet(2, 3, 4), FiniteSet(2, 3 ,4 ,5 )) \
+            == FiniteSet(5)
+    assert FiniteSet(1, 2, 3, 4, 5) ^ FiniteSet(1, 2, 5, 6) == \
+            FiniteSet(3, 4, 6)
+    assert Set(1, 2 ,3) ^ Set(2, 3, 4) == Union(Set(1, 2, 3) - Set(2, 3, 4), \
+            Set(2, 3, 4) - Set(1, 2, 3))
+    assert Interval(0, 4) ^ Interval(2, 5) == Union(Interval(0, 4) - \
+            Interval(2, 5), Interval(2, 5) - Interval(0, 4))
 
 
 def test_issue_9536():
@@ -1221,8 +1254,11 @@ def test_issue_10113():
 
 
 def test_issue_10248():
-    assert list(Intersection(S.Reals, FiniteSet(x))) == [
-        (-oo < x) & (x < oo)]
+    raises(
+        TypeError, lambda: list(Intersection(S.Reals, FiniteSet(x)))
+    )
+    A = Symbol('A', real=True)
+    assert list(Intersection(S.Reals, FiniteSet(A))) == [A]
 
 
 def test_issue_9447():