Beginners Programming Challenge #20

[schauerlich]

Beginners Programming Challenge #20
I hope this wall of text doesn't scare you. I just want to make sure you have a few simple concepts down, and then the rest of the challenge should be fairly simple. Feel free to skip ahead if you think you've got the idea down.

Concepts
First-class functions are a very useful tool. When a language allows first-class functions, it lets you pass around a function just like any other piece of data. You can store a function in a variable, pass it in to some other function, evaluate it with parameters, and return some other function. You can pass it around just like you would an integer or a character. This has some interesting benefits, and lets you describe common patterns in less code.

A common pattern is to take every element from a list, do something with it (say, add 5 to it, or square it, etc), and then make a list of the results. By sticking that "do something" into a function, we can hide the explicit iteration inside of a function we only have to write once. This is called 'mapping':

data = range(1, 11)
new_list = []

for i in data:
    new_list.append(i * i)

can be transformed into

def square(x):
    return x * x

def map(func, data):
    new_list = []

    for i in data:
        new_list.append( func(i) )

    return new_list

map(square, range(1, 11))

Now, this might look like MORE code, and that's true for this small example. But the benefit is that you only have to write 'map' once. Then, you can customize the behavior by writing a different function in place of 'square', and passing it in to 'map'.

Mapping is just one example of a common pattern that can be solved using first class functions. Your challenge is implement a couple more.

The Challenge
You must implement two functions, filter and reduce.

• Filter will take two arguments, a function 'f' and a list 'x'.
  
  • 'f' will be a function that returns True or False based on some input. For example, the function 'isOdd' should return True if it's given an odd number, and False otherwise.
  • Filter will return a list that contains all of the elements of 'x' such that 'f' returns True.

def isOdd(x):
    return x % 2 == 1

filter(isOdd, range(1, 11)) # returns [1, 3, 5, 7, 9]

• Reduce will take a function 'f', a list 'x', and an initial value 'i'.
  
  • 'f' will take two parameters, combine them in some way, and return the result.
  • Reduce takes all of the elements of 'x', combines them one at a time using 'f', and uses the value 'i' as the starting value when doing the first combination.

def add(x, y):
    return x + y

reduce(add, range(1, 6), 0) # returns (((((0 + 1) + 2) + 3) + 4) + 5), which is 15

Extra credit
A lot of things can be defined in terms of reduce, including map and filter. Other examples include: taking the sum or product of all elements in a list, concatenating a list of lists into one flat list, reversing a list, finding the minimum/maximum of a list, and so on. Implement anything else you feel like doing in terms of the functions presented here.

Help
For people who have never dealt with them before, first-class functions can be a little intimidating. If you're unclear on what filter and reduce should do or how first-class functions work, feel free to ask for a different explanation or more examples. Note that many languages already have map, filter and reduce built in or as part of the standard library under various names. You should experiment with those to get a better sense of what they do and what you can do with them.

Judging
Entries will be judged based on how well you seem to understand the applications of first class functions, as well as the basic criteria that you code must work and be readable. One way of demonstrating understanding is to at least attempt the extra credit, even if you can't get it working. The goal here is to make you think, not churn something out for a grade.

Have fun! Judging will commence in a few weeks, or when the entries stop coming in.