Map & Filter in Scheme & C

mgcadmin 07-01-2025

To use map/filter/reduce on lists would for the longest time immediately identify you as a lisp hacker. Overtime the immense utility of these list operations have led to their being incorporated by more and more mainstream languages. Now you can find their usage in languages from python to Javascript, and even in Java via the Streams API. Once developers become accustomed to their usage, these operations soon become indispensible. While this increasing popularity has led to more developers being familiar with what it is they accomplish, they may not know how this is acutally performed.

For 99% of developers, thats good enough for them. For the rest of us, I'd like to take a peek under the hood at how Map & Filter are implemented in scheme, and then muse what such an implementation might look like in a language like C.  I hope by the end of this post you come away with a greater appreciation for these wonderful programming constructs.

Adding the First to the Rest

The first time I saw the code to implement map in scheme I couldn't help but be awestruck at the (to me) sheer brilliance of the function. The idea behind map is to apply a function to each element of a list, saving the result and returning the resultant list. In scheme, it looks like this:

(define empty? 
           (lambda (x) (eq x ())
)
(define map 
          (lambda (f lst) 
              (if (empty? lst) 
                  () 
                 (cons (map f (car lst)) (map f (cdr lst) ) )
              )
          )
)

Now, for those of you who down speak lisp, I'll help you to read the above code so you have a better idea of just why that is such a beautiful piece of code. The above lisp expressions reads like this:

"Define a function named map, which accepts two parameters, f and lst. If lst is equal to an empy list, then return an empty list. Otherwise, evaluate the result of applying function f to the first element of lst, adding the result to the front of the list which results from applying the function f to the remaining elements of lst".

If THAT isn't a recursive definition, I don't know what is. When I read that description I can imagine the function creeping along the input like a catepillar, inching its way forward as it consumes the input and creating the output. When trying to describe the C code shown below in such a succint manner we run into immediate barriers. It isnt even really possible because C is not declarative in nature like lisp. Exclaiming that we should "add the result of a function application to the rest of a list" cant be succintly expressed in a language that doesnt have function application or native list types.

So what gives? Aside from not having native lists, C also is lacking lambda expressions and first class functions. This requires us instead to use in addition to a user defined list type with structs, to use predefined procedures and function pointers to accomplish a similar functionality. It is ultimately doable, but as you can see, quite a bit is lost in the translation.

struct node {
    int info;
    node* next;
};

node* map(int (*func)(int), node* h) {
    if (h == NULL)
        return nullptr;
    node* t = malloc(sizeof(struct node));
    t->info = func(h->info);
    t->next = map(func, h->next);
    return t;
}

Map is a non-destructive operation - it isn't mutating the input list. Pay careful attention to the recursive call on map. You will notice that we are adding new nodes to the resultant list, as we move to the next node of the input list.

Unless the predicate says otherwise...

Filter has a similar overall structure to map, however instead of mapping the result of applying the function to the input, we are returning only those elements from the list which satisfy our requirements. Filter expects the provided function to be a predicate, which is an expression which when evaluated returns a boolean value.

(define filter 
            (& (f lst) 
                 (if (empty? lst) 
                   () 
                   (if (f (car lst)) 
                     (push (car lst) (filter f (cdr lst) ) ) 
                     (filter f (cdr lst) ) 
                   ) 
            )
)

Just as we did for map, if the value of lst is an empty list, we're done. Unlike for map however, we may not necessarily be adding an item to the result list at every invocation where the argument isnt nil. Instead, we need to ensure that the remainder of the list is still processed when the current element fails the predicate. This is accomplished by adding a call to filter - without the associated push operator - as the else branch of the if test.

And now in C:

node* filter(bool (*func)(int), node* h) {
    if (h == nullptr)
        return nullptr;
    if (func(h->info)) {
        node* t = new node(h->info);
        t->next = filter(func, h->next);
        return t;
    }
    return filter(func, h->next);
}

As far as C goes, this is actually a bit more "natural" than the implementation of map is. It's still not idiomatic C, but far closer and it's clear enough that it certainly doesn't need much explaination.

Anyway, todays post is short one as that's all I've got for today, so until next time, Happy Hacking.

---