Beginners Programming Challenge #20

[andrew1992]

I see that there, but to me that seems really quite unnecessary - why not just use filter, in that case?

[simeon87]

I see that there, but to me that seems really quite unnecessary - why not just use filter, in that case?

This is an example that I just came up with and yes you can write in a more simple way. I wouldn't write it like that in a real-world application but the example does highlight the need of an initial value to keep the function as generic as possible. It would be an unnecessary restriction of the reduce function if it could only handle functions of the same type.

[andrew1992]

This is an example that I just came up with and yes you can write in a more simple way. I wouldn't write it like that in a real-world application but the example does highlight the need of an initial value to keep the function as generic as possible. It would be an unnecessary restriction of the reduce function if it could only handle functions of the same type.

I guess my current understanding of reduce is that it should take a function, apply it to pairs of entries in a list and returning a result, and stop after it has reduced to a single result. Could you help me understand why it would be beneficial to allow genericness with reduce (that is, reduce a list of different types)? Because I'm finding it hard to see any case where that would be necessary (although I'm still learning, haha). Thanks, I appreciate the help.

[andrew1992]

To add, your first example really did reduce a list of a single type, so could you show me an example of reducing a list of different types?

[simeon87]

I guess my current understanding of reduce is that it should take a function, apply it to pairs of entries in a list and returning a result, and stop after it has reduced to a single result. Could you help me understand why it would be beneficial to allow genericness with reduce (that is, reduce a list of different types)? Because I'm finding it hard to see any case where that would be necessary (although I'm still learning, haha). Thanks, I appreciate the help.

It happens quite often in data processing that you have some list of values [a, a, a, a, a] and some object B that you wish to use to compute something using an 'a'. This object B could be a file or a database or some complex mathematical thing.

For example, you could have a list of people and a database in which you can lookup their salaries and other information. The value that reduce returns does not have to be 1 value, it can also be a list or some more complex object. So you walk along the list, you look at a value 'a' and you perform some calculation with that object B.

You can then think of functions that can do:

- Given a list of people, reduce it to a list of people that earn at least $50,000 annually.
- Given a list of people, reduce it to the total salary of these people.
- Given a list of people, reduce it to a list of managers with a salary of at least $70,000.
- Given a list of people, reduce it to the average salary of these people.
- Given a list of people, reduce it to the lowest / highest salary of these people.

You don't need to write all these things with reduce but it's nonetheless possible. You can think of the inital value as a helper value or helper object that you can use in your computations using the values of the list.

[simeon87]

To add, your first example really did reduce a list of a single type, so could you show me an example of reducing a list of different types?

It's not the types of the values in the list, it's about the types of the parameters of function f. In my latest example, the types are different. In function f, the type of parameter a is a tuple of two lists and the type of parameter b is a string. That's why I have [0] at the end to return the correct list of the tuple that reduce returns. If you take that away, you'll see that reduce actually returns:

(['aaa', 'bbb'], ['aaa', 'bbb', 'ccc'])

A tuple where the first of these is the final result of my computation and the second is the list from which we are checking. Effectively I'm building up my final result in the first list while using the second list during my calculations.

[schauerlich]

Your example doesn't help me see why those initial values are needed.

Here's an example: Say you want to determine if a list of boolean values has an even or an odd number of Trues. We can write functions to test for both of these with reduce, using the same function, but different starting values:

def f(acc, b):
    if b:
        return not acc
    else:
        return acc

def oddBools(x):
    return reduce(f, x, False)

def evenBools(x):
    return reduce(f, x, True)

even = [True, True, False, True, True,  False]
odd  = [True, True, False, True, False, False]

print "evenBools(" + str(even) + "): " + str(evenBools(even))
print "oddBools("  + str(even) + "): " + str(oddBools(even))
print "evenBools(" + str(odd)  + "): " + str(evenBools(odd))
print "oddBools("  + str(odd)  + "): " + str(oddBools(odd))

Of course, this is just one (fairly trivial) example.

[andrew1992]

I understand that it's possible, it just seems unnecessary.

true_list = filter(lambda x: x, [False, True, True, False, True])
if len(true_list) % 2 == 0:
    print "Even number of trues"
else:
    print "Odd number of trues"

I know that you're just trying to illustrate the benefit of genericness, but it's hard for me to find a case where that would be useful.

[andrew1992]

Also, your example doesn't have any genericness, the function takes in and returns the same type.

[simeon87]

I understand that it's possible, it just seems unnecessary.

true_list = filter(lambda x: x, [False, True, True, False, True])
if len(true_list) % 2 == 0:
    print "Even number of trues"
else:
    print "Odd number of trues"

I know that you're just trying to illustrate the benefit of genericness, but it's hard for me to find a case where that would be useful.

To appreciate reduce (or foldr//foldl) you'd need to study algebraic data types as fold functions can be generalized to also "reduce/fold" other data structures into a result, such as trees. An example of that (in Haskell) can be found here: http://en.wikipedia.org/wiki/Catamorphism#Example This is often used in parsers to reduce a tree data structure into a single value. Lists are a simple case of that: http://en.wikipedia.org/wiki/Fold_%2...ransformations

It's not easy to come up with a straightforward example that demonstrates the usefulness of foldr/reduce because you can, in Python, always write something else that does the same. However, the general theory behind it can be applied to various data structures. In a language such as Haskell the fold functions can make complex operations quite easy to do. Python implements these concepts from functional programming but you don't need to use them rigorously.