# 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