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.