trait Church {
    /// T: an arbitrary parameter type
    /// E: an endomorphism on T
    fn eval<T, E: Fn(T) -> T>(&self, t: T, e: &E) -> T;
}

fn foo<C: Church>(c: C) {
    let bigly = |n: u64| -> u64 { n * 2 };
    let excitedly = |s: String| -> String {
        let mut result = String::new();
        result.push_str(&s);
        result.push_str("!");
        result
    };
    println!("{}", c.eval(10, &bigly));
    println!("{}", c.eval("hello".to_string(), &excitedly));
}

struct Zero;
impl Church for Zero {
    fn eval<T, E: Fn(T) -> T>(&self, t: T, _e: &E) -> T {
        t
    }
}

struct Succ<N: Church>(N);
impl<N: Church> Church for Succ<N> {
    fn eval<T, E: Fn(T) -> T>(&self, t: T, e: &E) -> T {
        e(self.0.eval(t, &e))
    }
}

fn main() {
    foo(Zero {});
    foo(Succ(Zero));
    for i in 2..5 {
        struct N(u64);
        impl Church for N {
            fn eval<T, E: Fn(T) -> T>(&self, t: T, e: &E) -> T {
                let mut result = t;
                for _ in 0..self.0 {
                    result = e(result);
                }
                result
            }
        }
        foo(N(i));
    }
}