|
=={{header|Rust}}==
{{works with|Rust|1.3544.0 stable}}
<lang rust>
<lang rust>//! A simple implementation of the Y Combinator
//! A simple implementation of the Y Combinator:
// λf.(λx.xx)(λx.f(xx))
// <=>! λf.(λx.f(xx))(λx.f(xx))
//! <=> λf.(λx.f(xx))(λx.f(xx))
// CREDITS: A better version of the previous code that was posted here, with detailed explanation.
// See <y> and also <y_apply>.
// A function type that takes its own type as an input is an infinite recursive type.
// We introduce a trait that will allow us to have an input with the same type as self, and break the recursion.
// The input is going to be a trait object that implements the desired function in the interface.
// NOTE: We will be coercing a reference to a closure into this trait object.
/// A function type that takes its own type as an input is an infinite recursive type.
/// We introduce the "Apply" trait, which will allow us to have an input with the same type as self, and break the recursion.
/// The input is going to be a trait object that implements the desired function in the interface.
trait Apply<T, R> {
fn apply(&self, f: &dyn Apply<T, R>, t: T) -> R;
&self,
f: &dyn Apply<T, R>,
t: T
) -> R;
}
/// If we were to pass in self as f, we get:
// In Rust, closures fall into three kinds: FnOnce, FnMut and Fn.
/// λf.λt.sft
// FnOnce assumed to be able to be called just once if it is not Clone. It is impossible to
/// => λs.λt.sst [s/f]
// write recursive FnOnce that is not Clone.
/// => λs.ss
// All FnMut are also FnOnce, although you can call them multiple times, they are not allow to
impl<T, R, F> Apply<T, R> for F where F: Fn(&dyn Apply<T, R>, T) -> R {
// have a reference to themselves. So it is also not possible to write recursive FnMut closures
fn apply(&self, f: &dyn Apply<T, R>, t: T) -> R {
// that is not Clone.
self(f, t)
// All Fn are also FnMut, and all closures of Fn are also Clone. However, programmers can create
}
// Fn objects that are not Clone
// This will work for all Fn objects, not just closures
// And it is a little bit more efficient for Fn closures as it do not clone itself.
impl<T, R, F> Apply<T, R> for F where F:
Fn(&dyn Apply<T, R>, T) -> R
{
fn apply(
&self,
f: &dyn Apply<T, R>,
t: T
) -> R {
self(f, t)
// NOTE: Each letter is an individual symbol.
// (λx.(λy.xxy))(λx.(λy.f(λz.xxz)y))t
// => (λx.xx)(λx.f(xx))t
// => (Yf)t
}
}
/// (λt(λx.(λy.xxy))(λx.(λy.f(λz.xxz)y)))t
// This works for all closures that is Clone, and those are Fn.
/// => (λx.xx)(λx.f(xx))
// impl<T, R, F> Apply<T, R> for F where F: FnOnce( &Apply<T, R>, T ) -> R + Clone {
/// => Yf
// fn apply( &self, f: &Apply<T, R>, t: T ) -> R {
fn y<T, R>(f: impl Fn(&dyn Fn(T) -> R, T) -> R) -> impl Fn(T) -> R {
// (self.clone())( f, t )
move |t| (&|x: &dyn Apply<T, R>, y| x.apply(x, y))
// // If we were to(&|x: pass&dyn inApply<T, selfR>, asy| f(&|z| x.apply(x, wez), gety), -t)
// // NOTE: Each letter is an individual symbol.
// // λf.λt.sft
// // => λs.λt.sst [s/f]
// // => λs.ss
// }
// }
// Before 1.26 we have some limitations and so we need some workarounds. But now impl Trait is stable and we can
// write the following:
fn y<T,R>(f:impl Fn(&dyn Fn(T) -> R, T) -> R) -> impl Fn(T) -> R {
move |t| (
|x: &dyn Apply<T,R>, y| x.apply(x, y)
) (
&|x: &dyn Apply<T,R>, y| f(
&|z| x.apply(x,z),
y
),
t
)
}
/// Factorial of n.
// fn y<T,R>(f:impl FnOnce(&Fn(T) -> R, T) -> R + Clone) -> impl FnOnce(T) -> R {
// |t| (|x: &Apply<T,R>,y| x.apply(x,y))
// (&move |x:&Apply<T,R>,y| f(&|z| x.apply(x,z), y), t)
// // NOTE: Each letter is an individual symbol.
// // (λx.(λy.xxy))(λx.(λy.f(λz.xxz)y))t
// // => (λx.xx)(λx.f(xx))t
// // => (Yf)t
// }
// Previous version removed as they are just hacks when impl Trait is not available.
fn fac(n: usize) -> usize {
let almost_fac = |f: &dyn Fn(usize) -> usize, x| if x == 0 { 1 } else { x * f(x - 1) };
y(almost_fac)(n)
if x == 0 {
1
} else {
x * f(x - 1)
}
;
let fac = y( almost_fac );
fac(n)
}
/// nth Fibonacci number.
fn fib( n: usize ) -> usize {
fn let almost_fib = |ffib(n: &dyn Fn(usize) -> usize, x|{
let almost_fib = |f: &dyn Fn((usize, usize, usize)) -> usize, (a0, a1, x)|
if x < 2 {
1 match x {
} else { 0 => a0,
f(x - 2) + f(x - 1) => a1,
_ => f((a1, a0 + a1, x - 1)),
};
let fib = y(almost_fib) };
fib(n)
y(almost_fib)((1, 1, n))
}
/// Driver function.
fn optimal_fib( n: usize ) -> usize {
fn main() {
let almost_fib = |f: &dyn Fn((usize,usize,usize)) -> usize, (i0,i1,x)|
matchlet xn {= 10;
println!("fac({}) = {}", n, fac(n));
0 => i0,
println!("fib({}) = {}", n, fib(n));
1 => i1,
x => f((i1,i0+i1, x-1))
}
;
let fib = |x| y(almost_fib)((1,1,x));
fib(n)
}
</lang>
fn main() {
println!("{}", fac(10));
println!("{}", fib(10));
println!("{}", optimal_fib(10));
}</lang>
{{output}}
<pre>3628800
fac(10) = 3628800
89
fib(10) = 89
89</pre>
</pre>
=={{header|Scala}}==
| 