How to do Higher Order Composition in Rust?

Question

I have this function that works:

fn compose<A, B, C>(f: impl Fn(A) -> B, g: impl Fn(B) -> C) -> impl Fn(A) -> C {
    move |x: A| g(f(x))
}

I'd like to use currying in this situation, so that I can do:

/* THIS */
compose(f)(g)(x)

/* Instead of this */
compose(f, g)(x)

Is it even reasonable to think about making a macro such that this is possible?

compose(f)(g)(h)···(x)

I've managed to get something that's kinda similar to what I want:

fn compose<A, B, C, F: 'static, G: 'static>(f: F) -> impl Fn(G) -> Box<dyn Fn(A) -> C>
where
    F: Fn(A) -> B + Copy,
    G: Fn(B) -> C + Copy,
{
    move |g: G| Box::new(move |x: A| g(f(x)))
}

let inc = |x| x + 1;
let mult2 = |x| x * 2;

let inc_compose = compose(inc);

println!("{}", inc_compose(mult2)(3)); // 8

Now there's a new problem: when creating a higher-order function based on my compose function, I need to give the function a type dependent on another function:

let inc   = |x: usize| x + 1;
let mult2 = |x: usize| x * 2;
let mult3 = |x: usize| x * 3;

let inc_compose = compose(inc);

println!("{}", inc_compose(mult2)(3)); // 8

println!("{}", inc_compose(mult3)(3)); // ERROR: [rustc E0308] [E] mismatched types

Is there a way to avoid this error?

None of these similar posts answer my question:

• How do I emulate Lisp (apply) or (curry) in Rust?
• How to implement a multiple level currying function in Rust?
• How to invoke a multi-argument function without creating a closure?

The main reason is that I want currying to get the ability to do point-free programming.

Answer 1

In Rust, currying is hard. The strict type system, lifetimes, and nested impl traits not existing all conspire to ruin your day when you try. However, it is possible to create a macro to curry functions, and I did so for code golf at one point. The ungolfed version is here:

macro_rules! curry{
    (
        $f:ident
        $(
            ($args:ident : $types:ty)
        )*
    ) => {
        $(move |$args: $types|)*
        $f(
            $($args),*
        )
    }
}

This matches on expressions of the form name(arg1, type1)(arg2, type2)...(argN, typeN) and returns a chain of move closures leading to the function call. Most of the time, however, you can just use _ for the type and let inference figure it out. Using it with compose is simple:

let inc = |x| x as u32 + 1;
let double = |x| x * 2;
let curried = curry!(compose(f: _)(g: _));
assert_eq!(curried(inc)(double)(7), 16);

The code generated by the macro, in this case, looks like this:

move |f: _| move |g: _| compose(f, g)

It simply takes the supplied name and type and pastes it into the closure heads, so you can use it to force arguments for generic functions into concrete types. Playground