Higher Order Functions

By Jonathan Bartlett
2005-05-13


Functions as function arguments
A practical use of nameless functions is that of building functions to pass as arguments to other functions. The best example of this is the Scheme built-in function map.

The map function takes two arguments: a function of one variable and a list. It then applies that function to each element of the list and returns a new list made up of the results. For example, using the square function, you can take a list of numbers and square them (as shown in Listing 3).

Listing 3. Passing functions as arguments to functions in Scheme

;Our function

(define square (lambda (x) (* x x)))



;Our data

(define my-test-data '(1 2 3 4 5 6))



;Create a new list as the squares of my-test-data

(define list-of-squares (map square my-test-data))



;Display results

(display list-of-squares)

(newline)

This is a pretty concise program compared with other languages. For example, in C the equivalent code would look like this code in Listing 4.

Listing 4. Passing functions as arguments to functions in C

int square(int x)

{

   return x * x;

}



int main()

{

   int my_test_data[6] = {1, 2, 3, 4, 5, 6};;

   int list_of_squares[6];

   int i;



   /* Note that this would only work if C had a function

    * called map which worked with integer functions.

    * It doesn't, so this is largely theoretical.  Also remember

    * that C doesn't know the size of the arrays, so you have to

    * pass it explicitly.  Also, list_of_squares has to be passed

    * as a parameter in C.

    */

   map(square, my_test_data, list_of_squares, 6);



   printf("(");

   for(i=0; i<6; i++)

   {

      printf("%d ", list_of_squares[i]);

   }

   printf(")\n");

}

Of course, in C, unless you use a type-tag mechanism like the one mentioned in the "Better programming through effective list handling" article, you will need a different function for every type of value used with map.

In addition to being more concise than C, coding such a function in Scheme has an additional advantage -- you don't need to name the function square. Because functions can be created and passed just like any other value in Scheme, the core of the code can be modified so that you don't even have to give your squaring function a name. You can just define it and pass it to map. In place of the variable name square you will instead have the definition of the function written as a lambda form. Listing 5 shows the code.

Listing 5. Passing anonymous functions as values

(define list-of-squares (map (lambda (x) (* x x)) '(1 2 3 4 5 6)))

(display list-of-squares)

(newline)

So why do it this way? Well, anonymous functions have several advantages over named functions when the function is only used once:

• The program namespace isn't polluted with a lot of functions that are only used once.
• The code for the function is located in the exact spot where it is used, therefore programmers don't have to go hunting for the code of tiny, one-use functions.
• The function is clearly associated with the function to which it's being passed, therefore it is obvious to other programmers in what context it is being used. If a one-use function is written separate from the calling function, if the calling function is later removed, it won't be obvious that the one-use function would need to be removed as well.

In short, using anonymous functions makes the code concise and easy to follow and makes it obvious to other programmers when a function is specialized for a single instance or specific use.

Also, as seen from the map function, passing functions as arguments allows you more control over what happens to your data downstream. In this instance, the map function iterated through each value in the list and then used your function to manage further processing of that list value. This allows function writers and users great flexibility -- you can create a function that allows the users of the function to plug in extra functionality by passing functions as arguments.

In addition to map, there are several other generic list-processing functions that take functions as parameters. These functions, or ones like them, are the backbone of any data-processing application. Using these generic functions takes a lot of the repetitiveness out of programming; otherwise you are left to code loops after loops that all essentially work the same way. Not only do you save time, you also have fewer opportunities to introduce bugs.

Following is a list of the most common generic list-processing functions:

• map takes a list and generates a new list by applying a user-supplied function to each list member.
• filter takes a list and generates a new list containing the members of the old list that match a user-specified condition.
• reduce takes a list and combines the values into a single value. This combining procedure can be summation, min-value, max-value, etc. In order to use this correctly, you need to use closures (which will be discussed in the section Building functions at runtime).

There are several other generic list-processing functions, but these are the basic ones that are easiest to learn and most widely used. Detailed descriptions of these functions are available through the links found in the Resources section.

Now that you've examined how to pass functions as arguments to other functions, let's look at how to write functions of your own that take functions as parameters.

Tutorial Pages:
» Using functions for such higher order purposes as arguments, function-generating functions, and anonymous functions
» Creating anonymous functions
» Functions as function arguments
» Using functions as arguments
» Building functions at runtime
» Functions and object-oriented programming
» Of the highest order
» Resources


First published by IBM DeveloperWorks

Related Tutorials: » How to Install PHP 5 on Linux » How to Install Apache 2 on Linux » How to Install MySQL 5.0 on Linux » SMB Caching » Mound --Bind » Tar Wild Card Interpretation