Recursions and Reductions
This lacks the recursion limits. It includes the required tail-call optimization.
Further, this will work equally well with either a sequence object or an iterable.
In other functional languages, this is called a foldl operation: the operators are
folded into the iterable collection of values from left-to-right. This is unlike the
recursive formulations which are generally called foldr operations because the
evaluations are done from right-to-left in the collection.
For languages with optimizing compilers and lazy evaluation, the fold-left and
fold-right distinction determines how intermediate results are created. This may
have profound performance implications, but the distinction might not be obvious.
A fold-left, for example, could immediately consume and process the first elements
in a sequence. A fold-right, however, might consume the head of the sequence, but
not do any processing until the entire sequence was consumed.
Group-by reductions – from many to fewer
A very common operation is a reduction that groups values by some key or
indicator. In SQL, this is often called the SELECT GROUP BY operation. The raw data
is grouped by some columns value and reductions (sometimes aggregate functions)
are applied to other columns. The SQL aggregate functions include SUM, COUNT, MAX,
and MIN.
The statistical summary called the mode is a count that's grouped by some
independent variable. Python offers us several ways to group data before computing
a reduction of the grouped values. We'll start by looking at two ways to get simple
counts of grouped data. Then we'll look at ways to compute different summaries of
grouped data.
We'll use the trip data that we computed in Chapter 4, Working with Collections.
This data started as a sequence of latitude-longitude waypoints. We restructured
it to create legs represented by three tuples of start, end, and distance for the leg.
The data looks as follows:
(((37.5490162, -76.330295), (37.840832, -76.273834), 17.7246),
((37.840832, -76.273834), (38.331501, -76.459503), 30.7382),
((38.331501, -76.459503), (38.845501, -76.537331), 31.0756), ...
((38.330166, -76.458504), (38.976334, -76.473503), 38.8019))