# 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` 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.

## 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