> > def flatten(a):> > if not isinstance(a,(tuple,list)): return [a]> > if len(a)==0: return > > return flatten(a)+flatten(a[1:])> The only problem with this if it is to big or to deeply nested then it> will overflow the stack?
Yes, it can overflow in its current incarnation. There is a way to fix
[WARNING WARNING: The code presented below is very evil, but I just can't
Please do not try to understand the code below, as it is not meant to be
read by humans. If you are just learning Python, please skip this
There's a way to systematically transform it so that it doesn't overflow,
by using "trampolining-style" programming. This technique turns any
recursive function into one that only consumes a constant amount of stack
It's used by programming language theory folks, despite being utterly
weird. *grin* I think I wrote a brief introduction to the topic on
Python-Tutor list, and have also applied it in a small project (PyScheme).
For your (or my?) amusement, here's the transformed flatten() function in
"""Flatten a list."""
return bounce(flatten_k(a, lambda x: x))
"""Bounce the 'thing' until it stops being a callable."""
thing = thing()
def flatten_k(a, k):
"""CPS/trampolined version of the flatten function. The original
function, before the CPS transform, looked like this:
if not isinstance(a,(tuple,list)): return [a]
if len(a)==0: return 
The following code is not meant for human consumption.
if not isinstance(a,(tuple,list)):
return lambda: k([a])
return lambda: k()
return lambda: k(v1 + v2)
return lambda: flatten_k(a[1:], k2)
return lambda: flatten_k(a, k1)
This actually does something useful.
>>> flatten([1, [2, [3, 4]]])
[1, 2, 3, 4]
Best of all, it does not stack-overflow. We can test this on an evil
>>> def makeEvilList(n):
... result = 
... for i in xrange(n):
... result = [[result], i]
... return result
>>> evilNestedList = makeEvilList(sys.getrecursionlimit())>>> assert range(sys.getrecursionlimit()) == flatten(evilNestedList)>>>
And it does work.
That being said, "trampolined-style" is just evil in Python: I would not
want to inflict that code on anyone, save in jest. *grin*