Higher Order Functions in Zig

2025-07-08 · corrected 2026-10-29 · show originalshow corrected

Fixed the map signature: a mapper returns T, not G.
Fixed the notation of the function signatures.
Put the expected values first in the test assertions.
Explained adHocPolyT.
Added definitions of map, filter and reduce.
Fixed typos.
Written for Zig 0.14; std.ArrayList has since become unmanaged.

In a post about ad hoc polymorphism in Zig (see "Ad hoc polymorphism in Zig"), we explored how to implement ad hoc polymorphism in Zig. We will as a continuation on that exercise implement some higher order functions in Zig. Specifically, we will implement filter, map and fold (frequently referred to as reduce). The reason this is a continuation of the previous post is that we will be needing ad hoc polymorphism to support multiple function signatures for our procedural parameter (~~i.e~~i.e., our mapping, predicates and reducers). Doing some quick scouring of the internet regarding functional programming in Zig, you will find that the community is generally "against" it. I will not make any judgements on whether or not this is a good practice in Zig, rather, this is more of an exercise, or exploration of ideas.

Nevertheless, ~~lets~~let's start with perhaps the easiest one, map. The idea of mapping is quite simple, it takes a function and applies it to each element in a collection, and in a pure functional programming language, it would return a new collection with the results of the function applied to each element. This is indeed quite trivial to implement, to make things a bit more interesting, we will implement it in a way that allows us to expose a singular function that supports a mapper which receives the index of the element as well. The implementations are picked with adHocPolyT, the adHocPoly from the previous post that takes the expected return type as its first argument.

fn mapImpl(comptime T: type) fn (fn (T) T, []T) void {
    return (struct {
        fn e(mapper: fn (T) T, slice: []T) void {
            for (0..slice.len) |idx| {
                slice[idx] = @call(.auto, mapper, .{slice[idx]});
            }
        }
    }).e;
}

fn mapIdxImpl(comptime T: type) fn (fn (T, usize) T, []T) void {
    return (struct {
        fn e(mapper: fn (T, usize) T, slice: []T) void {
            for (0..slice.len) |idx| {
                slice[idx] = @call(.auto, mapper, .{ slice[idx], idx });
            }
        }
    }).e;
}

pub fn map(comptime mapper: anytype, slice: []typed.ParamType(mapper, 0)) void {
    adHocPolyT(void, .{
        mapper,
        slice,
    }, .{
        mapImpl(typed.ParamType(mapper, 0)),
        mapIdxImpl(typed.ParamType(mapper, 0)),
    });
}

test "test map mutable slice on i32 slice without args" {
    const allocator = testing.allocator;

    // [0, 1, 2]
    const slice = try range.rangeSlice(allocator, i32, 3);
    defer allocator.free(slice);

    map(mappers.inc(i32), slice);

    try testing.expectEqualSlices(i32, slice, &[_]i32{ 1, 2, 3 });
    try testing.expectEqualSlices(i32, &[_]i32{ 1, 2, 3 }, slice);
}

Now this is not a pure function because it has side effects. One can easily implement the same function but also taking an allocator as an argument, and instead returning a new allocated slice. I'll leave that as an exercise for the reader (don't forget that the caller has to free the memory as a result!). Our map function supports the two following function signatures, where the $\mathbb{N}$ argument is the index of the element. The mapper has to return $T$ , since its result is written back into the same slice

~~$\begin{cases} \text{T} \rightarrow \text{G} \\ \text{T, i} \in \N \rightarrow \text{G} \end{cases}$~~

f : \begin{cases} T \to T \\ T \times \mathbb{N} \to T \end{cases} \qquad \mathrm{map}(f, [x_0, \dots, x_{n-1}]) = [f(x_0), \dots, f(x_{n-1})]

~~Which is~~These are the two implementations mapImpl and mapIdxImpl. It is also quite easy to add support for another function signature, perhaps one where the third argument is the slice itself. ~~Lets~~Let's continue with the implementation of filter, the idea here is that we want to supply a predicate function which decides whether an element should be included in the resulting slice or not. Although a bit more complicated than map (due to memory management), the implementation is still quite straightforward.

fn filterImpl(comptime T: type) fn (Allocator, fn (T) bool, []T) Allocator.Error![]T {
    return (struct {
        fn e(allocator: Allocator, pred: fn (T) bool, slice: []T) Allocator.Error![]T {
            var filtered_list = try std.ArrayList(T).initCapacity(allocator, slice.len);

            for (slice[0..]) |item| {
                if (@call(.auto, pred, .{item})) {
                    filtered_list.appendAssumeCapacity(item);
                }
            }

            return try filtered_list.toOwnedSlice();
        }
    }).e;
}

