GLists with a functional flavor

Project Euler offers a nice set of programming / math problems. Often, there's a brute-force solution and a nicer solution one finds after thinking about the math(s) a bit. When going through some of them using Guile (GNU's Scheme) and Mozilla's Rust, I noticed how elegantly many can be solved using not much besides lists/iterators and some higher-order functions such as filter, fold and map.

Good-old C doesn't support any of that of course, so typically you'd solve it with some blue-collar programming using explicit loops. However, it's actually not very hard to implement some of the higher-order goodness in C - I have done so, as part of GXLib (a library with some extensions for GLib).

Below are some examples. They are a bit artificial, but should show how things work. I'm assuming some knowledge of GList. Note that GXList is fully documented and comes with lots of examples.


Suppose we want to calculate the sum of prime numbers up to 100. We can decompose this into the following steps:

  • take a list of numbers (with gx_list_iota)
  • get a list with the items for which the predicate function gx_is_prime returns TRUE. gx_list_filter is the complement of g_list_remove_all.
  • take the sum of that list with gx_sum (which is just a convenient shorthand for a folding operation as discussed below)
int    sum;
GList *nums, *primes;

nums   = gx_list_iota (100, 1, 1);
primes = gx_list_filter (nums, (GXPred)gx_is_prime, NULL);
sum    = gx_list_sum (primes); /* => 1060 */

g_list_free (nums);
g_list_free (primes);

Note that predicate functions (GXPred) optionally takes a user-pointer; but we don't use it here; that's the NULL.

Mapping and folding

Mapping means creating a list consisting of the result of applying some function to each element of the original list. I.e., given a list [a,b,c] and some mapping function func, we create a list [func(a), func(b), func(c)].

GXLib has an _in_place version of this as well, which replaces the original values with the mapped ones.

Folding is often useful when we need to codense a list to a single value. I.e., given a list a [a, b, c], a folding function func and a 'seed' value init, we determine func (func (func (init , a), b), c).

Let's use this to find the greatest number in list of strings representing non-negative integers. We can decompose this into:

  • take a list of strings representing numbers
  • map that to a list of the corresponding numbers
  • find the maximum of that list, by folding it with gx_max.
int         greatest;
const char *numstrv[] = { "3", "48", "22", "73", "55" };
GList      *nums = gx_strv_to_list ((char**)numstrv, G_N_ELEMENTS(numstrv));

gx_list_map_in_place (nums, (GXBinaryFunc)atoi, NULL, NULL);
greatest = GPOINTER_TO_INT(gx_list_fold (nums, (GXTernaryFunc)gx_max,
                                         GINT_TO_POINTER(0), NULL, NULL));
g_assert_cmpint (greatest,==,73);
g_list_free (nums);

In the calls to gx_list_map_in_place and gx_list_fold, the first NULL is for a user-pointer; the second is for a function to free an element. We need neither here, hence the NULL.

If you worry about the performance versus hand-coding the loop: gx_max is an inline function, making it a zero-cost abstraction.


Compared to higher-level languages, what we lose here is a bit of syntactic sugar and some type-checking (and admittedly the casting looks a bit ugly).

When we can overlook that, it's actually a quite nice and clear way to decompose and solve problems - without straying too far from the 'bare metal'.

GXLib is still very young, but it's a good testing ground for implementing and using some of these features, and comes with a lot of examples and tests.

Published • 2015-10-04 | glib