Itertools, a Love Story

Published: 10/02/2019

I remember when I first learned about while loops. It was my second year of high school. My first year we learned Scheme, a lisp variant. But my second year Mr. Estep taught us Java, and the delight of language specified control structures was given to us. Loops were the focus of a week or two of our course. First we learned about while loops then for loops. I remember at the time thinking how pointless for loops were. Anything that could be accomplished with a for loop could also be done with a while loop. Why would I write:

for (int i = 0; i< n; i++) {
    // Do something

When I could simply write:

int i = 0;
while(i < n) {
     //Do something

Of course one may argue the for loop takes up slightly fewer characters. But this benefit seemed unconvincing to me in the face of the cost of needing to hold two different iteration constructs in my head. I grew older, and I wrote more code, and eventually I realized that everytime I whipped out my iteration hammer I had some index moving linearly through some data structure and my iteration tool might as well be explicit about what the index is and how its moving. The while construct ostensibly offered more flexibility but really I always iterated in the same way. It was the while loop which was redundant, not the for loop.

Enter the foreach loop:

for(Object thing : things) {
     //Do something

My initial reaction was again that this was pointless redundancy. But as time passed I realized this new briefer loop captured almost all the use cases I needed iteration for and abstracted away a crutch I thought I needed, but didn't really: the index. If I'm trying to compute some statistic from the collection, I don't need the index. If I'm trying to make some new collection, which comes from a transformation of elements of the old collection, I don't need an index. If I'm trying to make a subcollection from my original collection based on some sort of condition, I don't need an index. And those three things, reduce, map, filter, capture maybe 90% of all my iteration use cases. Fast forwarding to my Haskell years at UChicago after Java had been left far behind and I'd switched form Haskell to Python, but still appreciated the Haskell aesthetic. I liked to program like this:

reduce(function, collection)
map(function, collection)
filter(condition, collection)

And I'd write looooong lines of code composing them to get the result I wanted. In the beginning I thought in terms of base operations and operations on the index were just another operation. Now iteration was itself an operation on functions and collections. My words had gotten bigger and my reach had gotten farther.

There's one last chapter. What about double for loops? Maybe I want to do some operation on all tuples (i,j), 0<=i,j< N. Once upon a time I might have written a nested for loop. Or I might have made a map with its subfunction itself an instance of map. But no longer. Now I use itertools!

from itertools import product
map(function, product(range(N),2))

Such brevity and beauty. No mucking around at the level of indexes or even thinking about whether you're going in a left to right or up to down manner. Just pure data structures and operations.

Itertools came to my attention when I was googling for the Pythonic way to iterate over subgroups of a group. Once upon a time I would iterate over subgroups of a set of size N by iterating from 0 to 2^N - 1. Each such number encodes whether n is in the subgroup based on whether the nth character in the bitstring is a 0 or a 1. In other words the ith subgroup contains the element j if and only if !(i & (1<<j) == 0) is true. Yuck! What disgusting code I hacked together. Now I use itertools.combinations like a civilized scholar.