[Python-Dev] Using lists as sets

[Ka-Ping Yee]

On Fri, 17 Mar 2000, Ken Manheimer wrote:
> 
> I really like the idea of using dynamically-tuned lists provide set
> functionality!  I often wind up needing something like set functionality,
> and implementing little convenience routines (unique, difference, etc)
> repeatedly.  I don't mind that so much, but the frequency signifies that
> i, at least, would benefit from built-in support for sets...

Greg asked about how to ensure that a given item only appears
once in each list when used as a set, and whether i would
flag the list as "i'm now operating as a set".  My answer is no --
i don't want there to be any visible state on the list.  (It can
internally decide to optimize its behaviour for a particular purpose,
but in no event should this decision ever affect the semantics of
its manifested behaviour.)  Externally visible state puts us back
right where we started -- now the user has to decide what type of
thing she wants to use, and that's more decisions and loaded guns
pointing at feet that we were trying to avoid in the first place.

There's something very nice about there being just two mutable
container types in Python.  As Guido said, the first two types
you learn are lists and dicts, and it's pretty obvious which
one to pick for your purposes, and you can't really go wrong.

I'd like to copy my reply to Greg here because it exposes some of the
philosophy i'm attempting with this proposal:

    You'd trust the client to use take() (or should i say include())
    instead of append().  But, in the end, this wouldn't make any
    difference to the result of "in".  In fact, you could do multisets
    since lists already have count().

    What i'm trying to do is to put together a few very simple pieces
    to get all the behaviour necessary to work with sets, if you want
    it.  I don't want the object itself to have any state that manifests
    itself as "now i'm a set", or "now i'm a list".  You just pick the
    methods you want to use.

    It's just like stacks and queues.  There's no state on the list that
    says "now i'm a stack, so read from the end" or "now i'm a queue,
    so read from the front".  You decide where you want to read items
    by picking the appropriate method, and this lets you get the best
    of both worlds -- flexibility and simplicity.

Back to Ken:
> I guess the question is whether it's practical to come up with a
> reasonably adequate, reasonably general dynamic optimization strategy.  
> Seems like an interesting challenge - is there prior art?

I'd be quite happy with just turning on set optimization when
include() and exclude() get used (nice and predictable).  Maybe you
could provide a set() built-in that would construct you a list with
set optimization turned on, but i'm not too sure if we really want
to expose it that way.


-- ?!ng