CSC 270
Homework 7

Higher-order functions

In this assignment, we'll experiment with higher-order functions in various languages. Assume you already have some implementation of a list (the notion applies to things other than lists too, but these are the simplest examples I can think of). Implement the following operations:

countIf

takes in a list and a function from list elements to boolean (representing a "test" we can perform on individual list elements), and returns an integer telling how many of the list elements satisfy the test. For example, if we called countIf on the list of numbers {1,7,8,2,6,3,-4} and the "even" function, it would return 3 because there are 3 even numbers in that list. If we called countIf on the same list of numbers and a function that tells whether its argument is greater than 1, it would return 5 because 5 of the numbers in the list are greater than 1.

filterIf

takes in a list and a function from list elements to boolean, and returns a new list comprising only the list elements that pass the test (in the same order they were in before). For example, filterIf applied to {1,7,8,2,6,3,-4} and the "even" test would return the list {8,2,6}.

applyToEach

takes in a list and a function from list elements to some other type, and returns a list of the same length formed by applying the function to each list element. For example, applyToEach applied to {1,7,8,2,6,3,-4} and the "multiply by 3" function would return the list {3,21,24,6,18,9,-12}.

buildList

takes in a natural number n and a function f from natural numbers to some other type, and returns a list of length n consisting of {f(0),f(1),...f(n-1)} in that order.

After you've tried some of these, think about other situations in which you could make use of a function that takes in a function... or perhaps even a function that returns a function as its value... or even both! (An example of this is "derivative", which takes in a mathematical function and returns a different mathematical function.) Consider how you could rewrite the functions from homework 6 more briefly and elegantly using filterIf and applyToEach.

How you write higher-order functions varies considerably from one language to another:

Scheme

This is easier in Scheme than in any other language I know, since a Scheme function can easily use one of its parameters in function position (i.e. just after a left parenthesis). Thus for example

(define (do-twice f arg)
  (f (f arg)))
(do-twice sqr 3) "should be 81"
(do-twice 1+ 3) "should be 5"

Prolog

Prolog isn't really good at representing functions, but it can be done. For "functions returning boolean," the natural approach is to use a rule's success or failure; for "functions returning another type," use a two-place predicate that unifies the second argument with the result of the function on the first argument.

The remaining task is how to invoke a rule whose name you were given as a variable. Ideally, given variables Operator and Argument, you would simply ask Operator(Argument). But most implementations (including Amzi) consider that an error. There's a call/1 rule that takes in a complete question and asks it, e.g.

Question=even(6), call(Question).

which (assuming you've got an even/1 predicate working) should succeed.

However, call/1 requires that you have a whole question, not an operator and an argument separately. Again, you'd like to say something simple like call(Operator(Argument)) or Question = Operator(Argument), call(Question) And again, most implementations (including Amzi) consider these an error. So instead, you need to build up the question piece by piece:

functor(Question,Operator,1),
arg(1,Question,Argument),
call(Question).

To invoke a two-place predicate Operator(Arg1, Arg2), use

functor(Question,Operator,2),
arg(1,Question,Arg1),
arg(2,Question,Arg2),
call(Question).

and so on.

Java

The Java language doesn't allow you to pass functions as parameters, but you can do the next best thing: define a class consisting of a single method (and no instance variables), create an object of that class, and pass the object. A method that takes in such an object, naturally, needs to know what method to call on it; this is normally done by defining an interface specifying the method signature. Thus for example

interface IntToIntFunction {
   public int apply(int x);
   }
class AddOne implements IntToIntFunction {
   public int apply(int x) {
      return x+1;
      }
   }
class Square implements IntToIntFunction {
   public int apply(int x) {
      return x * x;
      }
   }
class Example {
   public int doTwice (IntToIntFunction f, int x) {
      return f.apply(f.apply(x));
      }
   }

C

In C, there is a data type "pointer to function", and one can take the address of a function. (In fact, referring to a function name without calling it is referring to its address, just as referring to an array name without subscripting it is referring to its base address.) Thus for example

int addOne(int x) {
        return x+1;
        }

int square(int x) {
        return x*x;
        }

int doTwice (int (*f)(int), int x) {
	return f(f(x));
/* which is really shorthand for
        return (*f)((*f)(x));     */

        }

int main () {
        printf ("doTwice(addOne, 3) should be 5: %d\n", doTwice(addOne, 3));
/* which is really shorthand for
        printf ("doTwice(&addOne, 3) should be 5: %d\n", doTwice(&addOne, 3)); */
        printf ("doTwice(square, 3) should be 81: %d\n", doTwice(square, 3));
        return 0;
        }

C++

Since C++ is supposed to be upward-compatible from C, the above C code should still work in C++. However, C++ adds an additional wrinkle: "pointers to member functions". You can read about these in Stroustrup, chap. 15.5.