Velocity Reviews > don't understand behaviour of recursive structure

# 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

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

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.

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