> > def flatten(a):
> > if not isinstance(a,(tuple,list)): return [a]
> > if len(a)==0: return []
> > return flatten(a[0])+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
that.
[WARNING WARNING: The code presented below is very evil, but I just can't
resist. *grin*
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
message.]
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
space.
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
trampolined style:
###
def flatten(a):
"""Flatten a list."""
return bounce(flatten_k(a, lambda x: x))
def bounce(thing):
"""Bounce the 'thing' until it stops being a callable."""
while callable(thing):
thing = thing()
return thing
def flatten_k(a, k):
"""CPS/trampolined version of the flatten function. The original
function, before the CPS transform, looked like this:
def flatten(a):
if not isinstance(a,(tuple,list)): return [a]
if len(a)==0: return []
return flatten(a[0])+flatten(a[1:])
The following code is not meant for human consumption.
"""
if not isinstance(a,(tuple,list)):
return lambda: k([a])
if len(a)==0:
return lambda: k([])
def k1(v1):
def k2(v2):
return lambda: k(v1 + v2)
return lambda: flatten_k(a[1:], k2)
return lambda: flatten_k(a[0], 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
constructed example:
###
>>> 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*
_______________________________________________
Tutor maillist - [email protected]
http://mail.python.org/mailman/listinfo/tutor
