I wrote this wrong recursive function that flattens a list:
def flatten(lst, acc=[]): #print 'acc =', acc, 'lst =', lst if type(lst) != list: acc.append(lst) else: for item in lst: flatten(item) return acc
a = [1, 2, [3, 4, 5], [6, [7, 8, [9, 10], 11], 12], 13, 14] b = flatten(a) print b
I was amazed to realize that it flattens the list alright. Why? 'acc' should be an empty list on each invocation of flatten, but is seems to accumulate anyway...
> a = [1, 2, [3, 4, 5], [6, [7, 8, [9, 10], 11], 12], 13, 14] > b = flatten(a) > print b
> I was amazed to realize that it flattens the list alright. Why? 'acc' > should be an empty list on each invocation of flatten, but is seems to > accumulate anyway...
When you say acc=[] in the function declaration, it binds acc to a particular list object, rather than to a concept of an empty list. Thus, all operations being performed on acc are being performed on the same list. If, after the sample code you provided, were to call
c = flatten([15,16,17,[18,19]]) print c
you would get back the list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19].
> > a = [1, 2, [3, 4, 5], [6, [7, 8, [9, 10], 11], 12], 13, 14] > > b = flatten(a) > > print b
> > I was amazed to realize that it flattens the list alright. Why? 'acc' > > should be an empty list on each invocation of flatten, but is seems to > > accumulate anyway...
> When you say acc=[] in the function declaration, it binds acc to a > particular list object, rather than to a concept of an empty list. > Thus, all operations being performed on acc are being performed on the > same list. If, after the sample code you provided, were to call
> c = flatten([15,16,17,[18,19]]) > print c
> you would get back the list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, > 13, 14, 15, 16, 17, 18, 19].
> Mark Sherry
I still don't understand: In each recursive call to flatten, acc should be bound to a new [], shouldn't it? Why does the binding happen only on the first call to flatten?
> > > a = [1, 2, [3, 4, 5], [6, [7, 8, [9, 10], 11], 12], 13, 14] > > > b = flatten(a) > > > print b
> > > I was amazed to realize that it flattens the list alright. Why? 'acc' > > > should be an empty list on each invocation of flatten, but is seems to > > > accumulate anyway...
> > When you say acc=[] in the function declaration, it binds acc to a > > particular list object, rather than to a concept of an empty list. > > Thus, all operations being performed on acc are being performed on the > > same list. If, after the sample code you provided, were to call
> > c = flatten([15,16,17,[18,19]]) > > print c
> > you would get back the list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, > > 13, 14, 15, 16, 17, 18, 19].
> > Mark Sherry
> I still don't understand: In each recursive call to flatten, acc > should be bound to a new [], shouldn't it? Why does the binding happen > only on the first call to flatten?
Default values are bound when the function is defined, not when it's called. For example,
>>> import random >>> def foo(bar = random.random()):
... print bar ...
>>> foo() 0.632312549821312 >>> foo()
0.632312549821312
If you view [...] just as shorthand for list(...), it might make a bit more sense. For immutable values, one can't change the value bound to the name, only what the name is bound to, so this behaviour is less obvious. But still there.
As to why default values are evaluated at define time vs. call time, I'd argue reasons of scope and speed - if the default value is a computed constant, it makes little sense to recompute it every time the function is called.
iu2 wrote: > I still don't understand: In each recursive call to flatten, acc > should be bound to a new [], shouldn't it? Why does the binding happen > only on the first call to flatten?
Nope. In each new call it's (re)bound to the same original list, which you've added to as your function continues--it's mutable. Default variables that are bound to mutable objects are one of the big caveats that is mentioned in the FAQ.
On Jul 16, 2:21 am, Michael Torrie <torr...@gmail.com> wrote:
> iu2 wrote: > > I still don't understand: In each recursive call to flatten, acc > > should be bound to a new [], shouldn't it? Why does the binding happen > > only on the first call to flatten?
> Nope. In each new call it's (re)bound to the same original list, which > you've added to as your function continues--it's mutable. Default > variables that are bound to mutable objects are one of the big caveats > that is mentioned in the FAQ.
On Jul 15, 7:21 pm, Michael Torrie <torr...@gmail.com> wrote:
> iu2 wrote: > > I still don't understand: In each recursive call to flatten, acc > > should be bound to a new [], shouldn't it? Why does the binding happen > > only on the first call to flatten?
> Nope. In each new call it's (re)bound to the same original list, which > you've added to as your function continues--it's mutable. Default > variables that are bound to mutable objects are one of the big caveats > that is mentioned in the FAQ.
Is this avoidable by using a call to list() in the definition instead?
On Jul 16, 1:09 pm, Jeff <jeffo...@gmail.com> wrote:
> On Jul 15, 7:21 pm, Michael Torrie <torr...@gmail.com> wrote:
> > iu2 wrote: > > > I still don't understand: In each recursive call to flatten, acc > > > should be bound to a new [], shouldn't it? Why does the binding happen > > > only on the first call to flatten?
> > Nope. In each new call it's (re)bound to the same original list, which > > you've added to as your function continues--it's mutable. Default > > variables that are bound to mutable objects are one of the big caveats > > that is mentioned in the FAQ.
> Is this avoidable by using a call to list() in the definition instead?
No.
Probably what you'd want to do, is something like this:
def func(arg1, arg2=None): if arg2 is None: arg2 = list()
...
So you create a list at runtime if arg2 has its default value.
Also note that "def" is an executable statement in Python, and that default arguments are evaluated in the "def" statement's environment. If you execute "def" multiple times, it'll create a new function object (with freshly calculated default values) each time.
:::
The workaround is, as others have mentioned, to use a placeholder value instead of modifying the default value. None is a common value:
def myfunc(value=None): if value is None: value = default() # go on an modify value
If you need to handle arbitrary objects (including None), you can use a sentinel object:
sentinel = object()
def myfunc(value=sentinel): if value is sentinel: value = default()
(in older code, written before "object" was introduced, you sometimes see things like "sentinel = ['placeholder']" used to create a non-false object with a unique identity; [] creates a new list every time it is evaluated.)
:::
Finally, it should be noted that more advanced Python code often uses this mechanism to its advantage; for example, if you create a bunch of UI buttons in a loop, you might try something like:
for i in range(10): def callback(): print "clicked button", i UI.Button("button %s" % i, callback)
only to find that all callbacks print the same value (most likely 9, in this case). The reason for this is that Python's nested scopes bind to variables, not object values, so all callback instances will see the current (=last) value of the "i" variable. To fix this, use explicit binding:
for i in range(10): def callback(i=i): print "clicked button", i UI.Button("button %s" % i, callback)
The "i=i" part binds a local variable "i" to the *current* value of the outer variable "i".
Two other uses are local caches/memoization; e.g.
def calculate(a, b, c, memo={}): try: value = memo[a, b, c] # return already calculated value except KeyError: value = do calculation on a, b, c memo[a, b, c] = value # update the memo dictionary return value
(this is especially nice for certain kinds of recursive algorithms)
and, for highly optimized code, local rebinding of global names:
Thanks, that made things very clear. I like that technique for adding memoization via the parameter. That is clever. It would be nice if there were a way to have multiple functions close over a shared local variable in Python, like let-binding in lisp.
On Jul 17, 8:27 am, Jeff <jeffo...@gmail.com> wrote:
> Thanks, that made things very clear. I like that technique for adding > memoization via the parameter. That is clever. It would be nice if > there were a way to have multiple functions close over a shared local > variable in Python, like let-binding in lisp.
