Flattening a list that contains lists of tuples, letters and integers

Question

I need to flatten a list recursively:

Before the list looks like:

L=[1,[2,[‘a’,(3,’b’)]],(5,6),([11,22])]

After:

Lflat=[1,2,’a’,(3,’b’),(5,6),([11,22])]

I've come across an issue with my code (lst1 is an empty lst1)

def list_flatten(lst,lst1):
    for item in lst:
        if type(item) == tuple:
            print(item)
            lst1.append(item)
        elif type(item) == list:
            list_flatten(item,lst1)
        else:
            lst1.append(item)
    return lst1

This returns the following:

OUTPUT : [1, 2, 'a', (3, 'b'), (5, 6), 11, 22]

Which lead me to find out that ([]) is considered a list, not a tuple.

Now my questions are as following:

Say I were to define lst1=[] inside the main program. How do I make it so the recursion doesn't empty the list out every iteration?
Why is ([]) considered a list?

`([])` is a list because a [tuple consists of a number of values separated by commas](https://docs.python.org/2/tutorial/datastructures.html#tuples-and-sequences), and there are no commas here. In this case, the parentheses are just forcing the evaluation of what's *inside* the parentheses, which is a list. — David Zemens, Jan 23 '17 at 14:30
@DavidZemens True, but the function mutates `lst1`, so it really doesn't need to return anything. — PM 2Ring, Jan 23 '17 at 14:41
I don't understand your question #1. The recursion _doesn't_ "empty the list out every iteration", it passes `lst1` to the recursive call with its contents intact. — PM 2Ring, Jan 23 '17 at 14:45
@PM2Ring If I were to add lst1= [] inside of the fucntion instead of calling a list from outside of the function, it would keep trample over the list every recursion run — RonaldB, Jan 23 '17 at 14:48

score 2 · Answer 1 · edited May 23 '17 at 12:33

Your list_flatten function mutates the lst1 argument, so you don't really need to return anything. You can call it like this:

L = [1,[2,['a',(3,'b')]],(5,6),([11,22])] 

def list_flatten(lst, lst1):
    for item in lst:
        if isinstance(item, list):
            list_flatten(item, lst1)
        else:
            lst1.append(item)

Lflat = []
list_flatten(L, Lflat)
print(Lflat)

output

[1, 2, 'a', (3, 'b'), (5, 6), 11, 22]

It's recommended to use isinstance rather than type because that makes the code more versatile: it will also work with objects derived from list.

We can re-write the function so that you don't need to pass in lst1:

def list_flatten(lst, lst1=None):
    if lst1 is None:
        lst1 = []
    for item in lst:
        if isinstance(item, list):
            list_flatten(item, lst1)
        else:
            lst1.append(item)
    return lst1

Lflat = list_flatten(L)
print(Lflat)

We give lst1 a default value of None and on the top level of the recursion we re-bind the name lst1 to an empty list to collect the results.

We can't give lst1 a default value of []. That's because default args are created when the function is compiled, not when the function is called, and if we gave lst1 a default value of [] that same list would get used on every call. It would look like it does what we want the first time we used list_flatten, but it would not behave as desired on subsequent calls. Here's a short demo.

L = [1,[2,['a',(3,'b')]],(5,6),([11,22])] 

def list_flatten(lst, lst1=[]):
    for item in lst:
        if isinstance(item, list):
            list_flatten(item, lst1)
        else:
            lst1.append(item)
    return lst1

Lflat = list_flatten(L)
print(Lflat)
Lflat = list_flatten(L)
print(Lflat)

output

[1, 2, 'a', (3, 'b'), (5, 6), 11, 22]
[1, 2, 'a', (3, 'b'), (5, 6), 11, 22, 1, 2, 'a', (3, 'b'), (5, 6), 11, 22]

As you can see, lst1 has retained its contents from the first call. For more info on this important topic, please see “Least Astonishment” and the Mutable Default Argument. There are times when this behviour is desirable, but in such cases it's wise to add a comment to your code that you're intentionally using a mutable default argument.

Yet another way is to make list_flatten into a generator, and collect its output into a list:

def list_flatten(lst):
    for item in lst:
        if isinstance(item, list):
            yield from list_flatten(item)
        else:
            yield item

Lflat = list(list_flatten(L))
print(Lflat)

In recent versions of Python you can replace list(list_flatten(L)) with [*list_flatten(L)].

Python 2 doesn't have yield from, but you can replace that line with:

for u in list_flatten(item):
    yield u

If you don't actually need the list you can call the generator like this:

for u in list_flatten(L):
    print(u)

output

1
2
a
(3, 'b')
(5, 6)
11
22

score 2 · Answer 2 · answered Jan 23 '17 at 16:04

You can note that what you need is:

if the list is empty, return it unchanged
if it has one single element and that element is not a list, return the list unchanged
else flatten first element, flatten the end of the list and concatenate the two sublists

In Python code, it leads to:

def flatten(L):
    if len(L) == 0: return L
    elif len(L) == 1 and not isinstance(L[0], list): return L
    else:
        return (flatten(L[0] if isinstance(L[0], list)
                else [L[0]]) + flatten(L[1:]))

it gives as expected:

>>> L = [1, 2, 'a', (3, 'b'), (5, 6), ([11, 22],)]
>>> flatten(L)
[1, 2, 'a', (3, 'b'), (5, 6), ([11, 22],)]

Flattening a list that contains lists of tuples, letters and integers

2 Answers2

Linked