Combinators in zig

Brainstorming
1

Trying to write a set of mutually recursive functions that were comptime (hence inlineable) and ran into this.

Can you write a function that takes a function body of the same type as the function itself?

const F = fn(comptime x: F, y: u32) u32; // compiler error for dependency loop

I think this generalizes more to: Can you write a combinator in comptime?

const L = fn(comptime x: L) L;

any ideas?

some background for fun: Fixed-point combinator - Wikipedia

2

Not sure if this is exactly what you’re looking for, but it compiles and runs:

const std = @import("std");

fn foo() bool {
    return true;
}

fn bar() bool {
    return false;
}

fn comb(func: anytype, coin: bool) @TypeOf(func) {
    return if (coin) func else bar;
}

pub fn main() !void {
    const f = comb(foo, false);
    std.debug.print("{}\n", .{f()});
}
3

Of course you can do anytype, but I was trying to define a type for the function. Clearly the compiler can do it, but can a user do it?

It’s just a programming puzzle. Nothing too serious.

edit: that’s doing it though. You would need to pass comb to comb (which probably works), but that’s not quite there. (ie, the function itself has to have the same signature as the function passed in).

4

No, you cannot define something with itself.
But you can have have pointers to that type, function pointers in your case.

A combinator is a high order function and higher order functions are common in zig.
But without closures and currying you cannot have the real Haskell thing.

5

I mean combinator in the lambda calculus sense. You don’t need currying or closures. There is only one type in that: const F = fn(x: F) F from there you can build up numbers (called Church numerals where the depth of the call is the number – crazy cool) and develop recursion (The infamous Y combinator).

comptime seems to have all the mechanics, but that dependency on itself seems to be the one thing it doesn’t like. That might just be a synax problem even, bc I think the compiler can represent it - i find it a fascinating question.