Flattening a List Recursively

Flatten an irregular list of lists in Python recursively

Your code is relying on a global; if the checker calls your function twice, it'll receive a longer list than expected:

>>> t = []
>>> def flatten(aList):
...     for i in aList:
...         if type(i) !=list:
...              t.append(i)
...         else:
...              flatten(i)
...     return t
...
>>> flatten([1, 1])
[1, 1]
>>> flatten([1, 1])
[1, 1, 1, 1]
>>> t  # your global, still holding all those values:
[1, 1, 1, 1]

Don't use globals. Use a local list, and and extend it with the result of recursive calls:

def flatten(aList):
    t = []
    for i in aList:
        if not isinstance(i, list):
             t.append(i)
        else:
             t.extend(flatten(i))
    return t

Note that I switched to using isinstance() to test for the type. This version doesn't suffer from shared state leaking into the next call:

>>> def flatten(aList):
...     t = []
...     for i in aList:
...         if not isinstance(i, list):
...              t.append(i)
...         else:
...              t.extend(flatten(i))
...     return t
...
>>> flatten([1, 1])
[1, 1]
>>> flatten([1, 1])
[1, 1]
>>> flatten([[[1]], [[[5]]]])
[1, 5]
>>> flatten([1, 1, [42, 81]])
[1, 1, 42, 81]

Flatten List of Lists Recursively

Ok so this is a recursive function as you have stated. It is a mostly 'look at the next element and decide what to do with it' method. It is started with the base case.

if S == []:
        return S

So this makes sense. You have an empty list, so you would expect to get back an empty list, it's flat.

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

Next is the first 'look at the next element, decide what to do', if I receive a list and at the first element there is a list, I will get the program to run this same flattening method on the first element.

But then comes the rest of the list, we don't know if that is flat so I will be doing the same thing for that calling flatten on that as well.

When this returns they should both be flat lists. Adding two lists just joins them together into a new list so this would be returned up a level to the previous call of the recursive method or return to the user.

return S[:1] + flatten(S[1:])

From before we know that the first element of the list is not a list as the if statement was if isinstance(S[0], list) so this is just taking a list with the first element stored in it and just like before running flatten on the rest of the list as we don't know whether the rest of the list is flat or not.

As for tracing, if you don't have Pycharm or pdb is to complex for you. Throw in some prints within each of the if statements. Don't be shy, you're the one that's going to read them. do a print(f"First element was a list: {S[0]}, {S[1:]}") that will be fine if you're a beginner dealing with such a small amount of code. Otherwise try PDB or such.

Recursively flatten a nested list of integers with low and high pointers

You could have used the original function as-is with subscript assignment:

def flatten(lst):
    if not lst:
        return lst
    if isinstance(lst[0], list):
        return flatten(lst[0]) + flatten(lst[1:])
    return lst[:1] + flatten(lst[1:])

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

L[0:2] = flatten(L[0:2])
print(L)

[1, 2, 3, [4, [5, 6, [7], 8]]]

Or implement a new function that uses the first one:

def flattenRange(L,low,high):
    L = L.copy()
    L[low:high] = flatten(L[low:high]) # use high+1 if it is inclusive
    return L

Or even 'bastardize', ... I mean 'enhance' the original:

def flatten(lst,low=0,high=None):
    if low>0 or high is not None:
        lst = lst.copy()
        lst[low:high] = flatten(lst[low:high]) # use high+1 if it's inclusive
        return lst
    if not lst:
        return lst
    if isinstance(lst[0], list):
        return flatten(lst[0]) + flatten(lst[1:])
    return lst[:1] + flatten(lst[1:])

Can I flatten a list using recursive function and list comprehension?

You can though it is a little strange:

def fun_d(x):
    return [i for e in x for i in (fun_d(e) if isinstance(e,list) else [e])]

In[] :
l=[1,[2,3],[4,5,[6,7,8,9]]]
fun_d(l)

Out[]:
[1, 2, 3, 4, 5, 6, 7, 8, 9]

You may want to use Sequence rather than list so other types of sequences would also be flattened.

from typing import Sequence

def fun_d(x):
    return [i for e in x for i in (fun_d(e) if isinstance(e, Sequence) and not isinstance(e, str) else [e])]

A named lambda is trivial, for a truly anonymous lambda you can use a y-combinator

And just to show how ridiculous this is, an anonymous recursive lambda:

In []:
lis = [1,[2,3],[4,5,[6,[7,8],9]]]
(lambda f: f(f))(lambda f: (lambda fun_d: lambda x: [i for e in x for i in (fun_d(e) if isinstance(e, list) else [e])])(lambda x: f(f)(x)))(lis)

Out[]:
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Recursively flatten nested list in python

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.

1. 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.

2. 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+.

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

Return a flatten list from my recursive function in Python

Try this

List = [68, -99,"abc", -8,100, [-92, 89, 81, 96]]

result = []
def flatten(my_list):
    for i in my_list:
        if isinstance(i, list):
            return flatten(i)
        else:
            result.append(i)
    return result

print(flatten(List))

Recursively flatten a list with streams

You could just use flatMap directly:

private static Stream<TerminalNode> flatten(final List<Node> nodes) {
    return nodes
            .stream()
            .flatMap(node -> {
                if (node instanceof InternalNode) {
                    return flatten(((InternalNode) node).getNodes());
                }
                return Stream.of((TerminalNode) node);
            });
}

If you want a List, you can just collect the result of that method call.

---

Related Topics