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.
Filtering
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
returnsTRUE
.gx_list_filter
is the complement ofg_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.
Summarizing
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