Results 1 to 10 of 37

Thread: Beginners Programming Challenge #20

Threaded View

  1. #1
    Join Date
    Apr 2007
    Ubuntu 10.04 Lucid Lynx

    Beginners Programming Challenge #20

    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.

    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.

    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.

    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.
    Last edited by schauerlich; April 26th, 2011 at 10:29 PM.
    Posting code? Use the [code] or [php] tags.
    I don't care, I'm still free. You can't take the sky from me.


Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts