Functional programming in C using linked list

Question

How would you do a functionally pure linked list in C? Is a linked list what I should even be doing? I'm trying to have a list of objects but I can't think of how to add an item to the list from a function without modifying outside states.

I basically want this:

void AddItemToList(Item item);

To be able to be called from anywhere, without the caller having to worry about what list is being added to.

Right now I just have:

void AddTypeToList(entityType_t *type, entityType_t *listHead)
{
    type->next = listHead;
    listHead = type;
}

void RegisterEntityType(entityType_t *type)
{
    AddTypeToList(type, typeList);
}

But this is obviously not functional (or is it?) because RegisterEntityType is modifying typeList. (which is a global entityType_t)

Answer 1

You'd need a different function, generically speaking,

List AddItemToList(List list, Item item);

Because you should return a new list with the item added, without modifying the original list. This involves other questions, such as that a Garbage Collector should be needed in order to keep track of the intermediate lists your are going to create and discard.

I don't think that C is the best language to implement functional programming techniques, you'll have to build everything from the ground up. The obvious, ideal choice would be a pure functional programming language, or at least a programming language with support for functional techniques, such as for example C++, C# or Python.

Maybe you would like to check this question.

Hope this (somehow) helps.