Implementing function composition


#1

Hello,

For learning purpose, I’m trying to implement a compose function. I tried many variant of this code but none would compile.

https://play.rust-lang.org/?gist=d5d36fcc158da0673deffa1ca94de4fb&version=stable&backtrace=0

    fn comp<F, Fin, Fout, G, Gout, H>(g: G, f: F) -> H
        where
            F: Fn(Fin) -> Fout,
            G: Fn(Fout) -> Gout,
            H: Fn(Fin) -> Gout {
        |x| g(f(x))
    }

Compiler message :

error[E0308]: mismatched types
 --> <anon>:6:9
  |
6 |         |x| g(f(x))
  |         ^^^^^^^^^^^ expected type parameter, found closure
  |
  = note: expected type `H`
  = note:    found type `[closure@<anon>:6:9: 6:20 g:_, f:_]`

After that I unsuccessfully tried various cast of lambda to Fn. Any hint ?

Thank you for your time.


#2

The problem is that H is an input parameter. It’d be the same as if you said this:

fn show<T: Display>() -> T {
   "Hello, world"
}

This type signature is wrong, because it says I could call show::<u32> and get a u32, when show simply returns a string every time.

The way to solve this problem on stable right now is to use a trait object:

fn show() -> Box<Display> {
    Box::new("Hello, world")
}

fn comp<F, Fin, Fout, G, Gout>(g: G, f: F) -> Box<Fn(Fin) -> Gout>
where F: Fn(Fin) -> Fout, G: Fn(Fout) -> Gout {
    Box::new(|x| g(f(x))
}

#3

Thank you so much. I understand the problem now :slight_smile:

For future readers here is a compiling snippet :

https://play.rust-lang.org/?gist=5c95f12060e556fc35114dec3b04c5d0&version=stable&backtrace=0

fn comp<F: 'static, Fin, Fout, G: 'static, Gout>(g: G, f: F) -> Box<Fn(Fin) -> Gout>
    where 
    F: Fn(Fin) -> Fout,
    G: Fn(Fout) -> Gout {
    Box::new(move |x| g(f(x)))
}

fn main(){
    let inc = |x| x + 1;
    let half = |x| x / 2;
    assert!((comp(inc,half))(3) == 2)
}

PS: I had to add those static lifetime, still obscure to me, may not be the right thing to do.


#4

The reason you have to add those static lifetimes is that the return type has F and G inside of it, and is 'static, so they need to be 'static too. If you need F and G to not be 'static (say, because they capture a reference in their closure environment), you can write it like this:

fn comp<'a, F, G, Fin, Fout, Gout>(g: G, f: F) -> Box<Fn(Fin) -> Gout + 'a>
where F: Fn(Fin) -> Fout + 'a, G: Fn(Fout) -> Gout + 'a {
    Box::new(move |x| g(f(x)))
}

Whereas a Box<Fn(Fin) -> Gout> is 'static and can live forever, a Box<Fn(Fin) -> Gout + 'a> can only live as long as 'a.


#5

Very nice. I tried an implementation with macros [1] to clean up long lines of function invocations. I like that your implementation allows the resulting composed function to be evaluated later.

[1]: https://play.rust-lang.org/?gist=931dd68424cf4201ea9a0655a34b49cf&version=stable&backtrace=0