Conceptualizing set comprehension

Question

def nfa_eclosure(M, s):
    """
    >>> M = [{'':{1,2,3}}, {'b':{1}}, {'a':{2}}]
    >>> nfa_eclosure(M, 0)
    set([0, 1, 2, 3])
    """
    try:
        states = {nfa_eclosure(M, x+1) for x in xrange(len(M[s])) if M[s].get('')}
    except IndexError:
        states = set([])
    states.add(s)
    return states

Running this throws TypeError: unhashable type: 'set'but I can't see the problem.

---

Edit: 2014-02-03 15:25:00

Thanks for the explanations everyone. That makes sense. Is there a "pythonic" way to take the code I have now and "splat" the contents of a set into a new set, rather than convert everything to a frozenset and then flatten it?

---

Edit: 2014-02-04 00:41:00

I made some modifications and now I came up with this:

try:
    return set([s]).union(*(nfa_eclosure(M, x) for x in M[s].get('')))
except IndexError:
    return set([s])

but I have a new error message

TypeError: union() argument after * must be a sequence, not generator

A google search didn't exactly explain the situation too well. Know what's going on?

Answer 1

You're trying to build a set of sets, recursively. This is not allowed because sets are unhashable and therefore cannot be placed in a set. You can use a frozenset because they are hashable.

try:
    states = frozenset({nfa_eclosure(M, x+1) for x in xrange(len(M[s])) if M[s].get('')})
except IndexError:
    states = frozenset([])

sets are unordered, precisely because they are ordered internally by the hash of their members. This allows for fast lookup of set members.

Read up on the docs for sets and hashable

Answer 2

You are trying to make a set of sets. This won't work, because a set is not a hashable type, as it is mutable, and sets can only contain hashable types. This is because Python uses the hashes of items in a set to quickly check for membership.

You might able to use a frozenset instead. Failing that, try a list.

Answer 3

Thanks for the help everyone. I'll get to accepting an answer shortly. Just wanted to explain the other issue I was having. Apparently the error I was seeing with TypeError was a bug. Upon closer inspection, I was trying to iterate of NoneType with the given key didn't exist for the dictionary. I set the default to set([]) and now everything runs as expected. Didn't end up going with the frozen set, but thanks for explaining it! I was so confused.