list parameter of a recursive function

[TP]

Hi,

I have a function f that calls itself recursively. It has a list as second
argument, with default argument equal to None (and not [], as indicated at:
http://www.ferg.org/projects/python_gotchas.html#contents_item_6 )

This is the outline of my function:

def f ( argument, some_list = None ):

if some_list == None:
some_list = []
[...]
# creation of a new_argument
# the function is called recursively only if some condition is respected
if some_condition:
some_list.append( elem )
f( new_argument, some_list )
# otherwise, we have reached a leaf of the a branch of the recursive tree
# (said differently, terminal condition has been reached for this branch)
print "Terminal condition"

The problem is that when the terminal condition is reached, we return back
to some other branch of the recursive tree, but some_list has the value
obtained in the previous branch!
So, it seems that there is only one some_list list for all the recursive
tree.
To get rid of this behavior, I have been compelled to do at the beginning of
f:

import copy from copy
some_list = copy( some_list )

I suppose this is not a surprise to you: I am compelled to create a new
some_list with the same content.
So, if I am right, all is happening as if the parameters of a function are
always passed by address to the function. Whereas in C, they are always
passed by copy (which gives relevance to pointers).

Am I right?

Julien

--
python -c "print ''.join([chr(154 - ord(c)) for c in '*9(9&(18%.\
9&1+,\'Z4(55l4('])"

"When a distinguished but elderly scientist states that something is
possible, he is almost certainly right. When he states that something is
impossible, he is very probably wrong." (first law of AC Clarke)

 

[Chris Torek]

I have a function f that calls itself recursively. It has a list as second
argument, with default argument equal to None (and not [], as indicated at:
http://www.ferg.org/projects/python_gotchas.html#contents_item_6 )

This is the outline of my function:

def f ( argument, some_list = None ):

if some_list == None:
some_list = []
[...]
# creation of a new_argument
# the function is called recursively only if some condition is respected
if some_condition:
some_list.append( elem )
f( new_argument, some_list )
# otherwise, we have reached a leaf of the a branch of the recursive tree
# (said differently, terminal condition has been reached for this branch)
print "Terminal condition"

The problem is that when the terminal condition is reached, we return back
to some other branch of the recursive tree, but some_list has the value
obtained in the previous branch!

Yes, this is the way it is supposed to work.

So, it seems that there is only one some_list list for all the recursive
tree. To get rid of this behavior, I have been compelled to do at the
beginning of f:

import copy from copy

[from copy import copy, rather]

some_list = copy( some_list )

I suppose this is not a surprise to you: I am compelled to create a new
some_list with the same content.

The above will work, or for this specific case, you can write:

some_list = list(some_list)

which has the effect of making a shallow copy of an existing list:

>>> base = [1, 2]
>>> l1 = base
>>> l2 = list(l1)
>>> l1 is l2 False
>>> l1[0] is l2[0] True
>>> base.append(3)
>>> l2 [[1, 2, 3]]
>>>

but will also turn *any* iterator into a (new) list; the latter
may often be desirable.

So, if I am right, all is happening as if the parameters of a function are
always passed by address to the function. Whereas in C, they are always
passed by copy (which gives relevance to pointers).

Am I right?

Mostly. Python distinguishes between mutable and immutable items.
Mutable items are always mutable, immutable items are never mutable,
and the mutability of arguments is attached to their "fundamental
mutability" rather than to their being passed as arguments. This
is largely a point-of-view issue (although it matters a lot to
people writing compilers, for instance).

Note that if f() is *supposed* to be able to modify its second
parameter under some conditions, you would want to make the copy
not at the top of f() but rather further in, and in this case,
that would be trivial:

def f(arg, some_list = None):
if some_list is None:
some_list = []
...
if some_condition:
# make copy of list and append something
f(new_arg, some_list + [elem])
elif other_condition:
# continue modifying same list
f(new_arg, some_list)
...

(Note: you can use also the fact that list1 + list2 produces a new
list to make a copy by writing "x = x + []", or "x = [] + x", but
"x = list(x)" is generally a better idea here.)

 

[TP]

import copy from copy

[from copy import copy, rather]

Yes, sorry.

Note that if f() is *supposed* to be able to modify its second
parameter under some conditions, you would want to make the copy
not at the top of f() but rather further in, and in this case,
that would be trivial:

def f(arg, some_list = None):
if some_list is None:
some_list = []
...
if some_condition:
# make copy of list and append something
f(new_arg, some_list + [elem])
elif other_condition:
# continue modifying same list
f(new_arg, some_list)

Thanks a lot Chris!
I think I prefer doing an explicit copy.copy, because it allows to remind
the reader that it is very important to take care of that. But your trick is
very interesting also.

Cheers,

Julien


--
python -c "print ''.join([chr(154 - ord(c)) for c in '*9(9&(18%.\
9&1+,\'Z4(55l4('])"

"When a distinguished but elderly scientist states that something is
possible, he is almost certainly right. When he states that something is
impossible, he is very probably wrong." (first law of AC Clarke)

 

[Terry Reedy]

Hi,

I have a function f that calls itself recursively. It has a list as second
argument, with default argument equal to None (and not [], as indicated at:
http://www.ferg.org/projects/python_gotchas.html#contents_item_6 )

This sort of function is an exception. If you add the line below, so
that you can use just one list, you should just say 'some_list = []' in
the header.

This is the outline of my function:

def f ( argument, some_list = None ):

if some_list == None:
some_list = []
[...]
# creation of a new_argument
# the function is called recursively only if some condition is respected
if some_condition:
some_list.append( elem )
f( new_argument, some_list ) some_list.pop()
# otherwise, we have reached a leaf of the a branch of the recursive tree
# (said differently, terminal condition has been reached for this branch)
print "Terminal condition"

The problem is that when the terminal condition is reached, we return back
to some other branch of the recursive tree, but some_list has the value
obtained in the previous branch!

Uhless you pop items off the stack as you back up!

This is assuming that you do not need to keep the leaf value of the list
as the funcions works up and back down to the next leaf, and so on. Even
if you do, it might still be better to copy the working buffer just once
when you hit the leaf.

So, it seems that there is only one some_list list for all the recursive
tree.
To get rid of this behavior, I have been compelled to do at the beginning of
f:

import copy from copy
some_list = copy( some_list )

I suppose this is not a surprise to you: I am compelled to create a new
some_list with the same content.
So, if I am right, all is happening as if the parameters of a function are
always passed by address to the function. Whereas in C, they are always
passed by copy (which gives relevance to pointers).

C sometimes copies values and sometimes passes addresses (pointers,
references). It does the latter for arrays and functions. I think the
rule has varied for structs. C and Python have quite different
name-object-value models.

Python calls functions by binding argument objects to parameter names.
Unlike C assignment, Python name binding never copies objects.

CPython implements binding by directly associating name and object
address. It also does not use a garbage collector that move objects
around in memory. Other implementation do differently.

 

[Diez B. Roggisch]

Hi,

I have a function f that calls itself recursively. It has a list as second
argument, with default argument equal to None (and not [], as indicated at:
http://www.ferg.org/projects/python_gotchas.html#contents_item_6 )

This is the outline of my function:

def f ( argument, some_list = None ):

if some_list == None:
some_list = []
[...]
# creation of a new_argument
# the function is called recursively only if some condition is respected
if some_condition:
some_list.append( elem )
f( new_argument, some_list )
# otherwise, we have reached a leaf of the a branch of the recursive tree
# (said differently, terminal condition has been reached for this branch)
print "Terminal condition"

The problem is that when the terminal condition is reached, we return back
to some other branch of the recursive tree, but some_list has the value
obtained in the previous branch!
So, it seems that there is only one some_list list for all the recursive
tree.
To get rid of this behavior, I have been compelled to do at the beginning of
f:

import copy from copy
some_list = copy( some_list )

I suppose this is not a surprise to you: I am compelled to create a new
some_list with the same content.
So, if I am right, all is happening as if the parameters of a function are
always passed by address to the function. Whereas in C, they are always
passed by copy (which gives relevance to pointers).

Am I right?

Yes and no. For some sensible definition of yes (this is to avoid the
*endless* discussions about python parameter passing semantics and it's
relation to common, yet misunderstood or unprecisely defined definitions
of parameter passing), passing around a mutable object (such as a list
or dictionary) will be like a pointer - mutations are visible to all
others having a reference to it.

You are wrong though that C-semantics are different, meaning that
"passing by copy" is not what happens. Some things are copied (primitive
types, structs that are passed directly). But not, for example - and
relevant to this case - arrays (as they are "only" pointers), lists (as they
don't exist, but are modeled by structs containing pointers).

Back to your example: your solution is perfectly fine, although a bit
costly and more error-prone if you happen to forget to create a copy.
A safer alternative for these cases is using tuples, because they are
immutable.

Diez

 

[Steven D'Aprano]

I think I prefer doing an explicit copy.copy, because it allows to
remind the reader that it is very important to take care of that.

I think a comment is better for that. It's better to explicitly say
something is important than to assume the reader will guess.

Besides, what if the caller wants to supply their own list, and they
*want* it modified in place rather than a copy made? (I have no idea why
they might want this, but anything is possible...) You should avoid
making copies except in methods that are *for* making copies.

 

[TP]

Back to your example: your solution is perfectly fine, although a bit
costly and more error-prone if you happen to forget to create a copy.
A safer alternative for these cases is using tuples, because they are
immutable.

Thanks Diez for your explanation.
The problem with tuples is that it is not easy to modify them: in my case, I
need to append a string to the tuple at each recursive step.
So, it seems to me that I need to write a loop to modify the tuple, because

a=("foo", "bar")
b=(a[0],a[1],"toto")
b

(u'foo', u'bar', u'toto')

I do not find any other means to obtain that result for b. With lists, I can
use ".extend()".
Am I right?


--
python -c "print ''.join([chr(154 - ord(c)) for c in '*9(9&(18%.\
9&1+,\'Z4(55l4('])"

"When a distinguished but elderly scientist states that something is
possible, he is almost certainly right. When he states that something is
impossible, he is very probably wrong." (first law of AC Clarke)

 

[TP]

I think a comment is better for that. It's better to explicitly say
something is important than to assume the reader will guess.

Yes, you are right.

Besides, what if the caller wants to supply their own list, and they
*want* it modified in place rather than a copy made? (I have no idea why
they might want this, but anything is possible...) You should avoid
making copies except in methods that are *for* making copies.

My function gives a sensible result only if the list is not modified in
place. In fact, this list is only used internally for the recursion. That is
why I have made this function "private":

def __relation_loop( sqlite_cursor
, table_name
, crossed_tables = None
, previous_step_link = None
, onetomany_allowed_depth = 1 ):

I give to the user (me!) only access to the public function:

def relation_loop( sqlite_cursor
, table_name
, onetomany_allowed_depth = 1 ):

return __relation_loop( sqlite_cursor
, table_name
, crossed_tables = None
, previous_step_link = None
, onetomany_allowed_depth = onetomany_allowed_depth )

So, crossed_tables and previous_step_link, are only used by the recursion
process, they are not accessible to the user.

--
python -c "print ''.join([chr(154 - ord(c)) for c in '*9(9&(18%.\
9&1+,\'Z4(55l4('])"

"When a distinguished but elderly scientist states that something is
possible, he is almost certainly right. When he states that something is
impossible, he is very probably wrong." (first law of AC Clarke)

 

[Chris Rebert]

Back to your example: your solution is perfectly fine, although a bit
costly and more error-prone if you happen to forget to create a copy.
A safer alternative for these cases is using tuples, because they are
immutable.

Thanks Diez for your explanation.
The problem with tuples is that it is not easy to modify them: in my case, I
need to append a string to the tuple at each recursive step.
So, it seems to me that I need to write a loop to modify the tuple, because

a=("foo", "bar")
b=(a[0],a[1],"toto")
b

(u'foo', u'bar', u'toto')

I do not find any other means to obtain that result for b. With lists, I can
use ".extend()".
Am I right?

Nope, sorry'foo', 'bar', 'toto')

Cheers,
Chris

 

[Seebs]

The problem with tuples is that it is not easy to modify them:

This is probably the best post-and-response I've seen in the last couple
of months.

-s

 

[Diez B. Roggisch]

Back to your example: your solution is perfectly fine, although a bit
costly and more error-prone if you happen to forget to create a copy.
A safer alternative for these cases is using tuples, because they are
immutable.

Thanks Diez for your explanation.
The problem with tuples is that it is not easy to modify them: in my case, I
need to append a string to the tuple at each recursive step.
So, it seems to me that I need to write a loop to modify the tuple, because

a=("foo", "bar")
b=(a[0],a[1],"toto")
b

(u'foo', u'bar', u'toto')

I do not find any other means to obtain that result for b. With lists, I can
use ".extend()".
Am I right?

Yes and no - again. Of course you cannot use extend. But you can
concatenate:

b = a + ("toto",)

Note the trailing comma. A common misconception is to think that tuples
are build using parethesis. They aren't. They are build using the
comma-operator, and needed for disambiguation, e.g. in this case:

foo(a, (b, c))

Diez

 

[TP]

This is probably the best post-and-response I've seen in the last couple
of months.

Yes, they are immutable. I badly expressed the fact that the facilities
of lists to create new lists are not available with tuples.

But my sentence was funny, I have to admit it I hope that this
conversation will not be included in the "fortunes"!!

--
python -c "print ''.join([chr(154 - ord(c)) for c in '*9(9&(18%.\
9&1+,\'Z4(55l4('])"

"When a distinguished but elderly scientist states that something is
possible, he is almost certainly right. When he states that something is
impossible, he is very probably wrong." (first law of AC Clarke)