FP-inspired C

list.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#include "list.h"

/*
 * A singly linked list and functions implemented in functional-style C.
 * Primary features/novelties:
 *  - no explicit loop constructs (for, while)
 *  - use of higher-order functions (within C's own restricitons)
 */



/*
 * full definition of node
 */
struct _list_node {
    struct _list_node * next;
    void * value;
}; // aka node

/*
 * node * make( int value )
 *  - allocates and creates a list node with the given value
 */
node * make(void * value) {
    node * new_node = (node*) calloc(sizeof(node), 1);
    new_node->value = value;
    return new_node;
}

/*
 * void * value( node * e )
 *  - returns the value of the given list element
 */
void * value(node * e) {
    return (void *)e->value;
}

static inline bool _has_next(node * e) {
    return e;
}

// implementation behind most iteration functions
// map, each, each_with, etc.
static inline node * _each(node * base, node * next, predicate iter_check, iterator fn, void * with) {
    if (iter_check(next)) {
        fn(next, with);
        return _each(base, next->next, iter_check, fn, with);
    } else {
        return base;
    }
}

static inline bool _not_last(node * e) {
    return e && e->next;
}

/*
 * but_last( node * list, iterator fn )
 *  - calls fn(e) for all but the last element of the list
 */
node * but_last(node * list, iterator fn) {
    return _each(list, list, _not_last, fn, NULL);
}

/*
 * node * last( node * list )
 *  - returns the last element of the list
 */
node * last(node * list) {
    if (list->next)
        return last(list->next);
    else
        return list;
}


// implementation for filter()
static inline node * _filter(node * list, node * next, predicate chk) {
    if (!next || !next->next) {
        return list;
    }
    if (chk(next->next)) {
        node * tnext = next->next->next;
        free(next->next);
        next->next = tnext;
    }
    return _filter(list, next->next, chk);
}

/* node * filter( node * list, predicate check )
 *  - removes all elements from the list that the check function returns true
 *  for
 */
node * filter(node * list, predicate chk) {
    if (list) {
        if (chk(list)) {
            node * tnext = list->next;
            free(list);
            return filter(tnext, chk);
        } else {
            return _filter(list, list, chk);
        }
    } else {
        return list;
    }
}

/*
 * node * each( node * list, iterator fn )
 *  - call fn for every element in list
 *  - fn can modify element
 */
node * each(node * list, iterator fn) {
    return _each(list, list, _has_next, fn, NULL);
}

// implementation behind foldl
static inline void * _foldl(node * list, node * next, iterator fn, void * acc) {
    if (next)
        return _foldl(list, next->next, fn, fn(next, acc));
    else
        return acc;
}

/*
 * void * foldl( node * list, iterator fn, void * accumulator )
 *  - apply fn( element, accumulator ) to each element in list
 *  - returns accumulator
 */
void * foldl(node * list, iterator fn, void * initial) {
    return _foldl(list, list, fn, initial);
}


/*
 * node * each( node * list, iterator fn )
 *  - call fn for every element in list, passing provided data
 *  - fn can modify element
 */
node * each_with(node * list, iterator fn, void * w) {
    return _each(list, list, _has_next, fn, w);
}

// an iterator that takes a map_fn as an argument so that map can be written
// in terms of _each
static inline void * mapper(node * n, void * f) {
    map_fn *fn = (map_fn*)f;
    n->value = fn(n);
    return f;
}

/*
 * node * map( node * list, map_fn fn )
 *  - apply fn to each element in the list
 *  - replaces the value of each element with the result of fn
 */
node * map(node * list, map_fn fn) {
    return _each(list, list, _has_next, mapper, fn);
}

// implementation behind append()
static inline node * _append(node * base, node * next, node * new) {
    if (next && !next->next) {
        next->next = new;
        return base;
    } else {
        return _append(base, next->next, new);
    }
}

/*
 * node * append( node * list, node * new )
 *  - appends a new element to the end of list
 */
node * append(node * list, node * new) {
    if (list) {
        return _append(list, list, new);
    } else {
        return new;
    }
}

/*
 * node * prepend( node * list, node * new )
 *  - prepends new node to the front of list
 *  - returns new list by necessity
 */
node * prepend(node * list, node * new) {
    new->next = list;
    return new;
}

// implementation behind reverse
static inline node * _reverse(node * head, node * remainder) {
    if (remainder) {
        node * next = remainder->next;
        head = prepend(head, remainder);
        return _reverse(head, next);
    } else {
        return head;
    }
}

