Idiom for flattening a shallow nested list: how does it work?

Question

I found this bit of code in a module I am working on:

l = opaque_function()
thingys = [x for y in l for x in y]

I can't read this. By experiment, I was able to determe that it is flattening a 2-level nested list, but the syntex is still opaque to me. It has obviously omitted some optional brackets.

>>> l = [[1,2],[3,4]]
>>> [x for y in l for x in y]
[1, 2, 3, 4]

My eyes want to parse it as either: [x for y in [l for x in y] ] or [ [x for y in l] for x in y ], but both of those fail due to y not being defined.

How should I be reading this?

(I suspect I will feel very embarassed when this is explained.)

Possible duplicate: http://stackoverflow.com/questions/406121/flattening-a-shallow-list-in-python http://stackoverflow.com/questions/120886/python-idiom-to-chain-flatten-an-infinite-iterable-of-finite-iterables http://stackoverflow.com/questions/457215/comprehension-for-flattening-a-sequence-of-sequences — Nadir Sampaoli, Sep 25 '12 at 15:09
thanks for asking this. i've been using this idiom for a long time, and have always wondered 'why does this work?' — Jonathan Vanasco, Mar 01 '13 at 22:44

score 6 · Answer 1 · answered Sep 25 '12 at 15:10

6

This used to really confuse me. You should read it like a nested loop:

new_list = []
for y in l:
    for x in y:
        new_list.append(x)

becomes

for y in l for x in y [do] new_list.append(x)

becomes

[x for y in l for x in y]

answered Sep 25 '12 at 15:10

DSM

342,061
65
592
494

Fred Foo · Answer 2 · 2012-09-25T15:22:09.970

You should read this as:

for y in l:
    for x in y:
        yield x

That's the generator version, but all comprehensions have the same basic syntax: while the x is put up front, the rest of the expression is still read left-to-right. I was confused by this at first too, expecting it to be the other way around, but it makes sense once you add filtering expressions:

>>> l = [[1,2,3,4,5], [1,"foo","bar"], [2,3]]
>>> [x for y in l
...    if len(y) < 4
...    for x in y
...    if isinstance(x, int)]
[1, 2, 3]

Now imagine having to write this entire thing backwards:

[x if isinstance(x, int)
   for x in y
   if len(y) < 4
   for y in l]

That would be confusing even to veteran Prolog programmers, not to mention the people maintaining Python parsers :)

The current syntax also matches that in Haskell, which inspired list comprehensions in the first place.

score 5 · Accepted Answer · answered Sep 25 '12 at 15:15

From the list displays documentation:

When a list comprehension is supplied, it consists of a single expression followed by at least one for clause and zero or more for or if clauses. In this case, the elements of the new list are those that would be produced by considering each of the for or if clauses a block, nesting from left to right, and evaluating the expression to produce a list element each time the innermost block is reached.

Thus, your expression can be rewritten as:

thingys = []
for y in l:
    for x in y:
        thingys.append(x)

Wow, I did not know that multiple `for` clauses were allowed. And here I thought I was the local python expert. Thanks. — Matthew Scouten, Sep 25 '12 at 18:21

score 1 · Answer 4 · answered Sep 25 '12 at 15:10

1

lis=[x for y in l for x in y] is Equivalent to:


lis=[]
for y in l:
   for x in y:
      lis.append(x)

answered Sep 25 '12 at 15:10

Ashwini Chaudhary

244,495
58
464
504

Idiom for flattening a shallow nested list: how does it work?

4 Answers4

Linked