# Functional Programming in C

June 22, 2012

Let's play around with functional programming in C.

## Function pointer

We'll write an `eval` function that, given a pointer to a binary function, and given two inputs, applies the inputs to the function and returns the result.

We'll want to print to standard output with `printf`:

``#include <stdio.h>``

We'll also want to convert command line arguments into integers with `atoi`:

``#include <stdlib.h>``

``````int add(int x, int y) {
return x + y;
}

int sub(int x, int y) {
return x - y;
}

int mult(int x, int y) {
return x * y;
}``````

We'll need a way to evaluate an arbitrary binary function given two arguments:

``````int eval(int (*f)(int, int), int x, int y) {
int result = f(x, y);
return result;
}``````

Now we can pass a binary function, `f`, and a couple of inputs, `x` and `y`, to `eval`, which will apply the inputs to the function and return the result.

``````void demoFunctionPointer(int x, int y) {
int result = eval(mult, x, y);
printf("mult(%d, %d) = %d\n", x, y, result);
}``````

## Partial application

We'll need a way to store a partially-applied binary function and its first argument:

``````typedef struct {
int (*f)(int, int);
int x;
} K2;

K2 * partial2(int (*f)(int, int), int x) {
K2 * k = malloc(sizeof(K2));
k->f = f;
k->x = x;
return k;
}``````

And a way to completely apply it:

``````int apply2(int (*f)(int, int), int x, int y) {
return f(x, y);
}

int applyK2(K2 * k, int y) {
return apply2(k->f, k->x, y);
}``````

Here's an example where we partially apply the `mult` function, then completely apply it and print the result:

``````void demoPartialApplication(int x, int y) {
K2 * timesX = partial2(mult, x);
int result = applyK2(timesX, y);
free(timesX);
printf("mult(%d, %d) = %d\n", x, y, result);
}``````

## Functor

For `map` (and `flatMap` below), we'll use a simple linked list:

``````typedef struct Cons {
struct Cons * tail;
} Cons;``````

To map over it, we iterate through the list, building up another as we go:

``````Cons * map(int (* f)(int), Cons * xs) {
Cons * ys = malloc(sizeof(Cons));
Cons * yi = ys;

xs = xs->tail;

while (xs != 0) {
yi->tail = malloc(sizeof(Cons));
yi = yi->tail;
xs = xs->tail;
}

return ys;
}``````

To test this, we'll need a unary function:

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

Now we can square all the numbers in a list:

``````void demoFunctor(int x, int y) {
// xs = {x, y}
Cons * xs = malloc(sizeof(Cons));
xs->tail = malloc(sizeof(Cons));

// ys = {x * x, y, * y}
Cons * ys = map(square, xs);
printf("{%d * %d, %d * %d} = ", x, x, y, y);
}``````

We'll need a way to concatenate two linked lists:

``````Cons * concat(Cons * xs, Cons * ys) {
Cons * zs = malloc(sizeof(Cons));
Cons * zi = zs;

xs = xs->tail;

while (xs != 0) {
zi->tail = malloc(sizeof(Cons));
zi = zi->tail;
xs = xs->tail;
}

zi->tail = malloc(sizeof(Cons));
zi = zi->tail;
ys = ys->tail;

while (ys != 0) {
zi->tail = malloc(sizeof(Cons));
zi = zi->tail;
ys = ys->tail;
}

return zs;
}``````

Now we can iteratively build and concatenate lists from each element in a list:

``````Cons * flatMap(Cons * (* f)(int), Cons * xs) {
Cons * yi = ys;

xs = xs->tail;

while (xs != 0) {
ys = concat(ys, yi);
yi = yi->tail;
xs = xs->tail;
}

return ys;
}``````

To test this, we need a function that produces a list from a number:

``````Cons * repeat(int x) {
Cons * xs = malloc(sizeof(Cons));
xs->tail = malloc(sizeof(Cons));
return xs;
}``````

Now we can mix and match functions that return numbers with functions that return lists:

``````void demoMonad(int x, int y) {
// xs = {x, y}
Cons * xs = malloc(sizeof(Cons));
xs->tail = malloc(sizeof(Cons));

// ys = {x * x, x * x, y * y, y * y}
Cons * ys = flatMap(repeat, map(square, xs));
printf( "{%d * %d, %d * %d, %d * %d, %d * %d} = "
, x, x, x, x, y, y, y, y
);
printf( "{%d, %d, %d, %d}\n"
);
}``````

## Demo

Let's put it all together and run it from the command line:

``````int main(int argc, char *argv[]) {

int x = atoi(argv[1]);
int y = atoi(argv[2]);

demoFunctionPointer(x, y);
demoPartialApplication(x, y);
demoFunctor(x, y);

return 0;
}``````

This post is literate C. Try running it with codedown:

``````\$ curl https://earldouglas.com/fp-c.md |
codedown c |
gcc -o fp-c -x c -
\$ ./fp-c 6 7
mult(6, 7) = 42
mult(6, 7) = 42
{6 * 6, 7 * 7} = {36, 49}
{6 * 6, 6 * 6, 7 * 7, 7 * 7} = {36, 36, 49, 49}``````