/*
 * node * reverse( node * list )
 *  - reverses the order of the elements in list
 */
node * reverse(node *list) {
    if (list) {
        node * next = list->next;
        list->next = NULL;
        return _reverse(list, next);
    } else {
        return list;
    }
}

// counting iterator
static inline void * counter(node * e, void * vcount) {
    int * total = (int*) vcount;
    if (e)
        *total = *total + 1;
    return total;
}

/*
 * int len( node * list )
 *  - returns the number of elements in list
 */
int len(node * list) {
    int total = 0;
    foldl(list, counter, &total);
    return total;
}

list.h

#pragma once

typedef struct _list_node node;
typedef bool (predicate)(node *);
typedef void * (iterator)(node *, void *);

// TODO: implement sorting
typedef int (cmp)(node *, node *);

typedef void * (map_fn)(node *);
node * make(void * value);

void * value(node * e);
node * filter(node * list, predicate chk);
node * each(node * list, iterator fn);
node * but_last(node * list, iterator fn);
node * last(node * list);
node * each_with(node * list, iterator fn, void * w);
void * foldl(node * list, iterator fn, void * initial);
node * map(node * list, map_fn fn);
node * append(node * list, node * new);
node * prepend(node * list, node * new);
node * reverse(node *list);
int len(node * list);

#define complement(_original_, _complement_) \
    static inline bool _complement_(node * e) { \
        return !_original_(e); \
    }

#define getter(_type_, _name_) \
    static inline _type_ _name_(node * e) { \
        return (_type_)value(e); \
    }

#define maker(_type_, _name_) \
    static inline node * _name_(_type_ v) { \
        return make((void *)v); \
    }

#define def_list(_type_, _name_) \
    getter(_type_, _name_##_value) \
    maker(_type_, _name_##_init)

// TODO: Implement embeddable lists
// struct my_list {
//     int my;
//     int data;
//     node list;
// };
//
// will require fully-defined node type and a bunch of other changes

#define embedded_getter(_container_, _member_, _name_) \
    static _container_ _name_(node * e) { \
        void * p = (void *)e - offsetof(_container_, _member_); \
        return (_container_ *)p; \
    }

#define embedded_list(_container_, _member_, _name_) \
    embedded_getter(_container_, _member_, _name_##_value)

Makefile

CFLAGS += --std=c11 -Wall -Wextra -Winline -finline-functions
CFLAGS += -O3
CFLAGS += -save-temps
# CFLAGS += -g
#LDFLAGS += -flto

run_tests: tests
	./tests

$(wildcard *.o): list.h

tests: tests.o list.o range.o

tests4: tests.c list.c range.c
	$(CC) $(CFLAGS) -O4 -o $@ $^

fast: range.c list.c tests.c
	$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^

%.S:%.c
	$(CC) -O3 -S $< -o $@

clean:
	-rm *.o *.i *.s *.res *.out tests fast tests4

range.c

#include "range.h"

static inline void * _range(int start, int end, int step, iter fn, void *d) {
    if (start == end)
        return d;
    else
        return _range(start + step, end, step, fn, fn(start, d));
}

void * range(int start, int end, iter fn, void *d) {
    if (start > end)
        return _range(start, end, -1, fn, d);
    else
        return _range(start, end, 1, fn, d);
}

range.h

#pragma once

typedef void *(iter)(int, void *);
void * range(int start, int end, iter fn, void *d);

tests.c

#include <stdbool.h>
#include <stdio.h>

#include "list.h"
#include "range.h"

def_list(int, ilist);

static inline bool odd(node * e) {
    if (ilist_value(e) % 2 != 0)
        return true;
    else
        return false;
}

//complement(even, odd);

static inline void * doubler(node * e) {
    return (void *)(ilist_value(e) * 2);
}

static inline void * new_node(int i, void * vl) {
    node * list = (node*)(vl);
    return append(list, ilist_init(i));
}

static inline void * printer(node * e, void * _) {
    printf("%d,", ilist_value(e));
    return _;
}

static node * list_print(node * list) {
    but_last(list, printer);
    printf("%d\n", ilist_value(last(list)));
    return list;
}

int main(void) {
    node * list;
    node * long_list = range(1, 10000, new_node, 0);
    printf("len: %d\n", len(long_list));

    list = range(1, 30, new_node, 0);
    list = list_print(list);
    list = filter(list, odd);
    list = list_print(list);
    list = map(list, doubler);
    list = list_print(list);
    list = reverse(list);
    list = list_print(list);

    printf("len: %d\n", len(list));
    return 0;
}