Recursively flatten nested list in python

Question

I am playing around a bit with generators in Python, and am trying to make use of a simple recursive scheme to implement a flatten-function. That is, a function that takes as input a list that may contain sublists, and outputs a iterable objects that iterates only over the atomic elements of the input.

So, print(list(flatten([1,2,3,[4,5,6]]))) should return something containing [1,2,3,4,5,6].

My attempt is as follows:

def flatten(toflatten):
    try:
        for element in toflatten:
            flatten(element)
    except TypeError:
        yield toflatten

So, it should check whether its argument is an iterable object. If this is the case, also recurse over this object. Else, yield it as an atomic element.

This does not work and flatten([1,2,3,[4,5,6]]) merely returns an empty list.

Why is this the case? And in particular; why is it not even performing the recursive function calls on this input? (I am using Python 3.5)

First of all, what do you expect `flatten(element)` to do? This line does not return/yield anything and does not mutate any data structure, so it's pointless. — timgeb, Jan 15 '18 at 11:30
I know this will not be helpful if your end goal is to learn recursion but try `sum(yourlist,[])` this will flatten your list. I would recommend returning a your list at the end. — Tomos Williams, Jan 15 '18 at 11:30
@timgeb ahh you're right! that's just the trick I tend to use when flattening lists — Tomos Williams, Jan 15 '18 at 11:33
Id expect it to either yield its atomic values or apply flatten on its sublists. I don't really get why it does not 'yield' the atomic values of, say, [1,2,3]. (say we doing something like: for x in flatten([1,2,3]): print(x) ) — ChuckSchuldiner, Jan 15 '18 at 11:33
@ChuckSchuldiner consider the function `foo(x): return 2*x`. Why would you expect a line that just contained `foo(x)` to be useful? The input parameter is not mutated and you don't use the result. — timgeb, Jan 15 '18 at 11:36
@timgeb Ah, I see what you mean now! Thanks (to all) for your comments. I was assuming that the yield-statements in the recursive function-call would transfer to the lower recursion level. So apparently this is not the case. Is there an elegant way of fixing this? — ChuckSchuldiner, Jan 15 '18 at 11:42
By the way, [here](https://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists) is the canonical "flatten nested lists" question. I didn't close as a duplicate because this one seems more about why the specific code does not work. — timgeb, Jan 15 '18 at 15:48

cs95 · Accepted Answer · 2018-01-15T11:44:49.207

So, you're trying to flatten a list. You're on the right track but you've made a couple of mistakes. Here they are.

Move your try-except inside the loop. With your code, if a TypeError is raised for one element, then the loop stops running. You don't want that happening.
In the try, you yield nothing. Only making a function call. You should be returning something from there as well. I'd recommend yield from if you have python3.3+.
Finally, in the except, you need to yield element, not toflatten. Don't yield the entire list.

def flatten(toflatten):    
   for element in toflatten:
       try:
           yield from flatten(element)
       except TypeError:
           yield element

This gives,

>>> list(flatten([1,2,3,[4,5,6]]))
[1, 2, 3, 4, 5, 6]

You've used the EAFP (Easier to Ask Forgiveness, than Permission), which is nice. That's one way to do it (my favourite, actually), but there's a drawback: This crashes on strings.

There's another approach: LYBL (Look Before You Leap). It consists of being more cautious, using if statements so errors are not raised.

def flatten(toflatten):    
   for element in toflatten:
       if isinstance(element, list):
           yield from flatten(element)
       else:
           yield element

Which works the same as before, and gives,

>>> list(flatten([1,2,3,[4,5,6]]))
[1, 2, 3, 4, 5, 6]

However, this is advantageous, in the fact that the yield from generator delegation is only invoked upon sub-lists. Did I mention it also works with string elements?

>>> list(flatten([1,2,3,[4,5,'abc']]))
[1, 2, 3, 4, 5, 'abc']

Note that in either case, the caveat of infinite recursion, if you have recursively defined lists. For example, flatten will crash with this sort of input.

x = [1, 2, 3]
x.append(x)

flatten(x)

You'll end up getting a runtime error:

RuntimeError: maximum recursion depth exceeded

You may also want to consider "unwanted" iterables such as strings and if you are particularly picky the possibility of a recursive `toflatten` iterable. (e.g. `toflatten = []; toflatten = [toflatten]`) — timgeb, Jan 15 '18 at 11:38
@timgeb Mentioned that EAFP fails with strings, and both fail with recursive lists. Thanks for the comments! — cs95, Jan 15 '18 at 11:46
Awesome, all problems solved, thanks a lot! (I was not yet familiar with the yield-from statement, this is exactly what I was looking for) — ChuckSchuldiner, Jan 15 '18 at 11:47

Recursively flatten nested list in python

1 Answers1

Linked