Terry Jones briefly mentioned support for very large sets via complements, which I think would solve many of the issues you bring up.<br><br><div class="gmail_quote">On Thu, Jul 23, 2009 at 08:26, Steven D'Aprano <span dir="ltr"><<a href="mailto:steve@pearwood.info">steve@pearwood.info</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="im">On Thu, 23 Jul 2009 04:28:33 pm Andy Kish wrote:<br>
> Hi all,<br>
><br>
> I think the addition of a universal set object would be a nice touch<br>
> for python sets.<br>
<br>
</div>But you can't have a universal set until you know what the problem<br>
domain is. If the problem domain is citrus fruits, then the universal<br>
set is: {lemons, limes, grapefruits, oranges, mandarins, tangelos,<br>
kumquats, ... }<br>
<br>
If the problem domain is Presidents of the USA, then the universal set<br>
is: {Washington, Lincoln, Bush, Clinton, Obama, Wilson, ... }<br>
<br>
If the problem domain is integers, then it is {0, 1, -1, 2, -2,<br>
3, -3, ...}<br>
<br>
The first two are finite, the third is infinite.<br><div class="im"></div></blockquote><div><br>The domain is inherently all objects that can be put into a Python set, so the universal set is all Python objects. (I think for the purposes of Python we could gloss over the
set-theoretical paradoxiness of "set.universal() in set.universal()"
returning True :)<br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="im">
> Manipulation of collections of sets becomes much<br>
> easier with it. Right now, certain operations are easy because empty<br>
> sets are easy to create while the dual operation requires special<br>
> cases:<br>
><br>
> set_union = set()<br>
> for s in sets:<br>
> set_union |= s<br>
<br>
</div>Better written as:<br>
<br>
>>> reduce(operator.or_, [set([1, 2, 3]), set([2, 4, 5])])<br>
set([1, 2, 3, 4, 5])<br>
<div class="im"><br>
<br>
> # this doesn't work<br>
> set_intersection = set(???)<br>
> for s in sets:<br>
> set_intersection &= s<br>
<br>
</div>But this does:<br>
<br>
>>> reduce(operator.and_, [set([1, 2, 3]), set([2, 4, 5])])<br>
set([2])<br>
<div class="im"><br>
<br>
> Implementation of a universal set would be pretty trivial.<br>
<br>
</div>You think so? I can think of a number of problems.<br>
<br>
(1) What elements should go into the universal set? Strings, ints,<br>
floats, presidents... ?<br>
</blockquote><div><br>There are two ways of defining what is "in" a set. One is what iter(set.universal()) iterates through, which there is no good answer for. But the other (arguably just as common) way to define what is "in" a set s is "the set of Python objects p such that "p in s" returns True." This latter definition is trivial to implement for the universal set. If we keep track of the complement of a nearly-universal set, that also gives us an easy way to implement in.<br>
<br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">(2) What is len(set.universal())?<br>
</blockquote><div><br>inf. Perhaps there is a complication since inf is technically a float type? I don't see it being a huge deal. ("Real" universal sets have uncountably many elements, whereas AFAICT floating-point inf is countable; since we have finite-memory systems I can't imagine it makes a difference.)<br>
<br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">(3) What does set.universal() print?<br>
</blockquote><div><br>Some special-case string; maybe "set(U)" for the universal set, or "set(U-[elements,in,complement])" for general nearly-infinite sets.<br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
(4) What does set.universal().clear() do?<br>
</blockquote><div><br>set.universal() doesn't have to be a singleton; it could return a brand new, mutable universal set. So set.universal() returns a new set, and .clear() clears a set regardless of what it contains.<br>
<br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">(5) For that matter, union(), copy(), difference(), issubset(), etc?<br>
</blockquote><div><br>I think these all fall pretty easily out of the definition of a universal set and a complement representation of nearly infinite sets.<br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
(The universal set for strings of length one is a subset of the<br>
universal set for all strings.)<br>
</blockquote><div><br>The universal set is a superset of all of these: it is the set of all Python objects. (Yes, that's paradoxical, but again, I don't think that matters for most use cases in Python.) <br><br></div>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">I don't think there is a suitable solution for all of these issues. That<br>
would mean that set.universal() can't be a real set object, it has to<br>
be some sort of not-quite-a-set object that doesn't provide the entire<br>
set interface.<br>
<br>
</blockquote><div><br>Storing the complement of an infinite set is pretty straightforward way of implementing sets that are universal except for a few (maybe zero) elements, and can satisfy the entire set interface except for iteration. As you suggest, it would be far trickier to provide general infinite sets, like the set of all integers, but that's not what's being asked for here.<br>
<br>I'm not saying it won't be tricky to implement; it requires changing pretty much all set methods, I've never touched CPython code. I'm also roughly +0 on the issue (not that my vote counts since I lurk far more than I contribute). I'm just pointing out it's possible.<br>
</div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><br>
<br>
--<br>
<font color="#888888">Steven D'Aprano<br>
</font><div><div></div><div class="h5">_______________________________________________<br>
Python-ideas mailing list<br>
<a href="mailto:Python-ideas@python.org">Python-ideas@python.org</a><br>
<a href="http://mail.python.org/mailman/listinfo/python-ideas" target="_blank">http://mail.python.org/mailman/listinfo/python-ideas</a><br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br>It is better to be quotable than to be honest.<br> -Tom Stoppard<br><br>Borowitz<br>