Pythonic way to flatten lists or arbitrary depth using assignment expressions

Question

I'm working through the classic "99 problems in prolog" collection. But trying to do them Pythonically. Flatten a list is problem 07. I am flattening a list of lists of arbitrary depth. I have two solutions below. Which is more Pythonic?

# helper function
def isList( x ): return isinstance( x, list )

def flatten3_h( *xs ): 
  if ( len(xs) == 0 ): return [] # base case, empty list/tuple
  hd, tl = xs[ 0 ], xs[ 1: ]
  if ( not(isList( hd ))): return [ hd ] + flatten3_h( *tl )
  return flatten3_h( *hd ) + flatten3_h( *tl )

def flatten4( *xs ):
  acc = []
  [ acc := acc + [x] if not(isList( x )) else acc + flatten4( *x ) for x in xs ]
  return acc

Here is example usage:

flatten4([ [] , [1, [2, [3, [], 4]], 5]] ) # => [1, 2, 3, 4, 5] 

I'm guessing flatten4 is more Pythonic as it uses list comprehensions. But I'm not sure since it uses an assignment expression which I just learned about. As it's a new feature in python3.8.

Any feedback is appreciated.

Answer 1

Welcome to Code Review.

1. Follow the PEP8 guide for naming conventions. Functions and variables would be snake_case.

2. When checking for empty list, you don't need to find the length. Empty lists/strings/sets are all falsy values in python.

3. Use better/fuller names. hd/tl -> head/tail.

4. There are a few inbuilt utilities in python, which might help you:

   • itertools.chain
   • itertools.chain.from_iterable
   • functools.reduce

Answer 2

Representing lists as a head and a tail is a common method, but honestly not the most Pythonic way to do things. Additionally, everything you're doing is appending lists together - this is generally inefficient due to the way memory has to be reallocated and the data has to be moved. This StackOverflow question has some interesting details. (Although I talk about efficiency, generally recursion and deeply nested generators may not be the most efficient either. Anytime you're considering performance, make sure you understand the requirements of your functionality and measure your own performance before attempting to optimize too much)

Ultimately, I think the cleanest solution would be to create a generator:

def flatten(iterable):
    try:
        iterator = iter(iterable)
    except TypeError:
        # this is potentially controversial, depending on your use case
        # you may want a mutually recursive function, or a keyword argument, to 
        # indicate if you want to yield the input vs raise an error
        yield iterable 
    else:
        first_value = next(iterator)
        if first_value is iterable:
            yield first_value
        else:
            yield from flatten(first_value)
            for value in iterator:
                yield from flatten(value)
    
def get_flat_list(iterable, constructor=list):
    return constructor(flatten(iterable))

A few things to call out - explicit isinstance checks are not always a Pythonic solution. Many libraries and functions in the Python ecosystem make heavy use of duck typing - if it iterates like a list, then it is a list as far as that functionality is concerned. You should re-evaluate whether it is a strict requirement that lists are supported, or iterables. I suspect that you want most/all iterables to be supported, and thus see if there are other ways to do this. There are generally two ways to do this:

• Just try, and handle the error
• Direct inspection of properties to see if it can be used (e.g. hasattr(iterable, "__getitem__") or hasattr(iterable, "__iter__"))

In this case, I'm just trying. You might also notice the first_value is iterable stuff - this is to handle cases like a string, where both "abc" and "a" are iterable, and you would hit infinite recursion. In this case, I'm simply making sure that if the first item of an object is itself we don't recurse forever. This probably isn't comprehensive, but it handles at least the string case.

I've also stopped restricting us to returning lists - what if you want a tuple? Some other type?

Lastly, I've renamed things to match Python's PEP8 naming conventions

---

As Peilonrayz pointed out in the comments, isinstance has become more "accepted" outside of core Python development recently (generally, strict types are more in vogue overall).

For example, instead of using a try/except, you could do isinstance(foo, collections.abc.Iterable) instead of catching the TypeError when we do iterator = iter(iterable). Note - collections.abc.Iterable will only work for objects that define the __iter__ dunder-method, so __getitem__ based iteration won't be usable with this approach. This is another good reason to avoid using isinstance if you have a good alternative (in our case, checking for iter(iterable)).

