Why does this work?


#1

n = [[1, 2, 3], [4, 5, 6, 7, 8, 9]]

Add your function here

def flatten(lists):
results = []
for numbers in lists:
for i in numbers:
results.append(i)
return results

print flatten(n)

I looked up a walkthrough and I'm confused why this works? Can anyone tell me?


#2

The outer loop iterates over the two contained lists, the inner loop iterates over each list, in turn, then appends the value to a flat list.


#3

I used this:

def flatten(lists):
    results = []
    for numbers in lists:
        for number in numbers:
        results.append(number)
return results

print flatten(n)

Does anyone know how to do this better without knowing first that there are lists inside lists? Or better, how many lists are inside other lists (1 deep in this case)?
Would I have to use an if check for this?


#4

Since we begin with the assumption that the contents of a list are unknown, and we don't know how many layers there are, then we can conclude some form of recursive function will be needed. Unfortunately, that's where I bow aside. I can picture it, but not write it, just now.


#5

Be warned, this may take some time to sink in. But there are many problems that fit this pattern, and once used to this way of thinking (takes even more time) it is actually very simple and powerful.

We are going to write a function flatten that flattens an arbitrarily deeply nested list.

This means that when the function is done, it can use itself.

Therefore, when iterating through a nested list, we can use flatten to flatten it, and add that flat list to our result. Non-list values are added to the result without modification:

def flatten(lst):
    result = []
    loop through lst
        if the element is a list, flatten(elem) and put the values in result
        otherwise the element is non-list and should be added as-is
    return result

What will happen is that each time it encounters a list, it will call itself with that list as the argument. That argument will have 1 less nesting level. Which means that eventually we come to the situation where we have an already flat list. If we look at the code above we see that such a list would simply be copied and our function returns. Because it returned, it will allow the previous call to return as well because it flattened all its lists. Which in turn allows the previous to finish and so on, until the whole list is flat.

So in general:
1) Split up the problem into less complex problems. They must eventually reach a trivial case.
2) Assemble the results to solve the current problem.
3) Make sure that the trivial cases are solved without recursion.

How the above corresponds to flatten:
1) Call flatten for each sub-list, which will each be 1 depth less
2) Add each value to result after flattening / add non-list values to result
3) A flat list gets copied and then returned, which then allows the rest to be solved.

Some more help in getting this to sink in:

Read the above code. Just assume that the flatten call will do what it's supposed to without considering why it does.
Convince yourself of that with that assumption, the correct result will be produced.

Convince yourself of that the depth of the lists is reduced by 1 every time flatten is called, and that this eventually leads to flat lists only.

Convince yourself of that flat lists cause flatten to return without recursion.

Convince yourself of that every time flatten runs, everything is split up into simpler problems that will eventually be solved, the problem will never grow, it will only shrink, and never get stuck, therefore the whole thing will get solved.


#6

I couldn't make heads or tails on how to do it the way CodeAcademy intended, so I ended up doing it my own way. It avoids taking a for loop within a for loop, but also avoids appending and creating an extra variable.

Is this a coincidental way to do this or something that would be applicable to more than just this particular, 2-list question?


#7

This takes advantage of Python's ability to concatenate two lists. It's probably the slowest method for doing this. results.append() is faster, as is results.extend(). The nested loop approach would be the slowest of all, most likely, but it doesn't hurt to be able to write and understand how it works. Seeing the basic mechanics often helps us get a better understanding of the abstracted methods for performing the same function.


#8

@ionatan Thank you for your reply. I still struggle with the concept of a function calling itself from within. I somehow think that the function might (and does, if the lists are nested) call itself before it's finished running for the first time. I don't know why this works. but I understand the concept.