cannot understand the critical comma in this function

Question

I have two questions regarding to a backtrack method. So I was looking at a function that can generate n parenthesis in all legal ways.

def gen_par(p, left, right, parens=[]):
    if left:
        gen_par(p + '(', left - 1, right)
    if right > left:
        gen_par(p + ')', left, right - 1)
    if not right:
        parens += p,
    return parens


print(gen_par('', 2, 2))
# >>> ['(())', '()()']

I noticed that there is a line parens += p, and the , at the end is doing something very important and I don't understand why.

if I take that , off, I will get this:

print(gen_par('', 2, 2))
# >>> ['(', '(', ')', ')', '(', ')', '(', ')']

In a addition, I don't understand why parens=[] has to be written in the parameter, and if I move it out to the body:

def gen_par(p, left, right):
    parens = []
    if left:
        gen_par(p + '(', left - 1, right)
    if right > left:
        gen_par(p + ')', left, right - 1)
    if not right:
        parens += p,
    return parens

This won't work.

So the two questions will be:

What is the function of that ,
Why is parens needs to be in the parameter area?

Thanks,

It's equivalent to `(p,)`; the parentheses have *nothing* to do with the creation of the tuple, beyond there normal use for parenthesizing expressions. A list literal, on the other hand, is *defined* by the use of `[...]`. — chepner, Feb 07 '19 at 16:22
A near duplicate is https://stackoverflow.com/questions/7992559/what-is-the-syntax-rule-for-having-trailing-commas-in-tuple-definitions, but it focuses more on the use of a trailing comma in *any* tuple literal, rather than the need (or lack thereof) for parentheses. — chepner, Feb 07 '19 at 16:23

chepner · Answer 1 · 2019-02-07T16:52:12.513

1

Contrary to popular belief, you don't need parentheses to create tuples:

>>> x = 1,
>>> type(x)
<type 'tuple'>

The only time you need parentheses is to disambiguate the tuple-constructing comma from another use of a comma. For example, commas are also used to separate the arguments to a function, and a trailing comma in such an argument list is optional, so

>>> type(1,)   # Equivalent to type(1)
<type 'int'>

but

>>> type((1,))  # or type((1,),)
<type 'tuple'>

As for the second question, don't use a mutable default argument. Instead, pass the necessary lists explicitly, so that the mutated default argument doesn't interfere with other calls to gen_par.

def gen_par(p, left, right, parens):
    if left:
        parens = gen_par(p + '(', left - 1, right, parens)
    if right > left:
        parens = gen_par(p + ')', left, right - 1, parens)
    if not right:
        parens += p,
    return parens


print(gen_par('', 2, 2, []))

edited Feb 07 '19 at 16:52

answered Feb 07 '19 at 16:20

chepner

497,756
71
530
681

How so? It's what lets you write `x, y = some_function()` rather than `(x,y) = some_function()`. When you do need parentheses, it's for the same reason you need them to distinguish between `2 * 3 + 5` and `2 * (3 + 5)`. – chepner Feb 07 '19 at 16:25
Ok, that makes sense. What about the second question? – jxie0755 Feb 07 '19 at 16:25
It's taking advantage of the fact that the same list (which is initially empty) is shared by *all* calls to `gen_par` that don't explicitly provide a list. See https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument for why that's generally a bad idea. `gen_par` should instead *always* take a list argument when it is called, with an empty list passed as the argument to the first call. Otherwise, trying to call `gen_par` a second time (non-recursively) will fail. – chepner Feb 07 '19 at 16:47
I did read somewhere else before, says to avoid using mutable elements as default parameters in a function. – jxie0755 Feb 07 '19 at 16:49

score 1 · Accepted Answer · answered Feb 07 '19 at 16:43

The first part of the question is already answered -- comma is what create tuples, not parentheses. For a caveat, please see a question of mine: Why do tuples need parantheses in list comprehension

The second part of your question is pretty simple: In your second code you are treating parens as a local variable which gets reset in each iteration, and the function returns an empty list at the end. You can treat it as a global variable to get a result equivalent to the first code, like so:

parens = []

def gen_par(p, left, right):
    global parens
    if left:
        gen_par(p + '(', left - 1, right)
    if right > left:
        gen_par(p + ')', left, right - 1)
    if not right:
        parens += p,
    return parens

print(gen_par('', 2, 2))
# Returns ['(())', '()()'] correctly.

Wow, this is superbly interesting way to global a variable in recursive method. I have never realized that this is possible. — jxie0755, Feb 07 '19 at 16:46

cannot understand the critical comma in this function

2 Answers2