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.
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
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
Re: Beginners Programming Challenge #20
Quote:
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.
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.
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]
Re: Beginners Programming Challenge #20
Quote:
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 ;)
Re: Beginners Programming Challenge #20
Quote:
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.
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
Re: Beginners Programming Challenge #20
Quote:
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:
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.