CODEWITHSUNDEEP
python
Lance Strait
Lance Strait

Reputation: 4261

Using Lists with Sets (Unhashable Type error)

So I am trying to use a set to keep track of tuples that contain a tuple and a list of tuples. Here is an example of what is in the set before the error:

((1, 16), [(1, 1), (1, 13), (1, 14), (1, 15), (1, 18), (2, 1), (2, 4),  (2, 7), (2, 10), (2, 13), (2, 18), (3, 6), (3, 7), (3, 8), (3, 9), (3, 10), (3, 18)])

Here is the error I get:

Traceback (most recent call last):
File "src/graph.py", line 60, in <module>
end_node, A_expanded = A_search_multiple(maze,start,dot_locs)
 File "/home/lstrait2/cs440/mp1/src/search_multiple.py", line 37, in      A_search_multiple
if((loc,state) not in closed):
 TypeError: unhashable type: 'list'
[lstrait2@linux-a2 mp1]$ gedit src/search_multiple.py

Is there anything I can do to make this work? Basically I am using the set to make sure no tuple of the form (location, list of locations) appears twice.

Upvotes: 0

Views: 1066

Answers (1)

Travis Griggs
Travis Griggs

Reputation: 22252

Short answer:

You have to convert your list into a tuple. It is legal to have a tuple of tuples (nested tuples).

Why is this?

Sets and Dictionaries work on a principle of uniqueness. At the time values are added to them, they determine if they already contain a value of equal nature. That is the only time the container has the opportunity to enforce its invariant of unique elements. Lists can certainly be compared for equality, but the problem is that they can change. Let us pretend that you could add lists to a set. Consider the following example:

list1 = [42]
list2 = [42, 13]
list1 == list2 # this would show false, they're different lists, obviously
mySet = set()
mySet.add(list1) # python won't allow this, but we're pretending it would
mySet.add(list2) # ditto

If we printed mySet at this point, we'd expect to something like:

{[42, 13], [42]}

But we can change lists, so what if we now executed:

list1.append(13)
list1 == list2 # This used to be false, but now it is true

Unbeknownst to the containing set, outside of it's awareness, two of its elements have suddenly become equal. Now we've violated the invariant that a set's elements should be unique.

To avoid this problem, dicts and sets won't allow you to stick objects in them that it knows have a predisposition to changing.

Upvotes: 2

Related Questions