About a year ago, I was using NetworkX (a Python package for studying graphs) for one of my projects. While I was working on it, I found that the topological sort implementation in NetworkX was very slow on large-scale instances. So I decided to take a look at it, hoping I can figure out what’s wrong and fix it. In the end, I sped up considerably the implementation. Here is how I did it.

While I don’t consider myself a functional programming expert, all those hours spent in Haskell, Lisp and Scheme definitively changed my way of programming. So, after seeing a lot of unnecessarily complex implementations of function composition in Python on the Web, I decided to write this article to present a simple yet powerful solution that covers all use cases. If you are familiar with function composition, you may want to go to the solution.

You will find lots of solutions on the Web to flatten a list of lists in Python. Most of them take linear time, which is efficient because each element is copied once. But some solutions take more than linear time. In this article, I will explain why one of the simplest solution sum(lst, []) is actually one of the worst solution.
The inefficiency comes from how the + operator (concatenation) is defined on a list: it creates a new list and copies each element into it.