Flattening list of list using other technique

Question

I am trying to understand this code for flattening list:

def flatten(iterable):
    """Recursively iterate lists and tuples.
    """
    for elm in iterable:
        if isinstance(elm, (list, tuple)):
            for relm in flatten(elm):
                yield relm
        else:
            yield elm here

Source: Making a flat list out of a multi-type nested list

However I am not able to understand recursive statement and how control is flowing. Specially these two lines:

   for relm in flatten(elm):
            yield relm

Can I get gist of how recursive is working at every iteration, that would be a great help.

And Can we use some other approch to do this problem?

score 1 · Answer 1 · answered Mar 23 '18 at 14:47

1

(I deleted my comment and posted is as answer, because my edit was too long.)

The flow control is as follows:

iterable is the nested list you have at the beginning,
the for and later if differentiates if the elm (element from iterable) is a list or tuple type,
if yes, then the statement under if makes the recurrence happen and the elm becomes new iterable,

...this happens for every element inside the main list until the elm isn't list or tuple

the function returns generator object, so to get to all outputs you have to call a list on it.

What you also can do, is adding print statements to see what is happening; for example:

def flatten(iterable):
    for elm in iterable:
        if isinstance(elm, (list, tuple)):
            print(elm)
            for relm in flatten(elm):
                yield relm
        else:
            print(elm)
            yield elm

If we input a = [1, 2, 3,[[4, 5], 5, (1, 2, 3)], 2] and say list(flatten(a)) we get:

1
2
3
[[4, 5], 5, (1, 2, 3)]
[4, 5]
4
5
5
(1, 2, 3)
1
2
3
2

This way we can see, what the function was working on in every step.

answered Mar 23 '18 at 14:47

Sqoshu

944
2
9
16

In your example when flatten() is called on elm=[4, 5] then iterable is replaced by elm... Then how flatten() keeps track of [5, (1, 2, 3)] rest elements. In this line: for relm in flatten(elm): – DreamerP Mar 23 '18 at 15:13
1

It keeps track of rest of the elements because of `for elm in iterable:`. The recursion happens for current element, until it is exhausted. Then the `for` continues.I think you can try to modify it further to see when the recursion is "inside" a nested list adding more `print` statements. – Sqoshu Mar 23 '18 at 15:15
Can you show it in a flow diagram. I am sorry if it's too much to ask but this will help me to understand better. – DreamerP Mar 23 '18 at 15:19
1

https://imgur.com/a/Q5GOO It's not the best, especially the second if, but maybe it will help you. – Sqoshu Mar 27 '18 at 14:47
Thanks. Wonderful Solution!! – DreamerP Mar 27 '18 at 16:17

score 1 · Accepted Answer · answered Mar 23 '18 at 15:58

Iterate protocol

In python there is such a key concept as iteration protocol. Iteration protocol is used every time you:

Use a for loop
Unpack/pack a tuple
Use list comprehension
Yield any value

Basically iteration protocol is used every time you want to process some sequence of data. Let's use list creation as example. Whenever you call:

my_list=list(x)

Python interpreter is calling __next__ method on x and then adding result to end of result list (which is empty at the beginning). And it stops when next(x) throws StopIteration.

So what with this yields?

Yield is pretty similar to return but it does not terminate the function. Result of the function with yields inside is generator. Generators implements __next__ method and they can be used in iterate protocol. Let's look at this function:

def gen():
    yield 1
    yield 2
    yield 3

This function will be generator and it will behave like this:

>>>gen()
<generator object a at 0x0000000002A1EAF0>
>>>list(gen())
[1,2,3]
>>>i=gen()
>>>next(i)
1
>>>next(i)
2
>>>next(i)
3
>>>next(i)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

So every time you call next(i) python only execute code till next yield and returns it's value. If you want to learn more about it I recommend this lecture or answers to this question.

P.S

Instead of this lines:

for relm in flatten(elm):
            yield relm

you can use:

yield from flatten(elm)

Flattening list of list using other technique

2 Answers2

Iterate protocol

So what with this yields?

P.S