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);
("mult(%d, %d) = %d\n", x, y, result);
printf}
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;
* partial2(int (*f)(int, int), int x) {
K2 * k = malloc(sizeof(K2));
K2 ->f = f;
k->x = x;
kreturn 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) {
* timesX = partial2(mult, x);
K2 int result = applyK2(timesX, y);
(timesX);
free("mult(%d, %d) = %d\n", x, y, result);
printf}
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:
* map(int (* f)(int), Cons * xs) {
Cons * ys = malloc(sizeof(Cons));
Cons * yi = ys;
Cons
->head = f(xs->head);
yi= xs->tail;
xs
while (xs != 0) {
->tail = malloc(sizeof(Cons));
yi= yi->tail;
yi ->head = f(xs->head);
yi= xs->tail;
xs }
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}
* xs = malloc(sizeof(Cons));
Cons ->head = x;
xs->tail = malloc(sizeof(Cons));
xs->tail->head = y;
xs
// ys = {x * x, y, * y}
* ys = map(square, xs);
Cons ("{%d * %d, %d * %d} = ", x, x, y, y);
printf("{%d, %d}\n", ys->head, ys->tail->head);
printf}
We'll need a way to concatenate two linked lists:
* concat(Cons * xs, Cons * ys) {
Cons * zs = malloc(sizeof(Cons));
Cons * zi = zs;
Cons
->head = xs->head;
zi= xs->tail;
xs
while (xs != 0) {
->tail = malloc(sizeof(Cons));
zi= zi->tail;
zi ->head = xs->head;
zi= xs->tail;
xs }
->tail = malloc(sizeof(Cons));
zi= zi->tail;
zi ->head = ys->head;
zi= ys->tail;
ys
while (ys != 0) {
->tail = malloc(sizeof(Cons));
zi= zi->tail;
zi ->head = ys->head;
zi= ys->tail;
ys }
return zs;
}
Now we can iteratively build and concatenate lists from each element in a list:
* flatMap(Cons * (* f)(int), Cons * xs) {
Cons * ys = f(xs->head);
Cons * yi = ys;
Cons
= xs->tail;
xs
while (xs != 0) {
= f(xs->head);
yi = concat(ys, yi);
ys = yi->tail;
yi = xs->tail;
xs }
return ys;
}
To test this, we need a function that produces a list from a number:
* repeat(int x) {
Cons * xs = malloc(sizeof(Cons));
Cons ->head = x;
xs->tail = malloc(sizeof(Cons));
xs->tail->head = x;
xsreturn 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}
* xs = malloc(sizeof(Cons));
Cons ->head = x;
xs->tail = malloc(sizeof(Cons));
xs->tail->head = y;
xs
// ys = {x * x, x * x, y * y, y * y}
* ys = flatMap(repeat, map(square, xs));
Cons ( "{%d * %d, %d * %d, %d * %d, %d * %d} = "
printf, x, x, x, x, y, y, y, y
);
( "{%d, %d, %d, %d}\n"
printf, 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]);
(x, y);
demoFunctionPointer(x, y);
demoPartialApplication(x, y);
demoFunctor(x, y);
demoMonad
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}