list parameter of a recursive function
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)
--
http://mail.python.org/mailman/listinfo/python-list
Re: list parameter of a recursive function
In article TP wrote: >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.) -- In-Real-Life: Chris Torek, Wind River Systems Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603 email: gmail (figure it out) http://web.torek.net/torek/index.html -- http://mail.python.org/mailman/listinfo/python-list
Re: list parameter of a recursive function
Chris Torek wrote:
>>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)
--
http://mail.python.org/mailman/listinfo/python-list
Re: list parameter of a recursive function
TP writes: > 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: list parameter of a recursive function
On Wed, 06 Oct 2010 23:00:10 +0200, TP wrote: > 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. -- Steven -- http://mail.python.org/mailman/listinfo/python-list
Re: list parameter of a recursive function
Diez B. Roggisch wrote:
> 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
on a simple example:
>>> 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)
--
http://mail.python.org/mailman/listinfo/python-list
Re: list parameter of a recursive function
Steven D'Aprano wrote:
>> 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.
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)
--
http://mail.python.org/mailman/listinfo/python-list
Re: list parameter of a recursive function
On 2010-10-07, TP wrote: > Diez B. Roggisch wrote: >> A safer alternative for these cases is using tuples, because they are >> immutable. > 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 -- Copyright 2010, all wrongs reversed. Peter Seebach / usenet-nos...@seebs.net http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated! I am not speaking for my employer, although they do rent some of my opinions. -- http://mail.python.org/mailman/listinfo/python-list
Re: list parameter of a recursive function
On Wed, Oct 6, 2010 at 10:25 PM, TP wrote:
> Diez B. Roggisch wrote:
>
>> 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
> on a simple example:
>
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:
>>> a = ("foo", "bar")
>>> s = "toto"
>>> b = a + (s,)
>>> b
('foo', 'bar', 'toto')
Cheers,
Chris
--
http://blog.rebertia.com
--
http://mail.python.org/mailman/listinfo/python-list
Re: list parameter of a recursive function
TP writes:
> Diez B. Roggisch wrote:
>
>> 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
> on a simple example:
>
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
--
http://mail.python.org/mailman/listinfo/python-list
Re: list parameter of a recursive function
On 10/6/2010 3:22 PM, TP wrote: 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. -- Terry Jan Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: list parameter of a recursive function
Seebs wrote:
> On 2010-10-07, TP wrote:
>> Diez B. Roggisch wrote:
>>> A safer alternative for these cases is using tuples, because they are
>>> immutable.
>
>> 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.
:-) 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)
--
http://mail.python.org/mailman/listinfo/python-list
