Tutorial: The correct way to compute Fibonacci numbers (April Fools)

1

I'd like to present the objectively correct way to implement the Fibonacci function in Rust, leveraging the magical Y combinator. Here it is in all of its glory:

fn main() {
    fn y<A, R>(f: &dyn Fn(&dyn Fn(A) -> R, A) -> R) -> impl Fn(A) -> R + '_ {
        move |a| f(&y(f), a)
    }

    let fibonacci = y(&|f, n| if n <= 1 { n } else { f(n - 1) + f(n - 2) });
    
    println!("{}", fibonacci(40));
}

(Playground)

This is obviously optimal because it:

  • Exudes the elegance of λ-calculus
  • The Y combinator ensures no one will ever touch your code.
  • O(1) time complexity for fixed size integers (2^2^32 is a constant after all)
  • Stack optimal - finally use the entirety of the memory you paid for

Feel free to suggest any improvements, and happy Fool's day! :smiley:

6 Likes