How to compose functions in rust?

Question

I'm trying to write a function that composes two functions, the initial design is pretty simple a function that takes two functions and returns a composed function which I can then compose with other functions, (since rust doesn't have rest parameters). But I've run into a long hard wall built with frustrating non-helpful compiler errors.

My compose function:

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

How I would like to use it:

fn main() {
    let addAndMultiply = compose(|x| x * 2, |x| x + 2);
    let divideAndSubtract = compose(|x| x / 2, |x| x - 2);

    let finally = compose(*addAndMultiply, *divideAndSubtract);
    println!("Result is {}", finally(10));
}

rustc doesn't like that, no matter what I try, trait bounds are never satisfied. The error is:

➜ cargo run                                                                                                                                               
   Compiling flowtree v0.1.0 (file:///home/seunlanlege/Projects/flowtree)
error[E0277]: the trait bound `std::ops::Fn(_) -> _: std::marker::Sized` is not satisfied
  --> src/main.rs:11:19
   |
11 |     let finally = compose(*addAndMultiply, *divideAndSubtract);
   |                   ^^^^^^^ the trait `std::marker::Sized` is not implemented for `std::ops::Fn(_) -> _`
   |
   = note: `std::ops::Fn(_) -> _` does not have a constant size known at compile-time
   = note: required by `compose`

error[E0277]: the trait bound `std::ops::Fn(_) -> _: std::marker::Sized` is not satisfied
  --> src/main.rs:11:19
   |
11 |     let finally = compose(*addAndMultiply, *divideAndSubtract);
   |                   ^^^^^^^ the trait `std::marker::Sized` is not implemented for `std::ops::Fn(_) -> _`
   |
   = note: `std::ops::Fn(_) -> _` does not have a constant size known at compile-time
   = note: required by `compose`

error: aborting due to 2 previous errors

error: Could not compile `flowtree`.

To learn more, run the command again with --verbose.

Answer 1

Just add references in finally and it will work:

fn main() {
    let addAndMultiply = compose(|x| x * 2, |x| x + 2);
    let divideAndSubtract = compose(|x| x / 2, |x| x - 2);

    let finally = compose(&*addAndMultiply, &*divideAndSubtract);
    println!("Result is {}", finally(10));
}

Dereferencing addAndMultiply or divideAndSubtract uncovers a trait object which is not Sized; it needs to either be wrapped in a Box or referenced in order for it to be passed to a function with a Sized constraint.

Answer 2

As @ljedrz points out, to make it work you only need to reference the composed functions again:

let finally = compose(&*add_and_multiply, &*divide_and_subtract);

(Note that in Rust, convention dictates that variable names should be in snake_case)

---

However, we can make this better!

Since Rust 1.26, we can use abstract return types (previously featured gated as #![feature(conservative_impl_trait)]). This can help you simplify your example greatly, as it allows you to skip the lifetimes, references, Sized constraints and Boxes:

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

fn main() {
    let add_and_multiply = compose(|x| x * 2, |x| x + 2);
    let divide_and_subtract = compose(|x| x / 2, |x| x - 2);

    let finally = compose(add_and_multiply, divide_and_subtract);
    println!("Result is {}", finally(10));
}

---

Finally, since you mention rest parameters, I suspect that what you actually want is to have a way to chain-compose as many functions as you want in a flexible manner. I wrote this macro for this purpose:

macro_rules! compose {
    ( $last:expr ) => { $last };
    ( $head:expr, $($tail:expr), +) => {
        compose_two($head, compose!($($tail),+))
    };
}

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

fn main() {
    let add = |x| x + 2;
    let multiply = |x| x * 2;
    let divide = |x| x / 2;
    let intermediate = compose!(add, multiply, divide);

    let subtract = |x| x - 2;
    let finally = compose!(intermediate, subtract);

    println!("Result is {}", finally(10));
}