| Store | Cart

[Tutor] flattening a list

From: Danny Yoo <d...@hkn.eecs.berkeley.edu>
Thu, 13 Jan 2005 07:15:35
> > 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*

Recent Messages in this Thread
Chad Crabtree Jan 13, 2005 03:28 am
Danny Yoo Jan 13, 2005 07:15 am
Gonšalo Rodrigues Jan 13, 2005 02:00 pm
Messages in this thread