Flattening a list recursively

Question

I am trying to flatten lists recursively in Python. I have this code:

def flatten(test_list):
    #define base case to exit recursive method
    if len(test_list) == 0:
       return []
    elif isinstance(test_list,list) and type(test_list[0]) in [int,str]:
        return [test_list[0]] + flatten(test_list[1:])
    elif isinstance(test_list,list) and isinstance(test_list[0],list):
        return test_list[0] + flatten(test_list[1:])
    else:
        return flatten(test_list[1:])

I am looking for a very basic method to recursively flatten a list of varying depth that does not use any for loops either.

My code does not pass these tests:

flatten([[[[]]], [], [[]], [[], []]]) # empty multidimensional list
flatten([[1], [2, 3], [4, [5, [6, [7, [8]]]]]]) # multiple nested list

What is wrong with the code, and how can I fix it?

possible diplicate http://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists-in-python — root, Sep 18 '12 at 07:34
@ Anthony -- check out the supposed duplicate. I think your questions has been answered well. — root, Sep 18 '12 at 07:37
I asked a similar question [here](http://stackoverflow.com/questions/9372463/extracting-strings-from-nested-lists-in-python), and the answer given doesn't use any imports or comprehensions. It does have a for loop though. Any particularly reason for that requirement? — Marius, Sep 18 '12 at 07:38

score 50 · Answer 1 · answered Sep 18 '12 at 07:48

50

This handles both of your cases, and I think will solve the general case, without any for loops:

def flatten(S):
    if S == []:
        return S
    if isinstance(S[0], list):
        return flatten(S[0]) + flatten(S[1:])
    return S[:1] + flatten(S[1:])

answered Sep 18 '12 at 07:48

Mu Mind

10,935
4
38
69

Thank you @Mu Mind - this is exactly what I was missing - returning the first part of the list to the recursive function as well as the remaining part. Been doing my head in so thanks heaps – Anthony Gough Sep 18 '12 at 09:08
I think the first if clause should be: if S == [] or len(S) == 1, since if then length is 1 the second or third return wich concats with S[1:] will throw an Index out of range.... – Robin van Leeuwen Jan 11 '17 at 13:07
1

@RvL Try it. =) Slicing `[:1]` and `[1:]` are perfectly reasonable for single-item lists, and anyway slicing never raises IndexError. – Mu Mind Jan 12 '17 at 01:43
This works for the provided testcases, but does not work for reasonably long inputs (even if they aren't deeply nested), because it recurses for each item, eventually running out of stack space – Retr0id Jul 14 '22 at 20:24
(@chyanog's solution does not have this issue) – Retr0id Jul 14 '22 at 20:29

score 27 · Answer 2 · edited Mar 31 '23 at 20:35

27

li=[[1,[[2]],[[[3]]]],[['4'],{5:5}]]
flatten=lambda l: sum(map(flatten,l),[]) if isinstance(l,list) else [l]
print(flatten(li))

edited Mar 31 '23 at 20:35

Guillaume Jacquenot

11,217
6
43
49

answered Sep 18 '12 at 09:34

chyanog

599
5
14

What's the purpose of `sum`? – Tom Hale Dec 15 '17 at 12:20
1

@TomHale `sum(list, list)` concatenates them(lists). – plhn Dec 26 '18 at 06:33

score 8 · Answer 3 · answered Sep 18 '12 at 07:41

8

Here's a possible solution without any loops or list comprehensions, just using recursion:

def flatten(test_list):
    if isinstance(test_list, list):
        if len(test_list) == 0:
            return []
        first, rest = test_list[0], test_list[1:]
        return flatten(first) + flatten(rest)
    else:
        return [test_list]

answered Sep 18 '12 at 07:41

tobias_k

81,265
12
120
179

1

Mmm, tastes like Lisp. This is literally the same code we'd have written in Scheme back in the day... – nneonneo Sep 18 '12 at 07:44
1

This will also return `[0]` for `flatten(0)`. Not sure if that's a pro or a con... – Mu Mind Sep 18 '12 at 07:52
2

This is a good answer given the requirements in the question (no loops), but it's probably worth noting that performance will be pretty lousy. Python's `list` type is not a linked list, but rather something array-like. Each time you join two lists in the recursive step `flatten(first) + flatten(rest)`, the code will copy all the contents of both lists. I think will take O(N^2) time to produce a length N output list. – Blckknght Sep 18 '12 at 07:53
@tobias_k Thank you for helping me - I knew from debugging the code where it was failing however I never thought to return the first part of the list as a parameter to the recursive function `return flatten(test_list[0]) + flatten(test_list[1:])` I was failing when test_list was `[[4, [5, [6, [7, [8]]]]]]` but could not work out the next step. I understand how inefficient recursion can be however this was an exercise in recursion. I would not have done it this way otherwise. Thanks heaps – Anthony Gough Sep 18 '12 at 08:59
In Python3, the code would be ```def flatten1(test_list): if isinstance(test_list, list): if len(test_list) == 0: return [] first, rest = test_list[0], test_list[1:] return chain(flatten(first),flatten(rest)) else: return [test_list]``` – soumya-kole Oct 23 '21 at 03:26

score 7 · Answer 4 · answered Sep 18 '12 at 07:59

7

Well, if you want it a lisp way, let's have it.

atom = lambda x: not isinstance(x, list)
nil  = lambda x: not x
car  = lambda x: x[0]
cdr  = lambda x: x[1:]
cons = lambda x, y: x + y

flatten = lambda x: [x] if atom(x) else x if nil(x) else cons(*map(flatten, [car(x), cdr(x)]))

answered Sep 18 '12 at 07:59

georg

211,518
52
313
390

3

lol, I love how you changed the last bit from `flatten(x[0]) + flatten(x[1:])` to `cons(*map(flatten, [car(x), cdr(x)]))`. Could you add some more parentheses for old times' sake? – Mu Mind Sep 18 '12 at 08:05

Flattening a list recursively

4 Answers4

Linked