Issue 2430 in sympy: Expression Countable Set
sy...@googlecode.com
Owner: MRock...@gmail.com
Labels: Type-Enhancement Priority-Medium
New issue 2430 by MRock...@gmail.com: Expression Countable Set
http://code.google.com/p/sympy/issues/detail?id=2430
I'm looking to build a basic vocabulary of sets. Currently Intervals,
Unions, and the EmptySet are implemented. Issue 2419 adds finite countable
sets like {1,2,3}. Issue 2424 adds cartesian products. One more major class
is sets which are like the natural numbers {1,2,3, ... } - infinite yet
countable. The elements of the geometric sequence {a*r^n | n in {1,2,3,...}
} are such a set.
What do sets need to be able to do?
- Test Membership
- Intersect with other sets
- Test for subset relations with other sets ( solved if you have
intersections really )
- Generate items in the set(nice to have)
How can we implement an object which can encode a possibly infinite (yet
countable) set and execute these operations efficiently?
My thought was to represent these sets as is done above for {a*r^n | n in
{1,2,3,...} }. The natural numbers and an expression, (a*r^n) was supplied.
My hope is that we can get everything we need by using existing SymPy
mechanics to manipulate the expression.
sy...@googlecode.com
Comment #1 on issue 2430 by christian.muise: Expression Countable Set
http://code.google.com/p/sympy/issues/detail?id=2430
Why not use lambda's to make up a set's behaviour? If it's countable, then
there should be a mapping from the ints to an element in the set and vice
versa. A lambda can be passed in that checks whether or not a number
qualifies. Using the set of even numbers as an example:
```python
even_numbers = CountableSet(lambda x: 0 == x % 2)
```
Internally, the check_membership function is set to be the passed in
lambda function. Then you could do set intersection (a new lambda that
checks both lambdas in the intersection), union (a new lambda that checks
at least one lambda in the union), etc.
Additionally, you could accept an optional second argument that is a
function to yield elements in the set given an integer:
```python
even_numbers = CountableSet(lambda x: 0 == x % 2, generator_func = lambda
x: 2*x)
```
If you are only concerned with sets that contain ints, you can have a
default generator_func that just iterates through integers until one passes
the test (inefficient, but gets the job done).
sy...@googlecode.com
Comment #2 on issue 2430 by asmeurer: Expression Countable Set
http://code.google.com/p/sympy/issues/detail?id=2430
```python``` only works in GitHub :)
That could be useful. We should support both. Actually, if you implement
set builder notation correctly, you should be able to just as easily say
{2*n|n\in ZZ}
or
{n\in ZZ|n % 2 == 0}.
The second one can also be written as
{n| n\in ZZ and n % 2 == 0}.
In other words, there are two parts. The first part is purely symbolic
(Expr), which is used to build the elements of the set. The second part is
the "such that" and defines which elements from the first part are in the
set. This is a Boolean that reduces to some kind of In object (I guess
it's some kind of 1st order logic object). We should use Lambda when
possible. And in this case, we would need a Mod() object.
This is all just me kind of rambling, by the way.
sy...@googlecode.com
Comment #4 on issue 2430 by MRock...@gmail.com: Expression Countable Set
http://code.google.com/p/sympy/issues/detail?id=2430
I've been playing with an idea for this here
https://github.com/mrocklin/sympy/blob/countable_set/sympy/core/fancysets.py
sy...@googlecode.com
Comment #5 on issue 2430 by asme...@gmail.com: Expression Countable Set
http://code.google.com/p/sympy/issues/detail?id=2430
Cool. We may need to change the names, as they conflict with single letter
names that we already have. I think it would be best to just use ZZ, NN,
etc. We'll need to either change the names of the poly domains or add some
magic to Poly to make these work like domains. I'm not sure what the
cleanest way to do that is.
Why is N._inf == -oo and N._sup == 0?
So you are using the definition of natural numbers that includes 0? Either
way is fine, but it needs to be documented. Also, if this is indeed the
case, than your definition of harmonics is wrong.
By the way, do you think these set related issues should go under the logic
label, or should I create a new label for sets?
sy...@googlecode.com
Comment #6 on issue 2430 by MRock...@gmail.com: Expression Countable Set
http://code.google.com/p/sympy/issues/detail?id=2430
-- Why is N._inf == -oo and N._sup == 0?
this is just a typo
-- So you are using the definition of natural numbers that includes 0?
Yes although I think I decided this with a coin flip while I was writing
the code.
-- Labels
No particular preference. I'm not planning to do extensive work with sets
in the near future if that's the question.
In general this code was just me playing to see how feasible this idea was.
I posted it to this issue to gather comments and suggestions for other ways
to do things.
One problem I'm running into is rules for intersection. The _intersection
methods are starting to include all possible interactions, i.e.
if other.is_Interval: ...
if other.is_FiniteSet: ...
if other.is_Union: ...
This is becoming troublesome.
Also, where should fancysets.py live? I don't think it belongs in the core.
sy...@googlecode.com
Comment #7 on issue 2430 by asme...@gmail.com: Expression Countable Set
http://code.google.com/p/sympy/issues/detail?id=2430
Personally, I don't see why any of the sets should be in the core (unless
I'm missing some fundamental core use of them). We should have a sets
module.
I don't have any thoughts on intersection right now.
> Yes although I think I decided this with a coin flip while I was writing
> the code.
Well, in my experience, {1, 2, 3, ...} is used more often, unless you are
talking about mathematical logic and Peano arithmetic. It just boils down
to writing N.union({0}) or N - {0} to get the other, though.
sy...@googlecode.com
Status: Started
Comment #10 on issue 2430 by MRock...@gmail.com: Expression Countable Set
http://code.google.com/p/sympy/issues/detail?id=2430
sy...@googlecode.com
Blockedon: 3231
Comment #11 on issue 2430 by MRock...@gmail.com: Expression Countable Set
http://code.google.com/p/sympy/issues/detail?id=2430
Ok, so we now have a TransformationSet
squares = TransformationSet(Lambda(x, x**2), S.Naturals)
In the original issue I said the following
What do sets need to be able to do?
- Test Membership
- Intersect with other sets
- Test for subset relations with other sets ( solved if you have
intersections really )
- Generate items in the set(nice to have)
Currently we have (1) and (4) but not (2) and thus not (3). I've made issue
3231 about intersections.
Also, I want to hear suggestions on sugared syntax. The way it is right now
is clear but ugly. Above Aaron mentioned writing set builder notation. I
suspect that this is not possible in the Python language. I'd love to be
wrong. Any thoughts on what could work?