Is there a functional way to do this?

Question

def flattenList(toFlatten):
 final=[]
 for el in toFlatten:
  if isinstance(el, list):
   final.extend(flattenList(el))
  else:
   final.append(el)
 return final

When I don't know how deeply the lists will nest, this is the only way I can think to do this.

Answer 1

This blog post covers a variety of flattening strategies. There's a little more discussion over here.

Answer 2

1. You should avoid typechecking in Python. In this case, this means avoiding arbitrarily-nested structures where you distinguish by type. You can build your own node type which you can traverse by methods other than typechecking, like looking at a specific attribute.

2. For flattening one level or exactly n levels, look at itertools.chain.from_iterable.

3. I don't know what you mean by "functional". This code is pretty functional: it uses recursion (not to its credit!) and it doesn't mutate its argument. (Strictly speaking, it does use mutable state for building a list, but that is just how you do it in Python.

4. I suppose one more functional attribute would be lazy evaluation. You could implement this thusly

   def flatten(toFlatten):
       for item in toFlatten:
           if isinstance(item, list): # Ewww, typchecking
               for subitem in flatten(item): # they are considering adding 
                   yield subitem             # "yield from" to the  language
                                             # to give this pattern syntax
           else:
               yield item
   

5. Recursion is very limited in Python (at least, in all its major implementations) and should generally be avoided for arbitrary depth. It is quite possible to rewrite this (and all recursive code) to use iteration, which will make this more scalable (and less functional, which is a good thing in Python, which is not especially suited for FP.)

Answer 3

Here's another option (though there may be something cleaner than type-checking, like testing if something is iterable and hence not an "atom"):

def flatten(lst):
    if not isinstance(lst,list):
        return [lst]
    else:
        return reduce(lambda x,y:x+y,[flatten(x) for x in lst],[])

It's based on something scheme-like.

Answer 4

Under the doc for itertools, there's a flatten() function

Answer 5

This answer explains why you do not want to use reduce for this in Python.

Consider the snippet

reduce(operator.add, [[1], [2], [3], [4], [5]])

What does this have to do?

[1] + [2] => [1, 2]
[1, 2] + [3] => This makes a new list, having to go over 1, then 2, then 3. [1, 2, 3]
[1, 2, 3] + [4] => This has to copy the 1, 2, and 3 and then put 4 in the new list
[1, 2, 3, 4] + [5] => The length of stuff I have to copy gets bigger each time!

This quadratic behavior is completely avoidable: the original solution (and any number of other solutions) does not form these intermediate copying steps.