The limits of list comprehensions

I’ve spent my recent posts unfavourably comparing the STL design of containers/iterators/algorithms with Python list comprehensions and their close relatives in Haskell. This is an unfairly restrictive way to view the STL design, which addresses a wider range of use cases than the ones addressed by list comprehensions. But it is also unfair in that it ignores the limitations of list comprehensions themselves, limitations avoided by the more general structure provided by the STL. In this post, I’ll start from the other direction, considering the inherent limitations of Python list comprehensions. This in turn leads to an idiom in the STL that in fact provides virtually all the functionality of basic list comprehensions, with only slightly more complex syntax.

The general and basic forms of Python list comprehensions

The full form of Python list comprehensions is complex, permitting many forms of nesting. For this post, I’m going to focus on the most basic form, [expression1 for var in expression2 if condition(var)], where expression2 evaluates to an iterator and expression1 is some function of var. I won’t consider the cases where there are multiple for ... if ... on the right, nor the cases where expression1 is itself a list comprehension.

I am also not going to consider Python’s syntactically similar generator expressions, which only compute elements on demand, handling very long and infinite streams. This is not how the STL algorithms work, which all require the complete evaluation of their range, corresponding to list comprehensions.

Within those restrictions, the basic Python list comprehension has this structure:

for each element returned by an iterator
  if the element passes the filter
    compute a function of the element
    append the computed value to the result list

This structure is broadly useful but its element-at-a-time structure has a fundamental limitation: You have to leave the paradigm whenever you have an operation on two or more values from the iterator. The classic algorithm requiring such an operation is sorting, which must test pairs of values.

It turns out that use cases that require you to filter, sort, and then filter again are rather specialized. The Python example that I wrote for this post wound up being so contrived that I won’t bother to include it here. I suspect the primary use cases for filter/sort/filter lie in database operations, where the intermediate sort step is required to efficiently scan key lists along indices, producing more efficient access to external storage. Intermediate sort steps seem far less useful for the cases considered in this post, where the entire data structure is already in memory.

If needed, sorting commonly precedes or follows a list comprehension

A far more common use case requires the filtering and computation to be performed in one step, with the sorting done either before or after. For example, given a list of pairs whose first value is an abbreviation for either a Canadian province or US for the USA and whose second value is an amount, func() filters out the US amounts and returns the squares of the Canadian amounts, sorted by province and squared amount:

def func(lst):
    a = [(x[0], x[1]*x[1]) for x in lst if x[0] != 'US']
    return sorted(a)

if __name__ == '__main__':
    a = func(zip(['BC','NB','BC','US','NB','BC','BC'],range(7)))
    print (a)

The per-pair processing is handled well by the list comprehension (Line 2), with the sort done (Line 3) on the computed result. The same effect can be accomplished via the considerably more prolix STL sequence (equivalent code highlighted)

using ppair = pair<string,int>;
using plist = vector<ppair>;

ostream& operator<<(ostream& os, const ppair& pp) {
  os << "(" << pp.first << ", " << pp.second << ")";
  return os;
}

ostream& operator<<(ostream& os, const plist& pl) {
  if ( ! pl.empty()) {
    cout << pl[0];
    for (auto p = pl.cbegin() + 1; p != pl.cend(); ++p)
      cout << ", " << *p;
  }
  return os;
}

int main () {
  plist src {
    ppair{"BC", 0},
    ppair{"NB", 1},
    ppair{"BC", 2},
    ppair{"US", 3},
    ppair{"NB", 4},
    ppair{"BC", 5},
    ppair{"BC", 6}
  };

  plist t1 {};
  t1.reserve(src.size());
  std::copy_if(src.cbegin(), src.cend(), back_inserter(t1), 
    [](auto p) { return p.first != string("US"); });

  plist res {};
  res.reserve(t1.size());
  std::transform(t1.cbegin(), t1.cend(), back_inserter(res),
    [](auto p) { return ppair{p.first, p.second * p.second}; });

  std::sort(res.begin(), res.end());

  cout << res << '\n';
}

The STL version uses the reserve/back_inserter approach to building the temporary t1 and the result res.

The primary source of the extra length of the STL algorithm is the requirement for separate copy_if and transform steps. This separation is necessitated by the transform algorithm’s requirement that it produce exactly one transformed result for every element in the source. By contrast, the Python list comprehension’s if filter allows its result to have fewer elements than its source.

Although it is not obvious, there is a way to combine the filter and computation in the STL transform function, giving a one-line transform that produces fewer elements than its sink. The trick is that the filter isn’t located in the lambda expression—at least not entirely. I’ll present that solution in my next post.