June 22, 2012

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}
```