Get list of values from a nested Python data-structure using a list comprehension?

Question

in calculating a longest increasing subsequence using patience sorting I create a nested tuple of (value, backlink) pairs that I then need to crawl to get all the values in order. Currently I use a small function to do this but was wondering if there was a way to use a list comprehensions to do the same thing.

The example uses a namedtuple as in my original program and should illustrate my issue:

>>> from collections import namedtuple
>>> P = namedtuple('P', 'val, back')
>>> q = P(val=15, back=P(val=11, back=P(val=9, back=P(val=6, back=P(val=2, back=P(val=0, back=None))))))
>>> q
P(val=15, back=P(val=11, back=P(val=9, back=P(val=6, back=P(val=2, back=P(val=0, back=None))))))
>>> #Request something like:
>>> [val for val, q in q]
Traceback (most recent call last):
  File "<pyshell#68>", line 1, in <module>
    [val for val, q in q]
  File "<pyshell#68>", line 1, in <listcomp>
    [val for val, q in q]
TypeError: 'int' object is not iterable
>>> q
P(val=15, back=P(val=11, back=P(val=9, back=P(val=6, back=P(val=2, back=P(val=0, back=None))))))
>>> # Wanted: [15, 11, 9, 6, 2, 0]
>>> 
>>> # Have to use:
>>> def _unwind(q):
    u = []
    while q:
        u.append(q.val)
        q = q.back
    return u

>>> q
P(val=15, back=P(val=11, back=P(val=9, back=P(val=6, back=P(val=2, back=P(val=0, back=None))))))
>>> _unwind(q)
[15, 11, 9, 6, 2, 0]
>>>

I was looking for some way of setting P up so I could write something like:

[val for val, q in q]

Maybe by overriding P.__iter__ and P.__next__ in some way to elegantly redefine the iter protocol for P?

falsetru · Accepted Answer · 2013-08-17 07:20:37Z

2

Try following:

>>> from collections import namedtuple
>>>
>>> class P(namedtuple('_P', 'val back')):
...     def __iter__(self):
...         while self:
...             yield self.val, self.back
...             self = self.back
...
>>> q = P(val=15, back=P(val=11, back=P(val=9, back=P(val=6, back=P(val=2, back=P(val=0, back=None))))))
>>> [val for val, back in q]
[15, 11, 9, 6, 2, 0]

answered Aug 17, 2013 at 7:20

falsetru

371k69 gold badges770 silver badges660 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Get list of values from a nested Python data-structure using a list comprehension?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related