Efficient implementation of deeply nested lists

Fuzzyman fuzzyman at gmail.com
Thu Jan 19 06:15:09 EST 2006

Kay Schluehr wrote:
> I want to manipulate a deeply nested list in a generic way at a
> determined place. Given a sequence of constant objects a1, a2, ..., aN
> and a variable x. Now construct a list from them recursively:
> L = [a1, [a2, [....[aN, [x]]...]]
> The value of x is the only one to be changed. With each value of x a
> new instance of L is needed so that we actually have a function:
> L = lambda x: [a1, [a2, [....[aN, [x]]...]]
> I'm seeking for an efficient implementation that does not recompute the
> whole list each time. Any ideas?

Is the sequence of a1 to aN fixed ?

I assume you want a new list each time ?

You can create a reference list once but keep a reference to the most
deeply nested part that contains x.

Each time you need a new copy, insert hte new value of x and use
copy.deepcopy to produce your new list.


def listmaker(consts, x):
    global finalref
    out = []
    if not consts:
        finalref = [x]
        return finalref
    entry = consts.pop()
    out.append(listmaker(consts, x))
    return out

listmaker recursively builds the list structure and creates a global
reference to the list holding x.

You can build this once as a 'generic' list.

When you need a copy do :

del finalref[0]

newlist = copy.deepcopy(reference_list)

I hope that helps, it may need debugging. :-)

Because lists are mutable, you can't avoid the copy operation - but it
is *probably* quicker than recomputing hte list. You should test this -
as it might not be the case.


> Kay

More information about the Python-list mailing list