Issues with emulating higher rank polymorphism

help
1

I want to write a trait which would express the following idea:

pub trait Foo {
    fn foo<F>(&self, f: F)
    // Hypothetical HKT syntax
    where
        F: for<G> FnOnce(G)
        G: for<const N: usize> Fn(&mut [Data; N]];
}

impl Foo for Bar {
    fn foo<F>(&self, f: F)
    where
        F: for<G> FnOnce(G)
        G: for<const N: usize> Fn(&mut [Data; N]];
    {
        // the first branch allows to process 4 `Data`s at once,
        // while the second one 8
        if runtime_cond() {
            f(|buf: &mut [Data; 4]| self.proc4(buf));
        } else {
            f(|buf: &mut [Data; 8]| self.proc8(buf));
        }
    }
}

Note that G and N must be fixed by a trait implementation and not by the method caller as you would get with the following method signature:

fn foo<F, G, const N: usize>(&self, f: F)
where F: FnOnce(G), G: Fn(&mut [Data; N]);

As a practical example, you can think about the first branch processing data using SSE2 and the second one using AVX2.

Unfortunately, Rust does not support HKT, so we can write such code in the desired straightforward and robust manner. But there is a way to emulate the desired higher rank polymorphism:

pub trait Foo {
    // the second argument of `fn` MUST have the same length as
    // the first argument of `FnOnce`
    fn foo(f: impl FnOnce(&mut [Data], fn(&Self, &mut [Data])));
}

impl Foo for Bar {
    fn foo(f: impl FnOnce(&mut [Data], fn(&Self, &mut [Data]))) {
        if runtime_cond() {
            let mut tmp: [Data; 4] = Default::default();
            f(&mut tmp, |s, data| {
                assert_eq!(data.len(), 4);
                s.proc4(data);
            })
        } else {
            // ..
        }
    }
}

It looks weird and somewhat unergonomic to use, but should do the job and with a bit of inlining from compiler we should not get any performance regressions.

Let's also introduce a mutable variant of the trait:

pub trait FooMut {
    fn foo_mut(f: impl FnOnce(&mut [Data], fn(&mut Self, &mut [Data])));
}

So far so good. But now we want to write the following blanket impls:

impl<T: Foo> FooMut for T {
    fn foo_mut(f: impl FnOnce(&mut [Data], fn(&mut Self, &mut [Data]))) {
        // ???
    }
}

impl<T: Foo> Foo for &T {
    fn foo(f: impl FnOnce(&mut [Data], fn(&Self, &mut [Data]))) {
        // ???
    }
}

// ideally it would've been nice to also write
// impl<T: FooMut> FooMut for &mut T { .. }
// but it results in conflicting impls

On the first glance the impls look straightforward, but the problem is that signature of the function pointer becomes incompatible. With a bit of unsafe code we can cast fn(&Self, &mut [Data])) to fn(&mut Self, &mut [Data])) (which could be sound) and write the first impl:

impl<T: Foo> FooMut for T {
    fn foo_mut(f: impl FnOnce(&mut [Data], fn(&mut Self, &mut [Data]))) {
        T::foo(|tmp, p| f(tmp, unsafe { core::mem::transmute(p) }));
    }
}

But I don't have any working ideas for the second blanket impl. The issue is that method accepts function pointer with a double reference, while inside blanket impl we have access only to a function pointer which accepts single reference. We can not capture the second pointer inside closure, since it will not be possible to use such closure as a function pointer.

Maybe you have ideas for working around this problem? Maybe there are solutions on horizon for automatically implementing Foo for &T/&mut T where T: Foo if the trait definition allows it?

2

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.