don't understand behaviour of recursive structure

Discussion in 'Python' started by Dan Davison, Mar 14, 2009.

  1. Dan Davison

    Dan Davison Guest

    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
    Dan Davison, Mar 14, 2009
    #1
    1. Advertising

  2. Dan Davison

    Guest

    On 14 Mar, 17:31, Dan Davison <> 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
    , Mar 14, 2009
    #2
    1. Advertising

  3. Dan Davison

    MRAB Guest

    wrote:
    > On 14 Mar, 17:31, Dan Davison <> 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.
    MRAB, Mar 14, 2009
    #3
  4. Dan Davison

    Dan Davison Guest

    writes:

    > On 14 Mar, 17:31, Dan Davison <> 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
    Dan Davison, Mar 14, 2009
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Nikko
    Replies:
    1
    Views:
    484
    Harry
    Apr 30, 2007
  2. n00m
    Replies:
    12
    Views:
    1,101
  3. vamsi
    Replies:
    21
    Views:
    2,048
    Keith Thompson
    Mar 9, 2009
  4. Kushal Kumaran
    Replies:
    0
    Views:
    569
    Kushal Kumaran
    Apr 1, 2011
  5. Russel Walker
    Replies:
    9
    Views:
    110
    Russel Walker
    Jul 7, 2013
Loading...

Share This Page