# Thread: Beginners Programming Challenge #20

1. ## 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.

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':
Code:
```data = range(1, 11)
new_list = []

for i in data:
new_list.append(i * i)```
can be transformed into
Code:
```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.

Code:
```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.

Code:
```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.
Last edited by schauerlich; April 26th, 2011 at 10:29 PM.

2. ## Re: Beginners Programming Challenge #20

Great challenge!
I like the idea of demonstrating understanding of a concept, rather than producing a result. Explaining something to someone else always aids your own understanding by making you think things through step-by-step.

Here's my entry, in Ruby. Two very helpful sites I used to aid my understanding are here and here (both are good for further reading on functions in Ruby).

PHP Code:
``` #!/usr/bin/ruby # Ruby has several kinds first-class functions, but I'm only going to look at # two: Procs and Lambdas. # First, Procs: is_odd = Proc.new{ |n| !(n%2).zero? } def filter(function, range)     values = []     range.each do |i|         values << i if function.call(i)     end     values end p filter(is_odd, (1..10)) # Procs also have a shorthand syntax. add = ->(n,m){ n+m } def reduce(function, range, initial)     range.each do |i|         initial = function.call(i, initial)     end     initial end p reduce(add, (1..10), 0) # Ruby also has Lambdas, which are similar to Procs but have different rules # for flow control, and behave more like methods in other languages. For # example, you can return from a Lambda back *to* the calling function, but # returning from a Proc is the same as returning *from* the calling function. def test     my_lambda = lambda{ return "returning from Lambda" }     my_proc = Proc.new{ return "returning from Proc" }     puts "starting test.."     puts my_lambda.call     # the lambda returns to here.     my_proc.call            # the Proc does *not* return to here.     "returning from test.." # control does *not* get here. end puts test                   # the Proc returns to here!  ```
Edit: This code is written in a more functional style than I'm used to; it's not very Rubyish, and is not the technique I would normally use for code re-use. However, this was the format requested in the challenge.

Edit 2: This is the output:
Code:
```[1, 3, 5, 7, 9]
55
starting test..
returning from Lambda
returning from Proc```
Last edited by krazyd; April 27th, 2011 at 06:47 PM.

3. ## Re: Beginners Programming Challenge #20

For a lark, I thought I'd do this one in ANSI C. I decided to break the rules by adding additional arguments to the required functions to make the test more friendly to C:

func_callback.h
PHP Code:
``` /* Programming Challenge 20  * Due to the difficulty of implementing generalized arguments in C,   * only an integer compatible version of the functions exist. */ #ifndef FUNC_CALLBACK_H #define FUNC_CALLBACK_H 1 #define TRUE  1 #define FALSE 0 typedef unsigned char boolean; typedef boolean (*TestFunc) (int); typedef int (*CombineFunc) (int, int); /* remove entries which do not match criteria specified by user supplied  * function 'f' and return an array containing only those matches. */ int *filter (const TestFunc f, int *arr, const int sz, int *result_sz); /* reduce array 'arr' by applying user supplied function 'f' into one result,  * starting with value 'start' */ int reduce (const CombineFunc f, int *arr, const int sz, const int start); #endif /* FUNC_CALLBACK_H */  ```
func_callback.c
PHP Code:
``` #include "func_callback.h" #include <stdlib.h> int * filter (const TestFunc f, int *arr, const int sz, int *result_sz) {     int i;     int x = 0;     int *tmp = malloc (sizeof (int) * sz);          if (!tmp) return NULL;          for (i = 0; i < sz; i++)       if (f (arr[i]))              tmp[x++] = arr[i++];          tmp = realloc (tmp, sizeof (int) * x);          *result_sz = !tmp ? 0 : x;          return tmp; } int  reduce (const CombineFunc f, int *arr, const int sz, const int start) {     int i;     int result = start;          for (i = 0; i < sz; i++)         result = f (result, arr[i]);          return result; }  ```
The following is the code used to test the above:

func_cb_main.c
PHP Code:
``` #include "func_callback.h" #include <stdio.h> #include <stdlib.h> /* "user" defined functions for use with filter and reduce */ static boolean  isOdd (const int num) {     return (num % 2); } static boolean  isEven (const int num) {     return !(num % 2) && num != 0; } static int add (const int x, const int y) {     return x + y; } static int sub (const int x, const int y) {     return x - y; } int main (void) {     int test_arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};     int *result_arr;     int result = 0;     int i;     int sz;          result_arr = filter (isEven, test_arr, sizeof(test_arr) / sizeof (int), &sz);     printf ("Printing even numbers from array:\n");     for (i = 0; i < sz; i++)         printf ("%d ", result_arr[i]);     printf ("\n");     free(result_arr);          result_arr = filter (isOdd, test_arr, sizeof(test_arr) / sizeof (int), &sz);     printf ("Printing odd numbers from array:\n");     for (i = 0; i < sz; i++)         printf ("%d ", result_arr[i]);     printf ("\n");     free(result_arr);     result_arr = NULL;          result = reduce (add, test_arr, 10, 0);     printf ("reduce (add) returned a result of %d\n", result);          result = reduce (sub, test_arr, 10, 20);     printf ("reduce (sub) returned a result of %d\n", result);          return 0; }  ```
Use whatever compile flags you want. I tested with:
Code:
`gcc -Wall -Wextra -ansi -pedantic func_callback.c func_cb_main.c && ./a.out`
Results:
Code:
```Printing even numbers from array:
2 4 6 8
Printing odd numbers from array:
1 3 5 7 9
reduce (add) returned a result of 45
reduce (sub) returned a result of -25```

