Std.mem.sort lessThanFn type requirements

Help
1

Playing around with an insertion sort using the same arguments as std.mem.sort, I’m finding that my function works with a lessThanFn having anytype arguments, but I could not get std.mem.sort to allow such a function. Why does lessThan below work with my insertionSort but not with std.mem.sort?

Why would null, 1, and u16 be allowed as context by insertionSort, but not true or [_]u16{ 9001, 9002 } or {}, i.e., what do the working values have in common that is not shared by the failing values?

const std = @import("std");

const ElementType = u8;

fn lessThan(_: anytype, a: anytype, b: anytype) bool {
    return a < b;
}

fn lessThanExplicit(_: void, a: ElementType, b: ElementType) bool {
    return a < b;
}

pub fn main() !void {
    var items = [_]ElementType{ 2, 1, 3, 6, 4, 5, 9, 7, 8 };
    // All of these work.
    insertionSort(ElementType, &items, null, lessThan);
    // insertionSort(ElementType, &items, 1, lessThan);
    // insertionSort(ElementType, &items, u16, lessThan);
    // insertionSort(ElementType, &items, {}, lessThanExplicit);
    // std.mem.sort(ElementType, &items, {}, lessThanExplicit);

    // All of these fail.
    // insertionSort(ElementType, &items, true, lessThan);
    // insertionSort(ElementType, &items, [_]u16{ 9001, 9002 }, lessThan);
    // insertionSort(ElementType, &items, {}, lessThan);
    // std.mem.sort(ElementType, &items, null, lessThan);
    // std.mem.sort(ElementType, &items, 1, lessThan);
    // std.mem.sort(ElementType, &items, {}, lessThan);

    const stdout_file = std.io.getStdOut().writer();
    var bw = std.io.bufferedWriter(stdout_file);
    const stdout = bw.writer();
    try stdout.print("{any}\n", .{items}); // { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
    try bw.flush();
}

fn insertionSort(
    comptime T: type,
    items: []T,
    context: anytype,
    comptime lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) void {
    var i: usize = 1;
    while (i < items.len) : (i += 1) {
        var j = i;
        while (j > 0 and lessThanFn(context, items[j], items[j - 1])) : (j -= 1) {
            const t = items[j - 1];
            items[j - 1] = items[j];
            items[j] = t;
        }
    }
}
2

Welcome to the forum!

This is an interesting finding. The thing that null, 1, and u16 all have in common that true, [_]u16{ 9001, 9002 }, and {} do not is that they are comptime-only values: null has a special type @TypeOf(null) which is comptime-only but allowed to coerce to any optional type, 1 has type comptime_int, and u16 has type type.

For example, if you change the first insertionSort call to

insertionSort(ElementType, &items, @as(?u8, null), lessThan);

which gives the null a type that isn’t comptime only, it fails to compile:

t.zig:16:56: error: expected type 'fn (?u8, u8, u8) bool', found 'fn (anytype, anytype, anytype) bool'
    insertionSort(ElementType, &items, @as(?u8, null), lessThan);
                                                       ^~~~~~~~
t.zig:16:56: note: generic function cannot cast into a non-generic function
t.zig:41:26: note: parameter type declared here
    comptime lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool,
                         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

This also ties in to why you couldn’t get std.mem.sort to work with those values. If I uncomment

std.mem.sort(ElementType, &items, null, lessThan);

then I get this compile error:

/home/ian/opt/zig-0.14.1/lib/std/sort.zig:34:46: error: unable to resolve comptime value
    insertionContext(0, items.len, Context{ .items = items, .sub_ctx = context });
                                            ~^~~~~~~~~~~~~
/home/ian/opt/zig-0.14.1/lib/std/sort.zig:34:46: note: initializer of comptime-only struct 'sort.insertion__anon_24305.Context' must be comptime-known
/home/ian/opt/zig-0.14.1/lib/std/sort.zig:24:18: note: struct requires comptime because of this field
        sub_ctx: @TypeOf(context),
                 ^~~~~~~~~~~~~~~~

which is a bit difficult to understand because it’s pointing within the sort implementation, but the fundamental reason why it doesn’t work is because the compiler is trying to use the comptime-only type @TypeOf(null) in a context that requires a runtime value.

As for the reason for that error (“generic function cannot cast into a non-generic function”), I don’t know for sure, but my best guess would be that it’s trying to prevent a situation like this:

fn f(a: anytype) void {
    _ = a;
}

test {
    const g: *const fn (bool) void = &f;
}

where g ends up being a runtime-usable function pointer value, and the compiler would need to do some magic to ensure &f creates a proper instantiation of f with parameter type bool that can actually be compiled down to machine code that g can point to. (anytype has no concrete representation of its own that the compiler could emit a single function implementation for)

4 Likes
3

Thanks, that’s helpful.

This builds a comparison function for std.mem.sort. Is it the idiomatic way to do it?

fn lessThanForType(T: type) fn (void, T, T) bool {
    return struct {
        fn lessThanSimple(_: void, a: T, b: T) bool {
            return a < b;
        }
    }.lessThanSimple;
}

// Either of these works.
std.mem.sort(ElementType, &items, {}, lessThanForType(ElementType));
std.mem.sort(ElementType, &items, {}, lessThanForType(@TypeOf(items[0])));
4

The idiomatic way is to use std.sort.asc which is the same function. Or desc if you want to sort the other way.

But writing your own function is idiomatic in situations where you need to do something more complex, like only sorting based on a few fields etc.

1 Like
5

I saw std.sort.asc but wanted to understand how to set up something custom, like passing a context pointer to allow the comparison function to keep a count of its calls. For my post, I tried to make the simplest possible case.

When I found my custom comparison function worked with my own sort but failed with std.mem.sort, I was surprised, since both sorts have the same argument types.