Getting around immutable default arguments for recursion

Discussion in 'Python' started by dpapathanasiou, Jan 14, 2009.

  1. I wrote this function to retrieve a list of items from a dictionary.

    The first time it was called, it worked properly.

    But every subsequent call returned the results of the prior call, plus
    the results of the current call.

    I was confused until I read in the docs that default arguments are
    immutable.

    Is there any way around this, to be able to write recursive functions
    with default arguments?

    Here's the code:

    def get_prior_versions (item_id, priors=[]):
    """Return a list of all prior item ids starting with this one"""
    global history_db # key = item id, value = prior item id
    prior_id = history_db[item_id]
    if not prior_id:
    return priors
    else:
    priors.append(prior_id)
    return get_prior_versions(prior_id, priors)
     
    dpapathanasiou, Jan 14, 2009
    #1
    1. Advertising

  2. dpapathanasiou

    MRAB Guest

    dpapathanasiou wrote:
    > I wrote this function to retrieve a list of items from a dictionary.
    >
    > The first time it was called, it worked properly.
    >
    > But every subsequent call returned the results of the prior call, plus
    > the results of the current call.
    >
    > I was confused until I read in the docs that default arguments are
    > immutable.
    >
    > Is there any way around this, to be able to write recursive functions
    > with default arguments?
    >
    > Here's the code:
    >
    > def get_prior_versions (item_id, priors=[]):


    The usual solution is:

    def get_prior_versions (item_id, priors=None):
    if priors is None:
    priors = []

    > """Return a list of all prior item ids starting with this one"""
    > global history_db # key = item id, value = prior item id
    > prior_id = history_db[item_id]
    > if not prior_id:
    > return priors
    > else:
    > priors.append(prior_id)
    > return get_prior_versions(prior_id, priors)
     
    MRAB, Jan 14, 2009
    #2
    1. Advertising

  3. dpapathanasiou

    James Mills Guest

    On Thu, Jan 15, 2009 at 8:11 AM, dpapathanasiou
    <> wrote:
    > I wrote this function to retrieve a list of items from a dictionary.
    >
    > The first time it was called, it worked properly.
    >
    > But every subsequent call returned the results of the prior call, plus
    > the results of the current call.
    >
    > I was confused until I read in the docs that default arguments are
    > immutable.
    >
    > Is there any way around this, to be able to write recursive functions
    > with default arguments?
    >
    > Here's the code:
    >
    > def get_prior_versions (item_id, priors=[]):
    > """Return a list of all prior item ids starting with this one"""
    > global history_db # key = item id, value = prior item id
    > prior_id = history_db[item_id]
    > if not prior_id:
    > return priors
    > else:
    > priors.append(prior_id)
    > return get_prior_versions(prior_id, priors)


    How about:

    def get_prior_versions (item_id, priors=None):
    """Return a list of all prior item ids starting with this one"""
    global history_db # key = item id, value = prior item id
    prior_id = history_db[item_id]
    if not prior_id:
    return priors
    else:
    if priors:
    priors.append(prior_id)
    else:
    priors = [prior_id]
    return get_prior_versions(prior_id, priors)
     
    James Mills, Jan 14, 2009
    #3

  4. > The usual solution is:
    >
    > def get_prior_versions (item_id, priors=None):
    > if priors is None:
    > priors = []


    Thanks!
     
    dpapathanasiou, Jan 14, 2009
    #4

  5. > How about:
    >
    > def get_prior_versions (item_id, priors=None):
    > """Return a list of all prior item ids starting with this one"""
    > global history_db # key = item id, value = prior item id
    > prior_id = history_db[item_id]
    > if not prior_id:
    > return priors
    > else:
    > if priors:
    > priors.append(prior_id)
    > else:
    > priors = [prior_id]
    > return get_prior_versions(prior_id, priors)


    It's not exactly right for what I'm doing, b/c the caller always
    expects a list in return.
     
    dpapathanasiou, Jan 14, 2009
    #5
  6. dpapathanasiou

    James Mills Guest

    On Thu, Jan 15, 2009 at 8:32 AM, dpapathanasiou
    <> wrote:
    (...)

    > It's not exactly right for what I'm doing, b/c the caller always
    > expects a list in return.


    How about this then:

    def get_prior_versions (item_id, priors=None):
    """Return a list of all prior item ids starting with this one"""
    global history_db # key = item id, value = prior item id
    prior_id = history_db[item_id]
    if not prior_id:
    if priors:
    return priors or []
    else:
    if priors:
    priors.append(prior_id)
    else:
    priors = [prior_id]
    return get_prior_versions(prior_id, priors)

    By the way, this is a really badly
    written function for 2 reasons:

    a) a global should and need not be used.
    b) this function could be rewritten without recursion.

    cheers
    James
     
    James Mills, Jan 14, 2009
    #6

  7. > You'll continue to be confused if you use that term. Python already
    > has a specific use of the term “immutable”, and it doesn't apply
    > here.


    I was just following the terminology used in "A Byte of
    Python" (which, that particular point aside, is a very good tutorial).

    > Better to say: default arguments are part of the function definition
    > statement, and are evaluated when the definition is evaluated.


    Yes, well said.
     
    dpapathanasiou, Jan 14, 2009
    #7

  8. > How about this then:
    >
    > def get_prior_versions (item_id, priors=None):
    > """Return a list of all prior item ids starting with this one"""
    > global history_db # key = item id, value = prior item id
    > prior_id = history_db[item_id]
    > if not prior_id:
    > if priors:
    > return priors or []
    > else:
    > if priors:
    > priors.append(prior_id)
    > else:
    > priors = [prior_id]
    > return get_prior_versions(prior_id, priors)


    Without the "if priors:" line just above the first return statement (a
    typo perhaps?), then yes, it would do what I want.

    > a) a global should and need not be used.


    Passing the entire dictionary to every function that accesses it is
    better?

    > b) this function could be rewritten without recursion.


    Right, any recursive function can be written iteratively and vice-
    versa. I'm not sure that makes it "bad".
     
    dpapathanasiou, Jan 14, 2009
    #8
  9. dpapathanasiou

    James Mills Guest

    On Thu, Jan 15, 2009 at 9:27 AM, dpapathanasiou
    <> wrote:
    > Without the "if priors:" line just above the first return statement (a
    > typo perhaps?), then yes, it would do what I want.


    Yes sorry it was :)

    >> a) a global should and need not be used.

    >
    > Passing the entire dictionary to every function that accesses it is
    > better?


    Yes :)

    >> b) this function could be rewritten without recursion.

    >
    > Right, any recursive function can be written iteratively and vice-
    > versa. I'm not sure that makes it "bad".


    No it doesn't necessarily make it bad,
    but recursion is not necessary here :)

    What does history_db look like ? I think
    I can write a much simpler function for you.

    Also, show me what the results are used for.

    cheers
    James
     
    James Mills, Jan 14, 2009
    #9
  10. On Wed, 14 Jan 2009 15:27:01 -0800, dpapathanasiou wrote:

    >> a) a global should and need not be used.

    >
    > Passing the entire dictionary to every function that accesses it is
    > better?


    Yes. There is very little overhead when passing objects to functions in
    Python. There's no performance penalty to passing objects instead of
    relying on globals, and it may in fact be marginally faster:


    >>> D = {'parrot': None}
    >>>
    >>> def byargument(d):

    .... return d
    ....
    >>> def byglobal1():

    .... return D
    ....
    >>> def byglobal2():

    .... global D
    .... return D
    ....
    >>>
    >>> from timeit import Timer
    >>> setup = "from __main__ import byargument, byglobal1, byglobal2, D"
    >>> t1 = Timer('result = byargument(D)', setup)
    >>> t2 = Timer('result = byglobal1()', setup)
    >>> t3 = Timer('result = byglobal2()', setup)
    >>>
    >>> min(t1.repeat())

    0.23665285110473633
    >>> min(t2.repeat())

    0.23789191246032715
    >>> min(t3.repeat())

    0.23757314682006836




    --
    Steven
     
    Steven D'Aprano, Jan 15, 2009
    #10
  11. dpapathanasiou

    alex23 Guest

    dpapathanasiou <> wrote:
    > Passing the entire dictionary to every function that accesses it is
    > better?


    If there are a large number of functions, you could combine them and
    the history_db dict into a single object.
     
    alex23, Jan 15, 2009
    #11
    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. Edward Diener
    Replies:
    14
    Views:
    5,125
    Josiah Carlson
    Apr 6, 2004
  2. Piet
    Replies:
    0
    Views:
    599
  3. tutmann
    Replies:
    4
    Views:
    460
  4. Network/Software Buyer
    Replies:
    0
    Views:
    442
    Network/Software Buyer
    May 23, 2010
  5. Replies:
    8
    Views:
    802
    John Reye
    Apr 26, 2012
Loading...

Share This Page