It's not a secret that for almost all people attempting to learn C pointers are a grey area. I personally was struggling quite a lot understanding them but I was saved by a huge amount of amazing guides on pointer usage you can find online. That said, I still feel like implementation of higher order functions in C deserves more exposure that it currently has and this article is my attempt to contribute to this cause.

Note: In this article I'm gonna assume that you have some experience with C and know what pointers are. Additionally, I will assume you know how to write and compile .c files.

What are higher order functions?

Higher order functions take other functions as their arguments or return new functions when they terminate. It might sound confusing especially if you've never seen it being done before but in reality it is really quite simple. Consider the pseudocode below:

reverse(string)
    -- Some code to reverse the string
    return string

uppercase(string)
    -- Some code to convert string to uppercase
    return string

apply(string, operation)
    return operation(string)

hello := "hello"

-- Reverse the string
hello := apply(hello, reverse)

-- Convert the string to uppercase
hello := apply(hello, uppercase)

To summarise: apply() function above takes 2 parameters: a string and an another function. Then, as the name implies, it applies the operation to the supplied string and returns whatever comes out. This results in a very interesting form of polymorphism: our apply() function can take any operation regardless of what it does as long as it accepts a string as an argument and returns the string afterwards.

The example above looks at the scenario when a function takes other functions as its arguments. Now let's take a look at functions that return new functions:

multiplyOperation(coefficient)
    -- Declare new function that multiplies the
    -- supplied argument by the coefficient
    operation(number)
        return number * coefficient
    -- Return the new function
    return operation

-- Function that multiplies everything by 5
multiplyBy5 := multiplyOperation(5)

-- This will return 35
multipleBy5(7)

As seen above, multiplyOperation() returns a new function that changes its behaviour depending on what value for the coefficient has been supplied to multiplyOperation(). Keep in mind that the examples above are just pseudocode to give you an idea of what higher order functions are about and C implementation will not necessarily look the same.

Function pointers in C

To achieve the functionality discussed in the previous section we're gonna use function pointers, which are pretty straightforward and shouldn't take you too long to wrap your head around. Before we start, remind yourself of these 2 things:

• You can get the address of a variable using the & operator, like so: int *a = &b; (a can now be used as a pointer to b). That said, when referencing a function you are allowed to drop the & operator. If you still don't have that much experience with pointers, I recommend leaving it in.
• Before you can access the variable a pointer is pointing to, you must dereference said pointer. Let's take integer pointer a from the line above - if I want to use it in a calculation, I need to dereference it using the * operator: int c = 3 + *a;.

// Required for the `printf()` function
#include <stdio.h>

// The function we'll be pointing to
int halve(int number) {
    return number / 2;
}

void main() {
    // Declare a pointer to the `halve` function
    // We say that operation takes 1 int argument
    // and returns an int when it terminates
    int (*operation)(int) = &halve;

    // Alternatively, you can drop the `&`:
    int (*anotherOperation)(int) = halve;
    // From here onwards, I will always drop the
    // `&` to make the code a bit more concise

    // Dereference the pointer to `halve` first,
    // then supply relevant arguments to it
    int halved = (*operation)(10);

    // Should print `5`, try it yourself
    printf("%d", halved);
}

As you can see in the beginning of the main() method, pointers to functions have a rather unusual type declaration. It consists of 3 parts:

1. The type before the parenthesis is the return type of the function the pointer is referencing.
2. The middle part is the name of the pointer. Note that you have to wrap it into parenthesis to indicate that this a pointer to a function.
3. The last part contains the types of parameters the function is expecting.

For example, the type for a pointer to a function that accepts 2 character arrays and returns a double would look as follows: double (*someFunction)(char*, char*).

Implementing the map() function

As an exercise, let's implement the infamous map() function. This function takes 2 arguments:

1. Some unary function that accepts an argument of type A and returns some value of type B.
2. An array of type A. Keep in mind, type A can be the same as type B.