4. ## Re: Beginners Programming Challenge #20

Originally Posted by JupiterV2
For a lark, I thought I'd do this one in ANSI C. I decided to break the rules by adding additional arguments to the required functions to make the test more friendly to C:
I was waiting for someone to try it in C. The idea for this challenge actually came from a discussion on how to make a generic version of map in C. There's no good way to do it. One method is to force the function you hand in to be of the type void foo(void *), and then make the user take care of casting the void * properly. Ugly.

If someone made a generic reduce in C, I'd be very impressed. After all, the value it accumulates should be able to be ANY type, including an array.
Last edited by schauerlich; April 28th, 2011 at 04:55 AM.

5. Dipped in Ubuntu
Join Date
Feb 2009
Beans
531
Distro
Ubuntu 12.04 Precise Pangolin

## Re: Beginners Programming Challenge #20

Interesting. I think I had an assignment a year or so ago where implementing filter in terms of reduce (in Haskell) was not just extra credit but actually required. It's been a while, though, the course was in German, and I seem to remember pulling my hair out over the problem.

EDIT: In fact, I seem to have found it so difficult that I used a loophole in the way the assignment was written to not implement filter in terms of reduce. I'll have to try again.
Last edited by jwbrase; April 28th, 2011 at 06:07 AM.

6. A Carafe of Ubuntu
Join Date
Feb 2011
Location
Cambridge, ON, CAN
Beans
105
Distro
Ubuntu 10.10 Maverick Meerkat

## Re: Beginners Programming Challenge #20

I figured reduce lends itself nicely to a recursive approach. Here's a concise Python example:

Code:
```def filter(function, list_):
return [i for i in list_ if function(i)]

def reduce(function, list_):
if len(list_) > 1:
list_ = [reduce(function, [function(list_[0], list_[1])] + list_[2:])]
return list_[0]```
Last edited by andrew1992; April 28th, 2011 at 01:46 PM.

7. A Carafe of Ubuntu
Join Date
Feb 2011
Location
Cambridge, ON, CAN
Beans
105
Distro
Ubuntu 10.10 Maverick Meerkat

## Re: Beginners Programming Challenge #20

Originally Posted by schauerlich
I was waiting for someone to try it in C. The idea for this challenge actually came from a discussion on how to make a generic version of map in C. There's no good way to do it. One method is to force the function you hand in to be of the type void foo(void *), and then make the user take care of casting the void * properly. Ugly.

If someone made a generic reduce in C, I'd be very impressed. After all, the value it accumulates should be able to be ANY type, including an array.
I've never touched C before, though I'm aware it has no support for function overloading as far as I know. I'm going to give this a shot though, just for kicks

8. ## Re: Beginners Programming Challenge #20

Originally Posted by andrew1992
I figured reduce lends itself nicely to a recursive approach. Here's a concise Python example:

Code:
```def filter(function, list_):
return [i for i in list_ if function(i)]

def reduce(function, list_):
if len(list_) > 1:
list_ = [reduce(function, [function(list_[0], list_[1])] + list_[2:])]
return list_[0]```
Your reduce function does not have an initial value (see opening post). The initial value is needed to perform certain tricks with reduce. For example, when calculating the sum or the product of a list then the initial value should be 0 and 1 respectively. You can also have a different value to do something like computing the sum of a list plus a value n > 0 or multiplying all elements of a list with each other and a value n > 1.

9. A Carafe of Ubuntu
Join Date
Feb 2011
Location
Cambridge, ON, CAN
Beans
105
Distro
Ubuntu 10.10 Maverick Meerkat

## Re: Beginners Programming Challenge #20

Your example doesn't help me see why those initial values are needed. Let's say you want to take the product of all the values in a list [1, 2, 3, 4, 5]. With my algorithm, an initial value isn't necessary.

[1, 2, 3, 4, 5]
[2, 3, 4, 5]
[6, 4, 5]
[24, 5]
120

10. ## Re: Beginners Programming Challenge #20

Originally Posted by andrew1992
Your example doesn't help me see why those initial values are needed. Let's say you want to take the product of all the values in a list [1, 2, 3, 4, 5]. With my algorithm, an initial value isn't necessary.

[1, 2, 3, 4, 5]
[2, 3, 4, 5]
[6, 4, 5]
[24, 5]
120
In my examples the initial values indeed cancel out. But the initial value is nonetheless part of reduce and foldr/foldl functions in languages such as Haskell.

The reason for the intial value is that the types can differ. Your reduce function can only handle functions that take two values of the same type. It's a function that takes two int values and returns an int.

More abstractly we can say that it takes two values of type a and it returns a value of type a.

But we can also think of functions that take a value of type a, a value of type b and return a value of type a. This allows us to reduce a list of values of type b by starting with a value of type a.

The following example shows how this can be used:

Code:
```def f(a, b):
if b in a[1]:
return (a[0] + [b], a[1])
return a

def contains(my_words):
return reduce(f, my_words, ([], ["aaa", "bbb", "ccc"]))[0]

print contains(["aaa", "ddd", "bbb"])```
which will print:

Code:
`['aaa', 'bbb']`
In other words, we have a function called contains that shows all words from my_words that are also in the predefined list of words ["aaa", "bbb", "ccc"]. Note that we can only do this because the types of a and b in function f differ.
Last edited by simeon87; April 28th, 2011 at 02:54 PM.

#### Posting Permissions

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