How to do Higher Order Composition in Rust?

user_13710847 0
Viewed 935

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:

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

rust functional-programming
1 Answers

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

user_151314910
Related