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>

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);
}

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 {
  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);
}

Monad

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 
        );
}

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);
  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}