## Reduce (fold) for the imperatively minded

*March 16, 2008 at 10:12 pm* *
Leave a comment *

The reduce or fold function is a concept in functional programming languages which can be used to simulate looping behaviour without the need for a real loop, and in particularly without the need for any explicit variables. I believe it originated in the field of functional programming languages, where getting rid of any form of ‘state’ seems to be an overriding aim.

I suspect that, with suitable training, one may be able to grasp the meaning of a reduce statement more quickly than the corresponding loop statement, since one doesn’t have to follow the flow of the program quite so much – but I’m not terribly sure how much training is suitable.

**Understanding the reduce with an imperative mind set**

A good way to understand a reduce statement is as an attempt to replace a for each loop with something that has no explicit state or variables.

To do this one can proceed as follows:

- First you define the initial state that the loop is meant to be in.
- You then define a function that defines how you change from one state to another when on of the list variables is read in.
- You then define your “perform loop function” to take an initial state, a list, and a state changing function and return the final state.
- By using this function and then extracting the final state you can simulate a loop.

Opaque as stone – An example might work:

Let’s look at the following loop that finds the sum of the two largest elements in a list:

def find_largest_pair(L): largest = 0 second_largest = 0 for x in L: if x > largest: largest = x second_largest = largest elif x > second_largest: second_largest = x return (largest, second_largest)

Our state is the tuple (largest, second_largest).

Our initial state is the value (0,0).

Our state changing operation is effectively the entire body of the loop:

def state_change(x, (old_largest, old_second_largest)): if x > old_largest: return (x, old_largest) elif x > old_second_largest: return (old_largest, x) else: return (old_largest, old_second_largest)

Let’s call out loop evaluating function *reduce*. So our final state is given by reduce(state_change, L, (0,0)). This final state happens to also be the final answer, so we don’t need to do anything to answer returned.

The reduce function is defined in exactly this way.

It is worth noting that the final state is not always equivalent to the return value. As a brief illustration consider the loop that sums every third entry in a list:

def sum_third_entries(L): sum = 0 index = 0 for x in L: index += 1 if index % 3 == 2: sum += x return sum

Here the state is (index, sum), whilst the value we return is just the sum part of this final state.

So this reduce function allows one to encode loops in a different format, which avoids any variables. But is this actually of any use to one. I’m not sure. A good way of deciding might be to compare some loops with their equivalent reduce statements. The following look at a few examples.

**Sum of elements in a list**

sum = 0 for x in L: sum += x return sum return reduce(lambda x,y: x+y, L, 0)

**Finding out if one of a number of values is set**

one_set = False for x in L: if x: one_set = true return one_set return reduce(lambda x,y: x or y, L, False)

Entry filed under: Uncategorized. Tags: functional programming, programming, slightly philosophical.

Trackback this post | Subscribe to the comments via RSS Feed