bad recursion, still works

[iu2]

Hi,

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...

[mdsherry]

On Jul 15, 2:59*pm, iu2 <[e-mail]:

Hi,

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...

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

[iu2]

On Jul 15, 9:30*pm, [e-mail] wrote:

On Jul 15, 2:59*pm, iu2 <[e-mail]:

Hi,

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...

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?

[mdsherry]

On Jul 15, 4:12*pm, iu2 <[e-mail]:

On Jul 15, 9:30*pm, [e-mail] wrote:

On Jul 15, 2:59*pm, iu2 <[e-mail]:

Hi,

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...

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.

Mark Sherry

[Michael Torrie]

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.

[iu2]

On Jul 16, 2:21*am, Michael Torrie <[e-mail]:

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.

Thanks guys, it's clear now