[Python-Dev] Using lists as sets

[Ka-Ping Yee]

On Fri, 17 Mar 2000, David Ascher wrote:
> > I think the semantics would be pretty understandable and simple to
> > explain, which is the main thing.
> >
> > Any thoughts?
> 
> Would
> 
> 	(a,b) in Set
> 
> return true of (a,b) was a subset of Set, or if (a,b) was an element of Set?

This would return true if (a, b) was an element of the set --
exactly the same semantics as we currently have for lists.

Ideally it would also be kind of nice to use < > <= >= as
subset/superset operators, but that requires revising the
way we do comparisons, and you know, it might not really be
used all that often anyway.

-, |, and & could operate on lists sensibly when we use
them as sets -- just define a few simple rules for ordering
and you should be fine.  e.g.

    c = a - b is equivalent to

        c = a
        for item in b: c.drop(item)

    c = a | b is equivalent to

        c = a
        for item in b: c.take(item)

    c = a & b is equivalent to

        c = []
        for item in a:
            if item in b: c.take(item)

where

    c.take(item) is equivalent to

        if item not in c: c.append(item)

    c.drop(item) is equivalent to

        while item in c: c.remove(item)


The above is all just semantics, of course, to make the point
that the semantics can be simple.  The implementation could do
different things that are much faster when there's a hash table
helping out.


-- ?!ng