Addition and += give different results for list (depth first search)

Question

I've been trying to understand depth first search, and using various sources online obtained the following code:

graph = {'A': ['B', 'D'], 'B': ['E'], 'C': [], 'D': ['C', 'E'], 
         'E': ['H', 'I', 'J'], 'F': [], 'G': [], 'H': ['F'], 
         'I': [], 'J': ['G']}

def dfs(graph, start, end, path=None):
    if path == None:
        path = []
    path = path + [start]
    paths = []
    if start == end:
        return [path]
    for neighbour in graph[start]:
        if neighbour not in path:
            paths.extend(dfs(graph, neighbour, end, path))
    return paths

print(dfs(graph, 'A', 'G'))

This outputs the desired result:

[['A', 'B', 'E', 'J', 'G'], ['A', 'D', 'E', 'J', 'G']]

But when I replace the line path = path + [start] with path += [start] (or path.extend([start]), which I understand does the same thing) I get the following output: [['A', 'B', 'E', 'H', 'F', 'I', 'J', 'G', 'D', 'C']]

I know this is to do with a difference in the operations, but I don't really understand how it applies here. Please could someone explain this?

You should avoid setting default mutable argument like `path=[]`, which is a common gotcha in python (http://docs.python-guide.org/en/latest/writing/gotchas/#mutable-default-arguments) — Raymond, Jan 06 '18 at 13:06
didn't see that. but the problem persists after editing, probably, since OP didn't use `dfs` with a default argument anyway. — Jean-François Fabre, Jan 06 '18 at 13:11
It does. It's an aside (and not an important one in this case, since the function is called only once) but one that taught me something I should know! And yes, the problem persists. — HelloWorld4444, Jan 06 '18 at 13:12
my answer completely ignored this(since I didn't see the [least atonishment and mutable argument](https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument) issue) — Jean-François Fabre, Jan 06 '18 at 13:15
Current code outputs: `[['A', 'B', 'E', 'H', 'F', 'I', 'J', 'G', 'D', 'C']]` and not `[['A', 'B', 'E', 'J', 'G'], ['A', 'D', 'E', 'J', 'G']]` as mentioned in the question. — rnso, Jan 06 '18 at 13:16

Jean-François Fabre · Accepted Answer · 2018-01-06T13:52:19.280

this

path = path + [start]

is slightly different than

path += [start]  # or path.extend([start])

for lists (and other mutable types) because it recreates a new reference of path (implicitly what you want, you don't want to write into the previous reference)

path += [start]  # or path.extend([start])

reuses the same reference because you're passing path many times here in your loop (without making a copy):

for neighbour in graph[start]:
    if neighbour not in path:
       paths.extend(dfs(graph, neighbour, end, path))

so if some other object has it in storage, you're changing both lists: not the same behaviour, not the behaviour you want.

Of course you could do paths.extend(dfs(graph, neighbour, end, path.copy())) but that would be against the principle of least atonishment for the caller (which doesn't expect the last parameter to be modified)

My advice:

If you want performance and you don't care about reusing the reference or not, always use += for lists because it just extends the list. The + operator creates a new list and copies, which is really slower.
when using path = path + something with a list type, always include a comment for future maintainers (including yourself!) not to optimize that with +=.

maybe some more explicit and equivalent code:

path = path.copy() # or path[:], or list(path)...: force creation of a new reference to break dependency with passed parameter
path += [start]

Also note: it doesn't apply to str or tuple type because even += creates a new reference, because of the string immutability. No risk of sharing references with strings, so using tuple instead of list here would have fixed it as well:

if path == None:
    path = tuple()
path += (start,)  # += creates a new path reference, cos path is a tuple, immutable

(but don't expect more performance with += in that case, copies are made)

good advice but doesn't answer the question as to why OP got different results — ShpielMeister, Jan 06 '18 at 13:15
@ShpielMeister There were basically 2 big mistakes in that code, which confused readers. Now that OP fixed the argument one (which didn't change anything but still...), my answer answers :) I just love that site :) thanks. — Jean-François Fabre, Jan 06 '18 at 13:19
else, it would have been another sad duplicate of https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument — Jean-François Fabre, Jan 06 '18 at 13:21

Addition and += give different results for list (depth first search)

1 Answers1