Alternatively, some new proposed functionality in Python is isinstance based - see PEP 622. Theoretically, you could come up with something like this (using sequence patterns):

match iterable:
    case ((inner_head, *inner_tail), *tail):
        yield inner_head
        yield from flatten(inner_tail)
        yield from flatten(tail)
    case ():
        return
    case _:
        yield iterable

Answer 3

Pythonic code comes in three main veins:

1. That it follows PEP 8.
2. Using features of Python that make code easier to read.
   This doesn't mean shorter or use new features.
3. That it follows Python norms.
   These are more norms in the sense that map, filter and reduce are no longer 'Pythonic' but are not mentioned in PEP 8.

In short these can be summed up as follow norms that make your code easy to read.

---

Your code doesn't do this.

1. • You shouldn't have spaces around parentheses. isList( x ) vs isList(x).

   • You should use snake_case for function names. isList vs is_list.

   • You should not have expressions on the same lines as ifs or defs

     def isList( x ): return isinstance( x, list )
     

     vs

     def is_list(x):
         return isinstance(x, list)
     

   • You should indent with 4 spaces.

   • You shouldn't have white space at the end of lines.

   • You should have two newlines between top level functions (and classes).

   • You should use descriptive variable names, what are xs, x, hd, tl?

2. • You should not have parentheses around if expressions. if ( len(xs) == 0 ): vs if len(xs) == 0:.
   • You can use truthy rather than len. if len(xs) == 0: vs if not xs:
   • You can use tuple unpacking with the * operator rather than xs[ 1: ].
   • Not is not a function it is a keyword. It does not need parentheses.

3. • You shouldn't abuse list comprehensions to contain mutability.

     [ acc := acc + [x] ... ]
     

In all more Pythonic versions of these functions would look like the following:

# helper function
def is_list(value):
    return isinstance(value, list)


def flatten3_h(*values):
    if not values:
        return []  # base case, empty list/tuple
    head, *tail = values
    if not is_list(head):
        return [head] + flatten3_h(*tail)
    return flatten3_h(*head) + flatten3_h(*tail)


def flatten4(*values):
    flattened = []
    for value in values:
        flattened += (
            [value]
            if not is_list(value) else
            flatten4(*value)
        )
    return flattened

I'm wondering which is more Pythonic

At this point they are both fairly Pythonic. But I would prefer to maintain flatten4.

Answer 4

PEP-8 issues aside, I found the answer from Peilonrayz (flatten4) the best. I would refine it further though, to make it less complicated, and more in line with EAPF programming:

def flatten4(values):
    flattened = []
    for value in values:
        try:
            flattened.extend(flatten4(value))
        except:
            flattened.append(value)
    return flattened

As mentioned by Dan Oberlam, use of isinstance is fairly accepted, but can mess with Duck Typing. Note three other small changes:

• I replaced flattened += [value] with flattened.append(value), which is both clearer and faster.

• Purely for consistency, I also replaced flattened += flatten4(value) with flattened.extend(flatten4(value)).

• I removed the * from *values, as the problem description clearly states

  flattening a list of lists of arbitrary depth

  i.e. flattening a single list.

Answer 5

Neither is a good idea. Note the term arbitrary depth. It will be easy to make this explode by constructing input that is deeper than your stack, since you recurse and Python has an explicitly limited stack. Even if it didn't have a limited stack, Python does not have tail recursion optimization so this will be (relatively) slow. You should attempt to make an iterative solution instead.

Answer 6

Other answers gave you great tips for the PEP8 compliance, implicit falseyness for empty lists and naming/style conventions. These are the first things I would have said if I code reviewed this first.

I wanted to add, if you are going to stick with the isinstance approach, that you can keep it while making your function a generator by replacing return with yield. You still have recursion, but now it will yield from itself instead of returning itself.

Something like:

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

Just note that because it is a generator, you have to wrap it with list() to print output.

list(flatten(['a','b',['c','d']])) 
--> ['a', 'b', 'c', 'd']