Reduce (fold) for the imperatively minded

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

Decorative PictureThe 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:

  1. First you define the initial state that the loop is meant to be in.
  2. You then define a function that defines how you change from one state to another when on of the list variables is read in.
  3. You then define your “perform loop function” to take an initial state, a list, and a state changing function and return the final state.
  4. 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)
Advertisements

Entry filed under: Uncategorized. Tags: , , .

Services near Tower Hamlets Ant troubleshooting

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed


March 2008
M T W T F S S
« Feb   Apr »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

%d bloggers like this: