Unable to pass generic function to another function


Recently I’m trying to implement sample code from the book “Understanding Computation”, and I ran into problem which I could not solve.
The problem comes from chapter 6: programming with nothing. It tries to write a “fizzbuzz” program with only Lambda Calculation. Here is the sample code:

Here is the step I tries. I implement them using function instead of lambda for clarity:

fn INCREMENT<T: Add<i32, Output = T>>(x: T) {x+1}
fn ZERO<F, T>(p: & F, x: T) -> T where F: Fn(T) -> T { x }
fn ONE<F, T>(p: & F, x: T) -> T where F: Fn(T) -> T { p(x) }

so far so good, I can write something like:
println!("{}", ZERO(&INCR, 0));
println!("{}', ONE(&INCR, 0));

However, I ran into problem when I tries to implement function to_integer (in helper.rb). I think it should be something like:

fn to_integer<F, T: Add<i32, Output=T>>(p: & Fn(& Fn(T) -> T, i32) -> i32) -> i32 { -p(&INCR, 0) }`

The compile says wrong:

type mismatch: 
the type `fn(&_, _) -> _ {ONE::<_, _>}` implements the trait `for<'r> core::ops::Fn<(&'r _, _)>`, 
but the trait `for<'r> core::ops::Fn<(&'r core::ops::Fn(_) -> _ + 'r, i32)>` is required

and I cannot figure out why
Could anyone help me figure out this.

ps, step-by-step thought:
First I let compiler tell me the type of p, I write:
fn to_integer(p: &()) -> i32 { p(&INCREMENT, 0) }
println!("{}", to_integer(&ONE));
get error:

expected `&()`,
found `&fn(&_, _) -> _ {ONE::<_, _>}`

So I write, by copy the interface of ONE:
fn to_int<F>(p: & Fn(F, i32) -> i32) -> i32 { p(&INCREMENT, 0) }
get error:

 expected `F`,
    found `&fn(_) -> _ {INCREMENT::<_>}`

OK, F should like INCREMENT, copying the interface:
fn to_int<F, T>(p: & Fn(& Fn(T) -> T, i32) -> i32) -> i32 { p(&INCREMENT, 0) }
and add Add trait to T:
fn to_int<F, T: Add<i32, Output=T>>(p: & Fn(& Fn(T) -> T, i32) -> i32) -> i32 { p(&INCREMENT, 0) }
get what I type above.


I might be reading your code wrong, but could it be that the function INCREMENT is missing its return type -> T?


That is my fault when typing the post, it is:
fn INCREMENT<T: Add<i32, Output = T>>(x: T) -> T {x+1}


It took me a while to figure it out, but the gist of it is that all the &s whenever you pass a function are unnecessary. This is because an expression like INCREMENT already is a function pointer, so no further referencing is necessary.

Basically, your functions ONE and ZERO should have a signature like this:

fn NAME<F, T>(p: F, x: T) -> T
    where F: Fn(T) -> T,
          T: Add<i32, Output = T>;

As for to_integer, you can determine its signature by what’s inside:


Because 0 is an i32, increment must be an fn(i32) -> i32.
Then p must be a function that takes both and produces an i32.
The result should be something like this:

fn to_integer<F>(p: F) -> i32
    where F: Fn(fn(i32) -> i32, i32) -> i32
    p(INCREMENT, 0)

Using this, you can write:

fn main() {
    println!("{}", to_integer(&ZERO));
    println!("{}", to_integer(&ONE));

Hope this helps and was somewhat understandable.


Thanks for your response, now I can compile it.
I think I can write it more generic:
In ZERO, ONE … it simply take a function that operates on T, no matter what it does and what type T is:

fn ONE<F, T>(p: F, x: T) 
  where F: Fn(T) -> T { p(x) }

Only INCREMENT need to specify what property T has:

fn INCREMENT<T>(x: T) -> T
  where T: Add<i32, Output=T>{ x+1 }
to_integer will be similar:
fn to_integer<F, T>(p: F) -> i32
  where F: Fn(fn(T)->T, i32) -> i32,
        T: Add<i32, Output=T> { p(INCREMENT, 0) }
Thank for your inspiring response.


After implement non-negative number, I ran into another trouble with IS_ZERO().
The concept is that, if we pass a function that always return false to ZERO, ONE, TWO, then only ZERO leave the value untouched.

Some related definition:

pub fn TRUE<T>(x: T, y: T) -> T { x } 
pub fn FALSE<T>(x: T, y: T) -> T { y } 
pub fn IF<F>(b: F) -> F { b } 
pub fn to_boolean<F>(p: F) -> bool
    where F: Fn(bool, bool)  -> bool { IF(p)(true, false) }

Here is the trouble when implement a function that take everything and return FALSE, or TRUE.

pub fn RETURN_FALSE<F, T>(p: F) -> (Fn(T, T) -> T) { FALSE }

Since the type of FALSE is specified, I got error:

trait `core::marker::Sized` is not implemented for the type `core::ops::Fn(T, T) -> T + 'static
 expected `core::ops::Fn(T, T) -> T + 'static`,
    found `fn(_, _) -> _ {solution::FALSE::<_>}`