reduce

Uses the supplied function to combine the input elements, often to a single output value

I've often run into people who find the reduce operation tricky to understand, even to the point of avoiding it. Yet reduce is a valuable operation for combining values from many items in a collection.

To start with the basics: a reduction operation takes a function that takes two arguments - an accumulator and the current iteration. With each iteration it combines these two arguments into a single value which is then put into the accumulator for the next iteration to use. Consider this code to concatenate a list of strings

["a", "b", "c"].reduce(""){|acc, s| acc + s}
# => "abc"

(reduce str "" ["a" "b" "c"])
;; => "abc"

To understand what happens, here is a table of each step in the iteration.

For the first example I included an initial value, but usually it isn't necessary. If I omit the initial value then the reduction sets the initial value to the first element and begins the iteration with the second element.

["a", "b", "c"].reduce(:+)
# => "abc"

(reduce str ["a" "b" "c"])
;; => "abc"

Even though my habit in ruby is to use lambdas for collection pipeline operations, I prefer just naming the function for reduce.

The reduce operations I've shown so far are left-reductions, since we iterate the list starting at the left. Some languages also have a right-reduction which goes from right to left. Semantically this is the same as reversing the list and then doing a left-reduce. Depending on how its implemented, a right-reduce operation may have different effects on memory, particularly stack, consumption and laziness. If the language use the “fold” terminology, then left-fold is often written “foldl” and right-fold as “foldr”.

The notion of left and right fold with an accumulator is the most common way of thinking about reduce but carries a flaw - it isn't inherently parallelizable. Some approaches look to solve this by thinking of reduce as an inherently parallel operation providing the combining function is associative (such as clojure's reduce library).

Smalltalk's term for reduce is inject:into and would be used like

aList inject: '' into: [:acc, :each| acc , each]

Smalltalk's string concatenation operator is “ , “.

Ruby uses “inject” as an alias for “reduce” but without both keyword parameters of inject:into: it doesn't read as well. I still used it out of familiarity, but now prefer to use “reduce”.