[Python-ideas] Predicate Sets

[Devin Jeanpierre]

On Sun, Jan 19, 2014 at 11:56 PM, Andrew Barnert <abarnert at yahoo.com> wrote:
> From: Daniel da Silva <var.mail.daniel at gmail.com>
>>Overview:
>>    Sets in mathematics can be defined by a list of elements without repetitions, and alternatively by a predicate (function) that determines inclusion.
>
> The whole point of modern set theory is that sets cannot be defined by a predicate alone; only by a predicate _and a set to apply it over_. Which we already have in set comprehensions.
>
> And your suggestion has the exact same problem that naive set theory had:
>
>>>> myset = predicateset(lambda s: s.startswith('a'))
>>>> 'xyz' in myset
> False
>
>>>> russellset = predicateset(lambda s: s not in s)
>>>> russellset in russelset
>
> Presumably this should cause the computer to scream "DOES NOT COMPUTE!" and blow up, which I think would be hard to implement in CPython.
>
> Still, this could be useful despite not being mathematically consistent.

No; what you have shown is that a predicateset can't both accept the
function you specified, and also have its containment method always
return a value (as opposed to raising an exception or not halting).
You have not shown that the idea of a predicateset is inherently
contradictory, unless that idea includes both of those facts -- and
that would indeed be silly, since, as you've shown, that is an idea
with self-contradicting requirements.

In contrast, naive set theory thought all of those things: a set can
be defined in that way, and a set either contains something or not,
but not neither and not both. And Russell proved that this is impossible.

There is not any kind of fundamental problem with the idea of a Python
set-like object defined by Python predicates. Python sets aren't
mathematical sets, and Python predicates aren't mathematical
predicates. Things can be different from how they are described in
mathematics, without being internally inconsistent, and without being
useless.

[...]
> The big problem is coming up with a compelling use case.
[...]
> In general, calling a function is just as easy, natural, and readable as testing membership; calling filter or using a comprehension would generally be simpler than creating a predicateset just to use intersection; etc.

Yes. If a predicate set is just a thin wrapper around predicates, it
is pointless. IMO the only utility of specially wrapping predicates is
allowing them to be combined efficiently, but the bulk of the work
there is just in manipulating sets of bitvectors (best done with
ROBDDs as far as I know). Arguably the work after that is trivial.

-- Devin