Efficient implementation of deeply nested lists

[Kay Schluehr]

Bengt Richter wrote:
> On 19 Jan 2006 01:19:06 -0800, "Kay Schluehr" <kay.schluehr at gmx.net> 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?
> >
> Make a custom class factory that makes a class with a1..aN and can be instantiated
> with x, producing an object that behaves like L

Hi Bengt,

I made such an attempt already yesterday but I disliked the result
because the __getitem__ method of the class that encapsulated a1...aN
worked as an object factory that was as expensive as list creation. My
second try is much cheaper and shifts only references:

def BinList(flat):
    proto = None

    class _BinList(object):
        def __init__(self, x=None):
            self.x = x
            if proto:
                self.first = proto.first
                self.next  = proto.next

        def _nest(self, lst):
            self.first = lst.pop(0)
            self.next  = None
            if lst:
                self.next = _BinList()
                self.next._nest(lst)

        def __getitem__(self, i):
            if i==0:
                return self.first
            elif i==1:
                if self.next:
                    self.next.x = self.x
                    return self.next
                else:
                    return self.x
            else:
                raise IndexError,i

        def __repr__(self):
            if self.next is None:
                return "[%s, %s]"%(self.first,self.x)
            else:
                return "[%s, %s]"%(self[0], self[1])

    # instantiate prototype
    bl = _BinList()
    bl._nest(flat)
    proto = bl
    return _BinList


>>> A = BinList([1,2,3])
>>> a0 = A(7)
>>> a1 = A(9)
>>> a0
[1, [2, [3, 7]]]
>>> a1
[1, [2, [3, 9]]]


> So the question in my mind is, how are you actually going to use these "L" things?

The "L" things are fragments of listified Python parse trees ;)

> 
> Regards,
> Bengt Richter

Regards too,
Kay