Let's play around with functional programming in C.
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>
Let's start with some basic arithmetic functions:
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);
}
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);
}
For map
(and flatMap
below), we'll use a simple linked list:
typedef struct Cons {
int head;
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;
yi->head = f(xs->head);
xs = xs->tail;
while (xs != 0) {
yi->tail = malloc(sizeof(Cons));
yi = yi->tail;
yi->head = f(xs->head);
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->head = x;
xs->tail = malloc(sizeof(Cons));
xs->tail->head = y;
// ys = {x * x, y, * y}
Cons * ys = map(square, xs);
printf("{%d * %d, %d * %d} = ", x, x, y, y);
printf("{%d, %d}\n", ys->head, ys->tail->head);
}
We'll need a way to concatenate two linked lists:
Cons * concat(Cons * xs, Cons * ys) {
Cons * zs = malloc(sizeof(Cons));
Cons * zi = zs;
zi->head = xs->head;
xs = xs->tail;
while (xs != 0) {
zi->tail = malloc(sizeof(Cons));
zi = zi->tail;
zi->head = xs->head;
xs = xs->tail;
}
zi->tail = malloc(sizeof(Cons));
zi = zi->tail;
zi->head = ys->head;
ys = ys->tail;
while (ys != 0) {
zi->tail = malloc(sizeof(Cons));
zi = zi->tail;
zi->head = ys->head;
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 * ys = f(xs->head);
Cons * yi = ys;
xs = xs->tail;
while (xs != 0) {
yi = f(xs->head);
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->head = x;
xs->tail = malloc(sizeof(Cons));
xs->tail->head = x;
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->head = x;
xs->tail = malloc(sizeof(Cons));
xs->tail->head = y;
// 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"
, ys->head
, ys->tail->head
, ys->tail->tail->head
, ys->tail->tail->tail->head
);
}
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);
demoMonad(x, y);
return 0;
}
This post is literate C. Try running it with codedown:
$ curl -s https://earldouglas.com/posts/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}