fn filterIdxImpl(comptime T: type) fn (Allocator, fn (T, usize) bool, []T) Allocator.Error![]T {
    return (struct {
        fn e(allocator: Allocator, pred: fn (T, usize) bool, slice: []T) Allocator.Error![]T {
            var filtered_list = try std.ArrayList(T).initCapacity(allocator, slice.len);

            for (slice[0..], 0..) |item, idx| {
                if (@call(.auto, pred, .{ item, idx })) {
                    filtered_list.appendAssumeCapacity(item);
                }
            }

            return try filtered_list.toOwnedSlice();
        }
    }).e;
}

pub fn filter(allocator: Allocator, comptime predicate: anytype, slice: []typed.ParamType(predicate, 0)) ![]typed.ParamType(predicate, 0) {
    return adHocPolyT(
        Allocator.Error![]typed.ParamType(predicate, 0),
        .{ allocator, predicate, slice },
        .{
            filterImpl(typed.ParamType(predicate, 0)),
            filterIdxImpl(typed.ParamType(predicate, 0)),
        },
    );
}

test "test filter on i32 slice" {
    const allocator = testing.allocator;
    const slice = try rangeSlice(allocator, i32, 6);
    defer allocator.free(slice);
    const even = try filter(
        allocator,
        predicates.even(i32),
        slice,
    );
    defer allocator.free(even);

    try testing.expectEqualSlices(i32, even, &[_]i32{ 0, 2, 4 });
    try testing.expectEqualSlices(i32, &[_]i32{ 0, 2, 4 }, even);
}

I chose to make it easy for myself by utilising the ArrayList data structure in the standard library. This is obviously not necessary and can be done just by allocating and resizing a new slice, but again, it makes it quite easy to just use ArrayList. Again, we support multiple function signatures on the predicate function, which are the following.

~~$\begin{cases} \text{T} \rightarrow \text{bool} \\ \text{T, i} \in \N \rightarrow \text{bool} \end{cases}$~~

p : \begin{cases} T \to \mathrm{bool} \\ T \times \mathbb{N} \to \mathrm{bool} \end{cases} \qquad \mathrm{filter}(p, [x_0, \dots, x_{n-1}]) = [\, x_i \mid p(x_i) \,]

The kept elements stay in their original order.

Lastly, we will implement reduce. The idea of reduce is to take a slice of elements and reduce it to a single value by applying a function to each element in the slice, and accumulating the result, essentially reducing the dimension of our data by 1. Again, the implementation is quite straightforward. Since Zig does not really have the concept of a default zero-value, like a language such as Go has, we need to provide a default value for the initial value of the accumulator.

fn reduceImpl(comptime T: type, comptime G: type) fn (fn (G, T) G, []T, G) G {
    return (struct {
        fn e(reducer: fn (G, T) G, slice: []T, initial_value: G) G {
            var accumulator: G = initial_value;

            for (slice[0..]) |item| {
                accumulator = @call(.auto, reducer, .{ accumulator, item });
            }

            return accumulator;
        }
    }).e;
}

fn reduceIdxImpl(comptime T: type, comptime G: type) fn (fn (G, T, usize) G, []T, G) G {
    return (struct {
        fn e(reducer: fn (G, T, usize) G, slice: []T, initial_value: G) G {
            var accumulator: G = initial_value;

            for (slice[0..], 0..) |item, idx| {
                accumulator = @call(.auto, reducer, .{ accumulator, item, idx });
            }

            return accumulator;
        }
    }).e;
}

pub fn reduce(comptime reducer: anytype, slice: []typed.ParamType(reducer, 1), initial_value: typed.ReturnType(reducer)) typed.ReturnType(reducer) {
    return adHocPolyT(
        typed.ReturnType(reducer),
        .{ reducer, slice, initial_value },
        .{
            reduceImpl(typed.ParamType(reducer, 1), typed.ReturnType(reducer)),
            reduceIdxImpl(typed.ParamType(reducer, 1), typed.ReturnType(reducer)),
        },
    );
}

test "test reduce slice on i32 slice" {
    const allocator = testing.allocator;
    const slice = try allocator.alloc(i32, 3);
    @memcpy(slice, &[_]i32{ 1, 2, 3 });
    defer allocator.free(slice);
    const result = reduce(
        reducers.sum(i32),
        slice,
        0,
    );

    try testing.expectEqual(result, 6);
    try testing.expectEqual(6, result);
}

Again, we support two function signatures for the reducer function, which are the following.

~~$\begin{cases} \text{G, T} \rightarrow \text{G} \\ \text{G, T, i} \in \N \rightarrow \text{G} \end{cases}$~~

f : \begin{cases} G \times T \to G \\ G \times T \times \mathbb{N} \to G \end{cases} \qquad \mathrm{reduce}(f, [x_0, \dots, x_{n-1}], g) = f(\cdots f(f(g, x_0), x_1) \cdots, x_{n-1})

That is a left fold: the accumulator starts at the initial value $g$ and takes in the elements from left to right, so for an empty slice the result is $g$ itself.

All of this code is available on my github for reference. You may have noticed some utility functions that were used to correctly type some things, they can be found here.