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)

To have a functional linkedlist you would have to reconstruct the entire list with the extra element, or have a reverse linkedlist where you can just add the add the element to the front. — leppie
– leppie, Commented May 31, 2013 at 10:19
If you're serious about functional programming on data structures you should be familiar with this -- cs.cmu.edu/~rwh/theses/okasaki.pdf -- if you are not already. A more polished version is available in book form, same author. — High Performance Mark
– High Performance Mark, Commented May 31, 2013 at 10:33

Community · Accepted Answer · 2017-05-23 11:50:18Z

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.

edited May 23, 2017 at 11:50

CommunityBot

11 silver badge

answered May 31, 2013 at 10:56

Baltasarq

12.4k3 gold badges41 silver badges59 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Functional programming in C using linked list

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related