Zig CTFP

Let this blog post be living proof that Zig is in fact also a functional programming language.

What?

Well, there is a famous book called “Category Theory For Programmers” (in short, CTFP) that expresses a lot of the core ideas of functional programming through category theory. CTFP has a set of challenges at the end of each chapter, and I aim to do all of them in Zig.

Challenges

1.4.1

Implement, as best you can, the identity function in your favorite language (or the second favorite, if your favorite language happens to be Haskell).

For functional programming we will make heavy use of anonymous functions. So a recurring pattern we will see is the following:

struct {
    fn call(args) T {
        <function body here>
    }
}.call; // Notice this .call will make the expression return a function pointer.

Solution:

So this challenge becomes very easy:

fn id(comptime T: type) fn (T) T {
    return struct {
        fn call(x: T) T {
            return x;
        }
    }.call; // The .call for id.
}

PS.

Since we don’t have function type inference in zig, we will make use of types as values. So the function call looks like:

id(i32)(42);

Some may be somewhat bothered by this syntax. But I think this is still fair since C++’s version of id without type inference (ie. using templates) is:

id<int>(42);

1.4.2

Implement the composition function in your favorite language. It takes two functions as arguments and returns a function that is their composition.

This is still very similar to the previous challenge but we do it twice nested.

fn compose(A: type, B: type, C: type) fn (fn (B) C, fn (A) B) fn (A) C {
    return struct {
        fn call(f: fn (B) C, g: fn (A) B) fn (A) C {
            return struct {
                fn call(a: A) C {
                    return f(g(a));
                }
            }.call;
        }
    }.call;
}

Solution:

const square_one = compose(i32, i32, i32)(square, inc);

You might notice that this only works for unary functions… Maybe in the future I’ll find a way to compose stuff in a better way. (maybe structs to pass multiple parameters in a single parameter?)

1.4.3

Write a program that tries to test that your composition function respects identity.

For this we need to verify that:

1. f . id = f
2. id . f = f

Solution:

test "1.4.3" {
    const f = inc;
    const fid = compose(i32, i32, i32)(inc, id(i32));
    const idf = compose(i32, i32, i32)(id(i32), inc);
    try std.testing.expectEqual(fid(42), f(42));
    try std.testing.expectEqual(idf(42), f(42));
}

2.7.1

Define a higher-order function (or a function object) memoize in your favorite language. This function takes a pure function f as an argument and returns a function that behaves almost exactly like f, except that it only calls the original function once for every argument, stores the result internallly, and subsequently returns this stored result every time it’s called with the same argument. You can tell the memoize function from the original by watching its preformance. For instance, try to memoize a function that takes a long time to evaluate. You’ll have to wait for the result the first time you call it, but on sebsquent calls, with the same argument, you should get the result immediately.

This one’s a doozy… Basically we need to create a function that will memoize another function. As elegantly expressed in Closure Conversion: How to compile lambda a closure is simply a lambda that can capture its environment. The way we capture the environment is simply by adding more data fields to the struct! So we simply add a AutoHashMap as a data field to the struct.

fn memoize(comptime A: type, comptime B: type) fn (fn (A) B) type {
    return struct {
        fn call(comptime f: fn (A) B) type {
            return struct {
                var mp: std.HashMap(A, B, std.hash_map.AutoContext(A), 80) =
                    std.AutoHashMap(A, B).init(std.testing.allocator);

                fn call(a: A) B {
                    const val = mp.get(a);
                    if (val) |v| {
                        return v;
                    } else {
                        const new_val = f(a);
                        mp.put(a, new_val) catch {};
                        return new_val;
                    }
                }
                fn deinit() void {
                    mp.deinit();
                }
            }; // Notice there isn't a .call here. The caller must call this
               // closure with .call(args)
        }
    }.call;
}

Solution

And it works!

const memo_fib = memoize(i32, i32)(fib);
defer memo_fib.deinit();
try std.testing.expectEqual(fib(5), memo_fib.call(5)); }

2.7.2

Try to memoize a function from your standard library that you normally use to produce random numbers. Does it work?

Apparently, it does! But this is only because it is being executed with the same seed, at compiletime.

Solution:

Since I haven’t figured out how to pass functions with different arity, we must create a wrapper for the standard library’s rng. This function will get rid of that argument since we don’t need it to produce the random numbers.

fn rand(_: i32) i32 {
    const RndGen = std.rand.DefaultPrng; var rnd = RndGen.init(@as(u64, @bitCast(std.time.milliTimestamp())));
    return rnd.random().int(i32);
} // Helper function

const RndGen = std.rand.DefaultPrng;
var rnd = RndGen.init(@as(u64, @bitCast(std.time.milliTimestamp())));

const memo_rnd = memoize(i32, i32)(rand);
defer memo_rnd.deinit();

try std.testing.expectEqual(rnd.random().int(i32), memo_rnd.call(42));

La Fin

This is what I’ve gotten up until now. Zig’s syntax is ugly, and I’m not particularly excited about it’s design philosophy but damn is it a solid language. This little challenge has made me enjoy Zig a lot more than I thought.