Typing the Y combinator in Rust

y.rs

// Typing the Y combinator in Rust.
// $ rustc y.rs -o y
// $ .y
// 720
// Succ(Succ(Succ(Succ(Succ(Succ(Zero))))))

use std::fmt;

trait Apply<A, B> {
    fn apply(&self, f: &dyn Apply<A, B>, x: A) -> B;
}

impl<A, B, F> Apply<A, B> for F where F: Fn(&dyn Apply<A, B>, A) -> B {
    fn apply(&self, f: &dyn Apply<A, B>, x: A) -> B {
        self(f, x)
    }
}

fn y<A, B>(f: impl Fn(&dyn Fn(A) -> B, A) -> B) -> impl Fn(A) -> B {
    move |t| (&|g: &dyn Apply<A, B>, x: A| g.apply(g, x))
             (&|g: &dyn Apply<A, B>, x: A| f(&|z| g.apply(g, z), x), t)
}

// The factorial function.
fn fac(n: usize) -> usize {
    let fac = |myself: &dyn Fn(usize) -> usize, x: usize| {
        if x == 0 { 1 } else { x * myself(x - 1) }
    };
    y(fac)(n)
}

// A representation of natural numbers.
enum Nat {
    Zero,
    Succ(Box<Nat>)
}

fn usize2nat(n: usize) -> Nat {
    let usize2nat = |myself: &dyn Fn(usize) -> Nat, n: usize| {
        if n == 0 {
            Nat::Zero
        } else {
            Nat::Succ(Box::new(myself(n - 1)))
        }
    };
    y(usize2nat)(n)
}

impl fmt::Display for Nat {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Nat::Zero => write!(f, "Zero"),
            Nat::Succ(n) => write!(f, "Succ({})", *n),
        }
    }
}

fn main() {
    let n = 6;
    println!("{}", fac(n));
    println!("{}", usize2nat(n))
}