Higher Order Functions in Zig
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 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 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 expose a singular function that supports a mapper which receives the index of the element as well.
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 });
}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
Which is the two implementations
and mapImpl
. It is also quite easy to add support for another function signature, perhaps one where the third argument is the slice itself. Lets 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.mapIdxImpl
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 });
}I chose to make it easy for myself by utilising the
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.ArrayList
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);
}Again, we support two function signatures for the reducer function, which are the following.
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.