The return value is a new array of type B. This new array is generated by applying the supplied unary function to every element in the supplied array of type A.

map() for integers

To make our lives easier we will only work with integers (for now). Below you can find the implementation of the map() function that only works with unary operations on integers and integer arrays.

// Required for the `printf()` function
#include <stdio.h>
// Required for memory management
// (`malloc()`, `free()`, etc.)
#include <stdlib.h>

// Multiply a number by 3
int triple(int number) {
    return number * 3;
}

// A rather complex function definition, read more about it below
int *map(int (*function)(int), int *array, int size) {
    // Allocate memory for our new array
    int *newArray = malloc(sizeof(int) * size);

    int i;
    // Apply the function to every element of the supplied
    // array and save the values into the new array
    for (i = 0; i < size; i++) {
        newArray[i] = function(array[i]);
    }

    // Return the pointer to the new array
    // (you must free the memory after
    // you're done working with it)
    return newArray;
}

void main() {
    // Initial array of size 4
    int array[4] = {1, 2, 3, 4};

    // Map the array above using the `triple()` function
    int *tripledArray = map(triple, array, 4);

    int i;
    // Print the new values
    for (i = 0; i < 4; i++) {
        printf("%d ", tripledArray[i]);
    }

    // Don't forget to free the memory afterwards
    free(tripledArray);
}

I tried to add comments to all of the important parts but I want to discuss the map() function definition separtely. Let's break it down: int* map(int (*function)(int), int* array, int length) {...}

• As in any other function, the first part (int*) denotes the return type of our map(). In this particular case it's a pointer to an integer array.
• map is simply the function name, nothing fancy here.
• Now the interesting part - function parameters. There are of them:
  1. int (*function)(int) Defines a parameter called function that is a pointer to a function accepting one integer and returning an integer.
  2. int* array A pointer to an integer array over which we'll be iterating.
  3. int size Integer storing the size of the above array.

Now, we can use our newly defined function to "transform" integer arrays using some unary function. Unfortunately we did not make it truly polymorphic, that is it only works with integers but there is a very good reason for it: polymorphism in C is quite a complicated topic and it goes beyond the scope of this article. If you're interested in an implementation of the map() function that supports generic types, check out this.

Functions returning functions

This section will look at the other type of higher order functions, namely functions that return other functions after they terminate. Below you can see the implementation of a function that does exactly that: it returns binary arithmetic operations based on the value of the type parameter supplied to it.

// Required for `printf()`
#include <stdio.h>

// Binary arithmetic functions we'll be
// returning from `getOperation()`
int multiply(int x, int y) {
    return x * y;
}
int add(int x, int y) {
    return x + y;
}

// Function returning different binary functions
// based on the supplied integer type.
// Check below this code block for more info.
int (*getOperation(int type))(int, int) {
    switch (type) {
        case 0:
            // If type `0` return multiplication
            return multiply;
        case 1:
            // If type `1` return addition
            return add;
        default:
            // If type is not recognised
            // return addition
            return add;
    }
}

void main() {
    // Numbers which we'll send to our binary functions
    int x = 4;
    int y = 2;

    // Getting pointers to binary functions using `getOperation()`
    int (*multiplication)(int, int) = getOperation(0);
    int (*addition)(int, int) = getOperation(1);

    // Confirm that correct functions were returned
    printf("Multiplication: %d\n", multiplication(x, y));
    printf("Addition: %d\n", addition(x, y));
}

Take a look at the function definition for getOperation(): Its return type is "outside" and the actual definition that matches the function body is "inside" the parentheses. Let's break it down:

      getOperation                      // Name of the function
      getOperation(int type)            // Parameters the function is expecting
    (*getOperation(int type))(int, int) // Parameters of the returned function
int (*getOperation(int type))(int, int) // Return type of the returned function

Conclusion

The aim of this article is to give you a basic idea of how to define functions that accept other functions as parameters and return new functions. If after having read it you feel like you can do it, then this article has successfully fulfilled its purpose. Otherwise, feel free to comment below for help.