Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > don't understand behaviour of recursive structure

Reply
Thread Tools

don't understand behaviour of recursive structure

 
 
Dan Davison
Guest
Posts: n/a
 
      03-14-2009
I'm new to python. Could someone please explain the following behaviour
of a recursive data structure?

def new_node(id='', daughters=[]):
return dict(id=id, daughters=daughters)

n0 = new_node(id='n0')
n1 = new_node(id='n1')

## Seems OK so far:
n0 # {'id': 'n0', 'daughters': []}
n1 # {'id': 'n1', 'daughters': []}

## Now try to make n1 a daughter of n0:
n0['daughters'].append(n1)

## But that seems to have made something funny happen to n1:
n1 # {'id': 'n1', 'daughters': [{...}]}

## In fact, n1 seems to have become its own daughter
n1['daughters'][0] # {'id': 'n1', 'daughters': [{...}]}

## and grand-daughter, etc etc
n1['daughters'][0]['daughters'][0] # {'id': 'n1', 'daughters': [{...}]}

## These changes to n1 are present in n0 (as I would expect)
n0 # {'id': 'n0', 'daughters': [{'id':'n1', 'daughters': [...]}]}
n0['daughters'][0]['daughters'][0] # {'id': 'n1', 'daughters': [...]}


Why did the append() operation have this effect? Straight assignment
seems to do what I expected, i.e.

n0['daughters'] = [n1]
n1 # still the same {'id': 'n1', 'daughters': []}
n0 # {'id': 'n0', 'daughters': [{'id': 'n1', 'daughters': []}]}

Thanks for any enlightenment,

Dan


~> python --version
Python 2.5.2
~> uname -a
Linux Tichodroma 2.6.27-11-generic #1 SMP Thu Jan 29 19:24:39 UTC 2009 i686 GNU/Linux
Ubuntu 8.10
 
Reply With Quote
 
 
 
 
bieffe62@gmail.com
Guest
Posts: n/a
 
      03-14-2009
On 14 Mar, 17:31, Dan Davison <(E-Mail Removed)> wrote:
> I'm new to python. Could someone please explain the following behaviour
> of a recursive data structure?
>
> def new_node(id='', daughters=[]):
> * * return dict(id=id, daughters=daughters)
>


Most probably, here is the problem : try this instead:

def new_node(id='', daughters=None):
if not daughters: daughters = []
return dict(id=id, daughters=daughters)

This is one of the less intuitive points in python: default values are
evaluated only once,
at 'compile' time I think. So when you call twice 'new_node' without
specifying the daughters
parameters, both dict will have the _same_ list. Hence chaos

In other words, it is exactly as if you wrote:

EmptyList = []
def new_node(id='', daughters=EmptyList):
return dict(id=id, daughters=daughters)

See the problem now? If not try this:

l1 = []
l2 = l1
l1.append(1)
print l2

See now? The same happens inside your 'nodes'.


Ciao
----
FB
 
Reply With Quote
 
 
 
 
MRAB
Guest
Posts: n/a
 
      03-14-2009
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> On 14 Mar, 17:31, Dan Davison <(E-Mail Removed)> wrote:
>> I'm new to python. Could someone please explain the following behaviour
>> of a recursive data structure?
>>
>> def new_node(id='', daughters=[]):
>> return dict(id=id, daughters=daughters)
>>

>
> Most probably, here is the problem : try this instead:
>
> def new_node(id='', daughters=None):
> if not daughters: daughters = []
> return dict(id=id, daughters=daughters)
>
> This is one of the less intuitive points in python: default values are
> evaluated only once,
> at 'compile' time I think. So when you call twice 'new_node' without
> specifying the daughters
> parameters, both dict will have the _same_ list. Hence chaos
>

[snip]
It's not really 'compile' time. 'def' is a _statement_, not a
declaration. Its effect is to create a function and bind it to a name in
the current namespace. Any default parameters are evaluated when the
function is created and they are shared by all the function calls.
 
Reply With Quote
 
Dan Davison
Guest
Posts: n/a
 
      03-14-2009
(E-Mail Removed) writes:

> On 14 Mar, 17:31, Dan Davison <(E-Mail Removed)> wrote:
>> I'm new to python. Could someone please explain the following behaviour
>> of a recursive data structure?
>>
>> def new_node(id='', daughters=[]):
>> * * return dict(id=id, daughters=daughters)
>>

>
> Most probably, here is the problem : try this instead:
>
> def new_node(id='', daughters=None):
> if not daughters: daughters = []
> return dict(id=id, daughters=daughters)
>
> This is one of the less intuitive points in python: default values are
> evaluated only once,
> at 'compile' time I think. So when you call twice 'new_node' without
> specifying the daughters
> parameters, both dict will have the _same_ list. Hence chaos
>
> In other words, it is exactly as if you wrote:
>
> EmptyList = []
> def new_node(id='', daughters=EmptyList):
> return dict(id=id, daughters=daughters)
>
> See the problem now? If not try this:


Yes, that's very clear. Thanks for all the answers on this thread.
Dan

>
> l1 = []
> l2 = l1
> l1.append(1)
> print l2
>
> See now? The same happens inside your 'nodes'.
>
>
> Ciao
> ----
> FB
> --
> http://mail.python.org/mailman/listinfo/python-list

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Recursive functions Vs Non-recursive functions - performance aspect vamsi C Programming 21 03-09-2009 10:53 PM
Two recursive calls inside of a recursive function n00m C++ 12 03-13-2008 03:18 PM
Trying to understand rfc822.Message() behaviour Phoe6 Python 4 11-30-2006 06:44 PM
division... strange behaviour i dont understand clqrq@yahoo.de C++ 10 07-12-2006 07:05 PM
Read all of this to understand how it works. then check around on otherRead all of this to understand how it works. then check around on other thelisa martin Computer Support 2 08-18-2005 06:40 AM



Advertisments